第 4 章 树和二叉树

作者： 作者的头像   huolong , 时间：2026-09-07 22:05:06 , 所有人可见, 阅读  1

第 4 章 树和二叉树

4.1 树

1、常见的数据结构？

（1）集合 集合的定义是由一组无序且唯一（即不能重复）的项组成的。不包含任何元素的集合就叫做空集。 （2）线性结构 线性结构是一个有序数据元素的集合。 常用的线性结构有：线性表，栈，队列，双队列，数组，串。 （3）树形结构 $n$ 个有限节点组成一个具有层次关系的集合。 （4）图形结构 图形结构——多个对多个，如图。

2、什么是树？

树：是一种数据结构，它是由 $n(n \ge 0)$ 个有限节点组成一个具有层次关系的集合。树是一类非线性结构。这种结构结点之间有分支，并具有层次关系。它非常类似于自然界中的树。 树的作用：表达家谱顺序、行政组织结构、计算机文件结构、书的教材章节结构等。

3、树的基本概念

（1）树是 $n(n \ge 0)$ 个结点的有限集。 （2）当 $n=0$ 时称为空树； （3）当 $n>0$ 时为非空树，在任意一棵非空树中，有且仅有一个称为根的结点，其余的结点可分为 $m(m \ge 0)$ 个互不相交的有限集 $T_1, T_2, \dots, T_m$，其中每一个集合又称为一棵树，并且称为根的子树；同理，每一棵子树又可以分为若干个互不相交的有限集……

总结树的特性： （1）空树是树的特例; （2）非空树中至少有一个结点，称为树的根，只有根结点的树称为最小树; （3）在含有多个结点的树中，除根结点外，其余结点构成若干棵子树，且各子树间互不相交。

4、树的基本术语

（1）树的结点：包含一个数据元素及若干个指向其子树的分支； （2）结点的度：一个结点拥有的子树数目； （3）树的度：一棵树上所有结点度的最大值； （4）叶子结点（终端结点）：度为零的结点； （5）分支结点（非终端结点）：度大于零的结点； （6）路径（从根到结点的）：由从根到该结点所经分支和结点构成； （7）孩子结点：结点的子树的根称为该结点的孩子结点； （8）双亲结点：相应地，该结点称为孩子的双亲结点； （9）兄弟：具有同一父结点的子结点互称兄弟； （10）堂兄弟：其双亲在同一层的结点互为堂兄弟； （11）祖先结点：从根到该结点所经分支上的所有结点； （12）子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙； （13）结点的层次：从根结点到该结点所经过的路径长度加 1； （14）树的深度：树中叶子结点具有的最大层次数； （15）树的宽度：整棵树中某一层中最多的结点数称为树的宽度； （16）有序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，与之相对的是无序树； （17）第一个孩子：在有序树中，最左边的子树的根称为第一个孩子； （18）最后一个孩子：在有序树中，最右边的子树的根称为最后一个孩子；

练习：参照右图的树，回答下列问题 （1）该树有哪些结点 ABCDEFGHIJKLM，其中的叶子节点有 EKLGHIM，分支节点有 ABCDFJ。 （2）结点 A 的度为 3，结点 B 的度为 2，树的度为 3。 （3）请写出 A 节点到 K 节点经过的路径 A->B->F->K。 （4）H 结点的兄弟结点有 I、J，堂兄弟结点有 E、F、G。 （5）F 结点的祖先结点有 B、A，子孙结点有 K、L。 （6）该树的深度为 4，树的宽度为 6。

5、树的表示方法

了解树的表示方法。 * 嵌套集合 * 广义表：(A (B (E (K, L), F), C (G), D (H (M), I, J))) * 凹入表示 * 二叉链表（孩子-兄弟）表示法 在这种存储方式下，每个结点包括三部分的内容：结点值、指向该结点第一个孩子结点的指针和指向该结点下一个兄弟结点的指针。 [ firstchild | data | nextsiblings ]

4.2 二叉树

1、什么是二叉树？

二叉树是 $n(n \ge 0)$ 个结点的有限集合，这个集合或是空集，或是由一个根结点以及两棵互不相交的、被称为根的左子树和右子树所组成；左子树和右子树分别又是一棵二叉树。 二叉树的特点：每个结点至多只有两棵子树，且二叉树的子树有左右之分，其次序不能任意颠倒。

问题：二叉树和树有哪些不同？ ① 树中结点的最大度数没有限制，而二叉树结点的最大度数为 2。 ② 树的结点无左、右之分，而二叉树的结点有左右之分。

