树是一种非线性的数据结构，它是由n(n>=0) 个有限结点组成一个具有层次关系的集合，当n=0时被称为空树。

树的特点

只有一个特殊的结点，称为根结点，根节点没有前驱结点 树形结构中，除根结点以外，其余结点都被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti（1<=i<=m）又是一棵结构与树类似的子树。 ***每棵子树的根结点（所有节点）有且只有一个前驱，可以有0个或多个后继结点。则n个结点的树有n-1条边，树是递归定义的 ***

树的相关术语

  • 节点的度：一个节点含有的子树的个数称为该节点的度

  • 叶节点或终端节点：度为0的节点称为叶节点，如上图：B、C、H、I、P…等节点

  • 非终端节点或分支节点：度不为0的节点，如上图：D、E、F、G…等节点

  • 双亲节点或父节点：若一个节点含有子节点，则这个节点被称为其子节点的父节点，如F是K和L的父节点

  • 孩子节点或子节点：一个节点含有子树的根节点称为该节点的子节点，如J是E的子节点

  • 兄弟节点：具有相同父节点的节点互称为兄弟节点，如D和E，I和J等等

  • 树的度：一棵树中，最大的节点的度称为树的度，如上图度为6

  • 节点的层次：从根开始定义，根为第1层，根的子节点为第2层，以此类推

  • 树的深度或高度：树中节点的最大层次，如上图：树的高度为4

  • 堂兄弟节点：双亲在同一层的互为堂兄弟；如上图：H和I，他们的父亲在同一层

  • 节点的祖先：从根到该节点所经分支上所有节点的祖先。如上图：A是图中所有节点的祖先

  • 子孙：以某节点为根的所有子树的节点称为该节点的子孙。如上图：所有节点都是A的子孙

  • 森林：由m棵互不相交的树的集合称为森林

树的常见表示方法

对于任意的二叉树都是由以下五种情况复合而成的

  • 满二叉树：每一层节点均为最大节点数的二叉树。

  • 完全二叉树：前h-1层为满二叉树，第h层自左向右是连续的二叉树。

二叉树的节点数和深度计算

  1. 二叉树第i层的结点个数：若规定根结点的层数为 1 ，则一棵非空二叉树的第i层上最多有 2i-1 个结点

  2. 二叉树的总结点个数：若规定根结点的层数为 1 ，则深度为 h 的二叉树的最大结点数是 2h-1

  3. 满二叉树的深度：若规定根结点的层数为 1 ，则具有 n 个结点的满二叉树的深度为h = log2 (n + 1)

  4. 二叉树的叶节点个数和度为2节点个数的关系：h0=h2+1

树的遍历（前序、中序、后序）

以上图为例： 深度优先遍历：  （a）中序（左，根，右）：4 2 5 1 3 

（b）前序（根，左，右）：1 2 4 5 3 

（c）后序（左，右，根）： 4 5 2 3 1

广度优先或级别顺序遍历：1 2 3 4 5

树与二叉树的基本概念和性质

  1. 树的的性质

1）树中的结点数 n 等于所有结点的度数之和加 1

【说明】结点的度是指该结点的孩子数量，每个结点与其每个孩子都由唯一的边相

连，因此树中所有结点的度数之和等于树中的边数之和。树中的结点（除根外）都

有唯一的双亲，因此结点数 n 等于边数之和加 1，即所有结点的度数之和加 1

常用于求解树结点与度之间关系的有： ① 总结点数＝ n0＋ n1 + n2 + …+ nm； ② 总分支数＝ 1n1 + 2n2 + …+ mnm （度为 m 的结点引出 m 条分支）； ③ 总结点数＝总分支数 ＋ 1 。

2）度为 m 的树中第 i 层上至多有 mi-1 个结点（i>=1）

` 【说明】第 1 层至多有 1 个结点（即根结点），第 2 层至多有 m 个结点，第 3 层至多有 m2 个结点，以此类推。使用数学归纳法可推出第 i 层至多有 mi-1个结点。```

3）高度为 h 的 m 叉树至多有 (mh - 1) / (m - 1) 个结点

【说明】当各层结点数达到最大时，树中至多有 1 + m + m2 +…+ mh-1 = (mh - 1) / (m - 1) 个结点。

