树

定义：若 n 个节点由 n-1 条边相连，且没有环，称为“树”。

普通树

特点：

1. 根节点不确定。
2. 指定根节点后每个节点都有自己唯一的父节点。
3. 各个父节点可有若干个孩子节点。
4. 各个节点一定连通。

性质：

1. 度：一个节点的孩子节点个数。
2. 节点的（深）高度：从根节点到节点 x 的层数,有时从 0 或 1 开始计数。
3. 树的（深）高度：所有节点的（深）高度的最大值。

二叉树

特点：

各个节点的孩子节点不超过 2 个。

性质：

1. 第 i 层最多有 2^{i-1} 个节点。
2. 若从 1 (根节点)开始算树的（深）高度，则深 h 的二叉树最多有 2^h-1 个节点。
3. 若从 1 (根节点)开始算树的（深）高度，则 n 个节点的树的（深）高度至少为 log_{2}n+1。
4. 若叶子节点有 n 个，有 m 个叶子节点的度为 2，则 n =m+1。

分类：

1. 完全二叉树 CBT：除最后一层外，全部放满，且最后一层的叶子节点尽量靠左。

2. 满二叉树 FBT：各个节点要么有 2 个孩子节点，要么没有。

3. 完美二叉树 PBT：（深）高度为 h，有 2^h-1 个节点，且所有位置是放满的。

   遍历树：

   树：

           c
          /  \
          a  d
         /\  \
         h f  b
         \   /
         g   e

4. 先序遍历：根左右(cahgfdbe)。

5. 中序遍历：左根右(hgafcdeb)。

6. 后序遍历：左右根(cadhfbge)。

由遍历顺序还原树：

1. 中序遍历 + 先序遍历：

   a. 先序遍历从头找根节点。

   b. 由根节点划分左右子树。

   c. 重复操作。

2. 中序遍历 + 后序遍历

   a. 后序遍历从后找根节点。

   b. 由根节点划分左右子树。

   c. 重复操作。