问题：具有 3 个结点的二叉树可能有 5 种不同形态？普通树有 2 种不同的形态？请分别画出他们。

2、满二叉树和完全二叉树

  • 满二叉树：一棵深度为 $k$ 且有 $2^k-1$ 个结点的二叉树。（特点：每一层上的结点数都是最大结点数）
  • 完全二叉树：深度为 $k$ 的，有 $n$ 个结点的二叉树，当且仅当其每一个结点都与深度为 $k$ 的满二叉树中编号从 1 至 $n$ 的结点一一对应（特点：至多只有最下面两层的结点的度可以小于 2，且倒二层如果只有一个孩子，那必是左孩子。）

注意：满二叉树是叶子一个也不少的树，而完全二叉树虽然前 $n-1$ 层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。 一棵深度为 $k$ 的完全二叉树，至少有 $2^{k-1}$ 个结点，最多有 $2^k-1$ 个结点。

3、二叉树的性质

① 性质 1：在二叉树的第 $i$ 层上至多有 $2^{i-1}$ 个结点（$i \ge 1$）。 * 问题：在第 $i$ 层上至少有 1 个结点。 ② 性质 2：深度为 $h$ 的二叉树至多有 $2^h-1$ 个结点（$h \ge 1$）。 * 问题：一棵深度为 $k$ 且有 $2^k-1$ 个结点的二叉树称为满二叉树。 * 问题：一颗深度为 $k$ 的二叉树，至少有 k 个结点。 ③ 性质 3：对任何一棵二叉树，如果其叶结点数 $n_0$，度为 2 的结点数为 $n_2$，则一定满足：$n_0 = n_2 + 1$。 * 问题：一棵完全二叉树有 5000 个结点，可以计算出其叶结点的个数是 2500。 ④ 性质 4：具有 $n$ 个结点的完全二叉树的深度为 floor(log2n)+1。 ⑤ 性质 5：对于一棵 $n$ 个结点的完全二叉树，对任一个结点（编号为 $i$） * 如果 $i=1$，则结点 $i$ 为根，无 父结点；如果 $i>1$，则其父结点编号为 floor(i/2)。 * 如果 $2i>n$，则结点 $i$ 无 子节点，即结点 $i$ 为 叶结点；否则左孩子编号为 2i。 * 如果 $2i+1>n$，则结点 $i$ 无 右孩子，否则右孩子编号为 2i+1。

4、二叉树的存储

（1）表示方法一：数组表示法 对于完全二叉树，用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。 对于一般二叉树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应位置中。 （2）表示方法二：字符串表示法；本质上来说，还是数组表示法。 例如字符串表示为：string s = "LDPCFM###EH#N"; （3）表示方法三：链式存储； 采用：含有两个指针域的结点结构体及链表的结构进行存储。 结点结构：[ lchild | data | rchild ] 问题：在 $n$ 个结点的二叉树链表中，有 n+1 个空指针域。

5、遍历方案

一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作: （1）访问根结点（D）; （2）遍历该结点的左子树（L）; （3）遍历该结点的右子树（R）;

遍历方案： * DLR：先序遍历（Preorder Traverse，亦称前序遍历） ———访问根结点、遍历左树、遍历右树。 * LDR：中序遍历（Inorder Traverse） ———遍历左树、访问根结点、遍历右树。 * LRD：后序遍历（Postorder Traverse） ———遍历左树、遍历右树、访问根结点。

先序遍历的结果为：A B C D E F G H K； 中序遍历的结果为：B D C A E H G K F； 后序遍历的结果为：D C B H K G F E A；

重要结论：若二叉树中各结点的值均不相同，则：由二叉树的 前序序列和中序序列，或由其 后序序列和中序序列 均能唯一地确定一棵二叉树，但由 前序序列和后序序列 却不一定能唯一地确定一棵二叉树。

问题：已知一棵二叉树的中序序列和后序序列分别是 BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。 * 解答： 中序，左根右：BDCEAFHG 后序，左右根：DECBHGFA

问题： ① 二叉树的先序序列和中序序列相同的条件是 任何结点至多只有右子树，没有左子树或是空树。 ② 二叉树的中序序列和后序序列相同的条件是 任何结点至多只有左子树，没有右子树或是空树。 ③ 二叉树的先序序列和后序序列相同的条件是 只有根结点。

4.3 树和二叉树课堂练习