4）具有 n 个结点的 m 叉树的最小高度 h 为 ⌈logm(n × (m - 1) + 1)⌉

【说明】为使树的高度最小，在前 h - 1 层中，每层的结点数都要达到最大，前 h - 1 层最多有 (mh-1 - 1) / (m - 1) 个结点，前 h 层最多有 (mh - 1) / (m - 1) 个结点。因此 (mh-1 - 1) / (m - 1) < n <= (mh - 1) / (m - 1) ，即 h - 1 < logm(n × (m - 1) + 1) <= h，解得 hmin = ⌈logm(n × (m - 1) + 1)⌉。 ` 5）具有 n 个结点的 m 叉树的最大高度 h 为 n - m + 1

【说明】由于树的度为 m ， 因此至少有一个结点有 m 个孩子，它们处于同一层。为使树的高度最大，其他层可仅有一个结点，因此最大高度（层数）为 n - m + 1 。由此，也可逆推出高度为 h、度为 m 的树至少有 h + m - 1 个结点。

  1. 二叉树的性质 1）非空二叉树上的叶结点数等于度为 2 的结点数加 1 ，即 n0 ＝ n2 + 1

【证明】设度为 0、1 和 2 的结点个数分别为 n0、n1 和 n2，结点总数 n = n0 + n1 + n2 。再看二叉树中的分支数，除根结点外，其余结点都有一个分支进入，设 B 为分支总数，则 n = B + 1 。由于这些分支是由度为 1 或 2 的结点射出的，所以又有 B = n1 + 2n2 。于是得 n0 + n1 + n2 = n1 + 2n2 + 1，则n0 ＝ n2 + 1 。

2）非空二叉树的第 k 层至多有 2k-1 个结点（k>=1）

【说明】第 1 层至多有 20 = 1 个结点（根），第 2 层至多有 21 = 2 个结点，以此类推，可以证明其为一个公比为 2 的等比数列 2k-1 。

3）高度为 h 的二叉树至多有 2h - 1 个结点（h>=1）

【说明】该性质利用性质2) 求前 h 项的和，即等比数列求和的结果。

性质2) 和 3) 还可以拓展到 m 叉树的情况，即 m 叉树的第 k 层最多有 mk-1 个结点，高度为 h 的 m 叉树至多有 (mk - 1) / (m - 1) 个结点。

4）对完全二叉树按从上到下、从左到右的顺序依次编号 1, 2, …, n， 则有以下关系： ① 当 i > 1 时，结点 i 的双亲的编号为 ⌊n / 2⌋，即当 i 为偶数时，其双亲的编号为 i / 2, 它是双亲的左孩子；当 i 为奇数时，其双亲的编号为 (i - 1) / 2, 它是双亲的右孩子。

② 当 2i <= n 时，结点 i 的左孩子编号为 2i，否则无左孩子。

③ 当 2i + 1 <= n 时，结点 i 的右孩子编号为 2i + 1 ，否则无右孩子。

④ 结点 i 所在层次（深度）为 ⌊log2i⌋ + 1。

5）具有 n 个(n >0) 结点的完全二叉树的高度为 ⌈log2(n + 1)⌉ 或 ⌊log2n⌋ + 1

【证明】设高度为 h，根据性质3) 和完全二叉树的定义有：2h-1 - 1 < n <= 2h - 1 或者 2h-1 <= n < 2h，得 2h-1 < n + 1 <= 2h ，即 h - 1 < log2(n + 1) <= h，因为 h 是正整数，所以 h = ⌈log2(n + 1)⌉，或者得 h - 1 <= log2n < h，所以 h = ⌊log2n⌋ + 1。

  1. 二叉树与度为 2 的有序树的区别

1）度为 2 的树至少有 3 个结点，而二叉树可以为空。

2）度为 2 的有序树的孩子的左右次序是相对于另一孩子而言的，若某个结点只有一个孩子，则这个孩子就无须区分其左右次序，而二叉树无论其孩子数是否为 2，均需确定其左右次序，即二叉树的结点次序不是相对于另一结点而言的，而是确定的。

  1. 几种特殊的二叉树

1）满二叉树：一棵高度为 h, 且含有 2h- 1 个结点的二叉树称为满二叉树，即树中的每层都含有最多的结点。满二叉树的叶结点都集中在二叉树的最下一层，并且除叶结点之外的每个结点度数均为 2 。

可以对满二叉树按层序编号：约定编号从根结点（根结点编号为 1 ) 起，自上而下，自左向右。这样，每个结点对应一个编号，对于编号为 i 的结点，若有双亲，则其双亲为 ⌊i / 2⌋，若有左孩子，则左孩子为 2i；若有右孩子，则右孩子为 2i + 1 。

2）完全二叉树：高度为 h 、有 n 个结点的二叉树，当且仅当其每个结点都与高度为 h 的满二叉树中编号为 1~n 的结点一一对应时，称为完全二叉树，其特点如下：

① 若 i <= ⌊n / 2⌋，则结点 i 为分支结点，否则为叶结点，即最后一个分支结点的编号为 ⌊n / 2⌋ 。

② 叶结点只可能在层次最大的两层上出现。对于最大层次中的叶结点，都依次排列在该层最左边的位置上（若删除满二叉树中最底层、最右边的连续 2 个或以上的叶结点，则倒数第二层将会出现叶结点）。

③ 若有度为 1 的结点，则最多只可能有一个，且该结点只有左孩子而无右孩子（重要特征，度为 1 的分支结点只可能是最后一个分支结点，其结点编号为 ⌊n / 2⌋ ）。

④ 按层序编号后，一旦出现某结点（如结点 i ) 为叶结点或只有左孩子，则编号大于 i 的结点均为叶结点。（与结论①和结论③是相通的）。

⑤ 若 n 为奇数，则每个分支结点都有左孩子和右孩子；若 n 为偶数，则编号最大的分支结点（编号为 n / 2 ) 只有左孩子，没有右孩子，其余分支结点都有左、右孩子。

3）二叉排序树：左子树上所有结点的关键字均小于根结点的关键字；右子树上的所有结点的关键字均大于根结点的关键字；左子树和右子树又各是一棵二叉排序树。

4）平衡二叉树：树上任意一个结点的左子树和右子树的深度之差不超过 1 。

有关二叉排序树和平衡二叉树的内容详见：【树形结构查找（BST、AVL树、RBT）】

5）正则二叉树：树中每个分支结点都有 2 个孩子，即树中只有度为 0 或 2 的结点。

正则k叉树：树中每个分支结点都有 k 个孩子，即树中只有度为 0 或 k 的结点。

  1. 有关树与二叉树性质的例题 ① 【2010 统考真题】在一棵度为 4 的树 T 中，若有 20 个度为 4 的结点、10 个度为 3 的结点、1 个度为 2 的结点和 10 个度为 1 的结点，则树 T 的叶结点个数是（ B ）。

A. 41 B. 82 C. 113 D. 122

② 【2016 统考真题】若森林 F 有 15 条边、25 个结点，则 F 包含树的个数是（ C ）。

A. 8 B. 9 C. 10 D. 11

③ 【2009 统考真题】已知一棵完全二叉树的笫 6 层（设根为第 1 层）有 8 个叶结点，则该完全二叉树的结点个数最多是（ C ）。

A. 39 B. 52 C. 111 D. 119

④ 【2011 统考真题】若一棵完全二叉树有 768 个结点，则该二叉树中叶结点的个数是（ C ）。

A. 257 B. 258 C. 384 D. 385

⑤ 【2018 统考真题】设一棵非空完全二叉树 T 的所有叶结点均位于同一层，且每个非叶结点都有 2 个子结点。若 T 有 k 个叶结点，则 T 的结点总数是（ A ）。

A. 2 × k - 1 B. 2 × k C. k2 D. 2k - 1

⑥【2020 统考真题】对于任意一棵高度为 5 且有 10 个结点的二叉树，若采用顺序存储结构保存，每个结点占 1 个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元数量至少是（ A ）。

A. 31 B. 16 C. 15 D. 10

⑦ 【2022 统考真题】若三叉树 T 中有 244 个结点（叶结点的高度为 1 ），则 T 的高度至少是（ C ）。

A. 8 B. 7 C. 6 D. 5