【NOIP 普及组】一棵二叉树如右图所示,若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为 1,若某结点的下标为 $i$,则其左孩子位于下标 $2i$ 处、右孩子位于下标 $2i+1$ 处）,则该数组的最大下标至少为（ ）。 A. 6 B. 10 C. 15 D. 12 答案：C 解析：根据题目给定的规则可知,下标最大的结点为树中深度最大且最靠右的结点,其下标为 ((1*2+1)*2+1)*2+1 = 15。

【NOIP 普及组】假设一棵二叉树的后序遍历序列为 DGJHEBFCA，中序遍历序列为 DBGEHJACIF，则其前序遍历序列为（ ） A. ABCDEFGHIJ B. ABDEHJCFI C. ABDEGJHCFI D. ABDEGHJFIC 答案：B 解析：后序遍历的规则是“左右根”、中序遍历的规则是“左根右”,因此可知 A 是树根、DBGEHJ 是 A 左子树的中序遍历（对应后续遍历 DGJHEB）、CIF 是 A 右子树的中序遍历（对应后续遍历 IFC），递归画出对应的二叉树,再根据前序遍历规则“根左右”即可求出答案。

【NOIP 普及组】根节点深度为 0，一棵深度为 $h$ 的满 $k(k>1)$ 叉树，即除最后一层无任何子节点外，每一层上的所有结点都有 $k$ 个子结点的树，共有（ ）个结点。 A. $(k^{h+1} - 1) / (k - 1)$ B. $k^{h-1}$ C. $k^h$ D. $(k^{h-1}) / (k - 1)$ 答案：A 解析：假设 $h=2, k=2$，画出完美二叉树，共 7 个节点，带入运算，得到选 A。 推导过程： 深度为 $h$ 的树(根节点深度为 0),其总节点数为： $s = k^0 + k^1 + k^2 + \dots + k^h$ （公式 1） 两边都乘以 $k$,得到： $sk = k^1 + k^2 + \dots + k^h + k^{h+1}$ （公式 2） 公式 2 减公式 1,得到： $(k-1)s = k^{h+1} - k^0 = k^{h+1} - 1$ 于是 $s = (k^{h+1}-1)/(k-1)$

【NOIP 提高组】下列说法中，是树的性质的有（ ）。【不定项选择】 A. 无环 B. 任意两个结点之间有且只有一条简单路径 C. 有且只有一个简单环 D. 边的数目恰是顶点数目减 1 答案：ABD

【NOIP 提高组】一棵二叉树如右图所示，若采用二叉树链表存储该二叉树（各个结点包括结点的数据、左孩子指针、右孩子指针）。如果没有左孩子或者右孩子，则对应的为空指针。那么该链表中空指针的数目为（ ）。 A. 6 B. 7 C. 12 D. 14 答案：B

【NOIP 普及组】前序遍历序列与中序遍历序列相同的二叉树为（ ） A. 根结点无左子树的二叉树 B. 根结点无右子树的二叉树 C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树 D. 只有根结点的二叉树或非叶子结点只有右子树的二叉树 答案：D

【NOIP 普及组】如果根的高度为 1，具有 61 个结点的完全二叉树的高度为（ ） A. 5 B. 6 C. 7 D. 8 答案：B

4.4 树和二叉树习题 1

一、单项选择题

1．下列说法中正确的是 ( D ) A．任何一棵二叉树中至少有一个结点的度为 2 B．任何一棵二叉树中每个结点的度都为 2 C．任何一棵二叉树中的度肯定等于 2 D．任何一棵二叉树中的度可以小于 2

2．树最适合用来表示 ( C ) A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据

3．若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是（ B ） A．9 B．11 C．15 D．不确定

4．一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是（ E ）（注：计算为 501） A．250 B．500 C．254 D．505 E．以上答案都不对

5．二叉树的第 $i$ 层上最多含有结点数为（ C ） A．$2^i$ B．$2^{i-1}-1$ C．$2^{i-1}$ D．$2^i - 1$

6．一棵二叉树高度为 $h$, 所有结点的度或为 0，或为 2，则这棵二叉树最少有( B )结点 A．$2h$ B．$2h-1$ C．$2h+1$ D．$h+1$

7．已知一棵二叉树的前序遍历结果为 ABCDEF，中序遍历结果为 BADCFE，则后序遍历的结果为（ A ）。 A．BDFECA B．FEDCBA C．BDCAFE D．不定

8．已知某二叉树的后序遍历序列是 dbeca，中序遍历序列是 debac，它的前序遍历是（ D ）。 A．acbed B．decba C．debac D．cedba

9．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ B ） A．都不相同 B．完全相同 C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同

10．在完全二叉树中，若一个结点是叶结点，则它没（ C ）。 A．左子结点和兄弟结点 B．右子结点和兄弟结点 C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点

11．$n$ 个结点的线索二叉树上含有的线索数为（ C ） A．$2n$ B．$n-1$ C．$n+1$ D．$n$

12．由 3 个结点可以构造出多少种不同的二叉树？（ D ） A．2 B．3 C．4 D．5

  1. 一棵有 $n$ 个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组 $A[1..n]$ 中，则二叉树中第 $i$ 个结点（$i$ 从 1 开始用上述方法编号）的右孩子在数组 $A$ 中的位置是（ D ） A．$A[2i]$ ($2i \le n$) B．$A[2i+1]$ ($2i+1 \le n$) C．$A[i-2]$ D．条件不充分，无法确定

二、填空题

1．深度为 $k$ 的完全二叉树至少有 $2^{k-1}$ 个结点，至多有 $2^k-1$ 个结点。 2．高度为 $h$ 的完全二叉树至少有 $2^{h-1}$ 个叶子结点。 3. 具有 $n$ 个结点的二叉树中, 一共有 2n 个指针域, 其中只有 n-1 个用来指向结点的左右孩子，其余的 n+1 个指针域为 NULL。 4．树的主要遍历方法有 先序遍历、后序遍历、中序遍历 等三种。 5．一个深度为 $k$ 的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依次对结点编号，则编号最小的叶子的序号是 $2^{k-2}+1$；编号是 $i$ 的结点所在的层次号是 trunk(log2i)+1。 6．如果结点 A 有 3 个兄弟，而且 B 是 A 的双亲，则 B 的度是 4。 7．二叉树的先序序列和中序序列相同的条件是 任何结点至多只有右子树，没有左子树或是空树。 二叉树的中序序列和后序序列相同的条件是 任何结点至多只有左子树，没有右子树或是空树。 二叉树的先序序列和后序序列相同的条件是 只有根结点。 8．若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的 前序遍历 序列中的最后一个结点。

4.5 树和二叉树习题 2

一. 选择题

  1. 假定在一棵二叉树中，双分支结点数为 15，单分支结点数为 30 个，则叶子结点数为（ B ）个。 A. 15 B. 16 C. 17 D. 47

  2. 深度为 5 的二叉树至多有（ C ）个结点。 A. 16 B. 32 C. 31 D. 10

  3. 设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为（ B ）。 A. 2h B. 2h-1 C. 2h+1 D. h+1

  4. 对一个满二叉树，m 个树叶，n 个结点，深度为 h，则（ D ）。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2h-1

  5. 任何一棵二叉树的叶结点在先序.中序和后序遍历序列中的相对次序（ A ）。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对

  6. 如果某二叉树的前根次序遍历结果为 stuwv，中序遍历为 uwtvs，那么该二叉树的后序为（ C ）。 A. uwvts B. vwuts C. wuvts D. wutsv

  7. 某二叉树的前序遍历结点访问顺序是 abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是（ D ）。 A. adgcefa B. gdarecfha C. adgtechf D. gdbehfca

  8. 在一非空二叉树的中序遍历序列中，根结点的右边（ A ）。 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点

  9. 如图所示二叉树的中序遍历序列是（ B ）。 A. abcdgef B. dfebagc C. dbaefcg D. defbagc

  10. 一棵二叉树如图所示，其中序遍历的序列为（ B ）。 A. abdgecfh B. dgbaechf C. gdbehfca D. abcdefgh

  11. 设 a,b 为一棵二叉树上的两个结点，在中序遍历时，a 在 b 前的条件是（ B ）。 A．a 在 b 的右方 B．a 在 b 的左方 C．a 是 b 的祖先 D．a 是 b 的子孙

  12. 如下图所示的 4 棵二叉树，（ C ）不是完全二叉树。

  13. 某二叉树结点的中序序列为 A.B.C.D.E.F.G，后序序列为 B.D.C.A.F.G.E，则其左子树中结点数目为（ C ）。 A. 3 B. 2 C. 4 D. 5

  14. 具有 $n(n>0)$ 个结点的完全二叉树的深度为（ B ）。 A. $\log_2(n)$ B. $\log_2(n) - 1$ C. $\text{trunc}(\log_2(n)) + 1$ D. $2^n-1$

  15. 将一棵有 100 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为 1，则编号为 49 的结点的左孩子的编号为（ A ）。 A. 98 B. 99 C. 50 D. 48

  16. 将一棵有 100 个结点的完全二叉树从根开始，每一层从左到右依次对结点进行编号，根结点编号为 1，则编号最大的非叶结点的编号为（ C ）。 A. 48 B. 49 C. 50 D. 51

  17. 一棵树深度为 K 的完全二叉树至少有（ B ）个结点 A．$2^k - 1$ B. $2^{k-1}-1$ C. $2^{k-1}$ D. $2^k$

  18. 一棵二叉树的前序遍历序列为 ABCDEFG，它的中序遍历序列可能是（ B ）。 A．CABDEFG B．ABCDEFG C．DCBAEFG D. ADCFEG

  19. 一个具有 1025 个结点的二叉树的高 h 为（ C ）。 A. 11 B. 10 C. 10 至 1025 之间 D. 10 至 1024 之间

  20. 对于有 $n$ 个结点的二叉树, 其高度为（ D ）。 A．$n\log_2 n$ B．$\log_2 n$ C．$\log_2 n + 1$ D．不确定

  21. 在下列关于二叉树的叙述中，正确的是（ D ）。 ①只有一个结点的二叉树度为 0; ②二叉树的度为 2； ③二叉树的左右子树可任意交换; ④深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④

  22. 在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ B ）。 A．都不相同 B．完全相同 C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同

  23. 如图所示二叉树的中序遍历序列是（ B ）。 A．abcdgef B．dfebagc C．dbaefcg D．defbagc

  24. 设 a 和 b 为一棵二叉树上的两个结点，在中序遍历时 a 在 b 前的条件是（ D ）。 A．a 是 b 的左孩子 B．b 是 a 的右孩子 C．a 是 b 左子树上结点或 b 是 a 右子树上结点 D．以上三项均可

  25. 假定在一棵二叉树中，双分支结点数为 15，单分支结点数为 30，则叶子结点数为（ B ）个。 A．45 B．15 C．16 D．31

  26. 二叉树的第 k 层的结点数最多为（ D ）。 A．$2^{k-1}$ B．$2^{k+1}$ C．$2^{K-1}$ D．$2^{k-1}$

  27. 设某棵二叉树中有 2000 个结点，则该二叉树的最小高度为（ C ）。 A. 9 B. 10 C. 11 D. 12

  28. 对于一棵深度为 4 的三叉树，最多有（ D ）个结点。 A. 30 B. 36 C. 40 D. 54

  29. 设结点 A 有 3 个兄弟结点且结点 B 为结点 A 的双亲结点，则结点 B 的度数数为（ A ）。 A. 3 B. 4 C. 5 D. 1

二. 填空题

  1. 一棵具有 257 个结点的完全二叉树，它的深度为 9。
  2. 如某二叉树有 20 个叶子结点，有 30 个结点仅有一个孩子，则该二叉树的总结点数为 69。
  3. 设一棵完全二叉树具有 1000 个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为 2 的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。
  4. 一棵含有 $n$ 个结点（$n>1$）的 k 叉树，可能达到的最大深度为 n，最小深度为 2。
  5. 若已知一棵二叉树的前序序列是 FEGHDCB，中序序列是 FGHDCBE，则它的后序序列必是 FEGHDCB。
  6. 有一棵树如右图所示，回答下面的问题： 1) 这棵树的根结点是 k1； 2) 这棵树的叶子结点是 k2, k4, k5, k7； 3) 结点 k3 的度是 3； 4) 这棵树的度是 3； 5) 这棵树的深度是 4； 6) 结点 k3 的子女是 k5, k6； 7) 结点 k3 的父结点是 k1；
  7. 一棵二叉树的结点数据采用顺序存储结构，存储于数组 t 中，如下图所示，则请画出该二叉树的形状。（略）
  8. 深度为 k 的完全二叉树至少有 $2^{k-1}$ 个结点。至多有 $2^k-1$ 个结点，若按自上而下，从左到右次序给结点编号（从 1 开始），则编号最小的叶子结点的编号是 $2^{k-2}+1$。
  9. 在一棵二叉树中，度为零的结点的个数为 $n_0$，度为 2 的结点的个数为 $n_2$，则有 $n_0 = \text{n2}+1$。
  10. 一棵二叉树的第 $i$（$i \ge 1$）层最多有 $2^{i-1}$ 个结点；一棵有 $n(n>0)$ 个结点的满二叉树共有 (n+1)/2 个叶和 (n-1)/2 个非终端结点。
  11. 由如图所示的二叉树，回答以下问题： 1) 其中序遍历序列为 dgbaechif； 2) 其前序遍历序列为 abdgcefhi； 3) 其后序遍历序列为 gdbeihfca。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com