知识点

1.树和二叉树的概念

树是一种非线性的数据结构,它是由n个有限结点组成有层次关系的集合.

• 树具有以下特点，可以根据这些特点来判断一个数据结构是否是树
  • 每个结点具有0个或多个子结点
  • 每个子结点只有一个父结点
  • 没有前驱的结为根结点
  • 除了根结点外，每个子结点又可以由m棵不相关的子树组成

• 树的基本术语
  • 结点的度：结点拥有的子树数量称为结点的度
  • 树的度：树内各结点度的最大值，即上图 D 结点的度就是此树
  • 叶子：度为 0 的节点称为叶子或终端节点
  • 结点的层次和树的深度
  • 森林：m棵互不相交的树的集合。

二叉树与数主要有以下区别：

• 二叉树每个结点至多只有两颗子树(即二叉树中不能存在度大于 2 的结点)
• 二叉树的子树有左右之分，其次序不能任意颠倒
• 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树
• 基本形态

2.二叉树

二叉树的性质：

• 性质 1：在二叉树的第 i 层上最多有 2i-1 个结点（i≥1）；
• 性质 2：深度为 K 的二叉树最多有 2K-1 个结点 （K≥1）；
• 性质 3：对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点数为 n2，则 n0=n2+1；
• 性质 4：具有 n 个结点的完全二叉树的深度为[log₂n]+1。（其中，[log₂n] 的结果是不大于log2n 的最大整数。）

二叉树的存储结构：

• 顺序存储：二叉树顺序存储结构一般只用于完全二叉树
• 链式存储

遍历二叉树

二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次

二叉树遍历方式有三种：

• 先序遍历：根左右（DLR）
• 中序遍历：左跟右（LDR）
• 后序遍历：左右根（LRD）

根据遍历序列确定二叉树

根据前序可知 A 为根节点，再看中序可知 BC 是在根节点 A 左子树，EDGHFI 是在根节点 A 右子树
再看前序和中序可知，B 为 根节点 A 的左孩子，C为B的右孩子，由此类推。

线索二叉树

是在普通二叉树基础上，通过利用空指针域来存储结点在某种遍历次序下的前驱或后继信息，从而加速遍历操作的一种数据结构。—-线索二叉树
对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化

总结：

• 对于n个结点的二叉树，则在二叉链存储结构中就会有n+1个空链域
• 对于一个有 n 个结点的二叉链表，每个结点指向左右孩子的两个指针域，故共有 2n 个指针域，而 n 个结点的二叉树共有 n-1 条分支，即存在 2n-(n-1) = n+1 个空链域
• 如果一个结点的左孩子为空，则指向它的前驱结点。
• 如果一个结点右孩子为空，则指向它的后继。

3.树和森林

树的存储结构：

• 双亲表示法
• 孩子表示法
• 孩子兄弟表示法

森林与二叉树的转换

1.树==>二叉树

条件：

• 给兄弟加线
• 给除长子外的孩子去线
• 层次调整（孩子在左兄弟在右）

2.二叉树==>树

条件：

• 左孩子的左孩子和右孩子的右孩子加线
• 右孩子去线

3.森林==>二叉树

条件：

• 森林中的每一棵树==>二叉树
• 将所有二叉树==>一颗二叉树（将后序的二叉树变为前一个二叉树的右节点以此类推）

4.二叉树==>森林

条件：

• 寻找右孩子去线
• 将分离的二叉树转为树

4.哈夫曼树及其应用

基本概念

哈弗曼树不存在度为 1 的结点。
n个叶子结点的哈弗曼树有 2n-1 个结点

在构造哈弗曼树时，是从叶子结点向根节点的方向进行的，每次都是两个两个成对的结点来形成一个新的分支结点，所以不存在度为1的结点。

树的带权路径长度（WPL）:WPL=所有(结点权值×从根到该结点的路径长度)的和

构造哈夫曼树

注意：同值相同时，求和值后置

1. 初始化：根据给定的n个权值 ，构造n棵只有一个根结点的二叉树， 这n棵二叉树构成森林F
2. 找最小树：在F中选取两棵根结点树值最小的树作为左、右子树，构造一颗新的二叉树，置新二叉树根的权值为左、右子树根结点权值之和；
3. 删除与加入：从F中删除这两颗树，并将新树加入F；
4. 判断：重复 2）和 3），直到F中只含一颗树为止，此时得到的这颗二叉树就是哈夫曼树。

示例：w={5,29, 7, 8, 14, 23, 3, 11}

哈夫曼树HT存储结构的初态和终态

例：已知w = (5,29,7,8,14,23,3,11)，利用算法5.10试构造一棵哈夫曼树，计算树的带权路径长度，并给出其构造过程中存储结构HT的初始状态和终结状态。

带权路径长度：WPL=23 × 2 + 11 × 3 + 5 × 4 + 3 × 4+ 29 × 2 + 14 × 3 + 7 × 4 + 8 × 4 = 271

方法：
HT初态：按照顺序，将权值依次填入，并且父节点，左孩右孩均为0，并将哈夫曼树的所有节点依次写出
HT终态：填写对应左右父节点

哈夫曼编码

前缀码：如果在一个编码系统中，任一个编码都不是其他任何编码的前缀，则称该编码系统中的编码是前缀码。例如，一组编码01,001,010,100,110就不是前缀码，因为01是010的前缀，若去掉01或010就是前缀码。

哈夫曼编码：对一棵具有n个叶子的哈夫曼树，若对树中的每个左分支赋予0，右分支赋予1，则从根到每个叶子的通路上，各分支的赋值分别构成一个二进制串，该二进制串就称为哈夫曼编码。

练习题

一、选择题

1.有关二叉树下列说法正确的是（ ）
A. 二叉树中至少有一个结点的度为2
B. 二叉树中每个结点的度都为2
C. 二叉树中任何一个结点的度都为2
D. 一棵二叉树的度可以小于2

2.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）
A. 250
B. 500
C. 254
D. 501

3.已知一算术表达式的中缀形式为 A-B/C+DE，前缀形式为+-A/BCDE，其后缀形式为( )
A. AB/C-DE+
B. ABC/-DE+
C. ABCDE/-+
D. A-BC/DE+

4.已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（ ）
A. 不确定
B. CBEFDA
C. FEDCBA
D. CBEDFA

5.引入二叉线索树的目的是（ ）
A. 加快查找结点的前驱或后继的速度
B. 为了能在二叉树中方便的进行插入与删除
C. 为了能方便的找到双亲
D. 使二叉树的遍历结果唯一

6.在有10个结点的二叉树的二叉链表表示中,空指针数为( )
A. 不定
B. 11
C. 10
D. 9

7.设二叉树T的树根为第一层,则在二叉树T的第k层至多有__个结点
A. 2k-1
B. 2k
C. 2k-1
D. log₂k+1

8.100个结点的完全二叉树采用顺序存储，从1开始按层次编号，则编号最小的叶子结点的编号应该是（ ）
A. 100
B. 51
C. 50
D. 49

9.深度为h的满m叉树的第k层有（ ）个结点。(1≤k≤h)
A. m^k-1
B. m^k-1
C. m^h-1
D. m^h-1

10.在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（ ）
A. 41
B. 82
C. 113
D. 122

11.不含任何结点的空树( )
A. 是一棵树
B. 是一棵二叉树
C. 是一棵树也是一棵二叉树
D. 既不是树也不是二叉树

12.若一棵二叉树的前序遍历序列为a,e,b,d,c,后序遍历序列为b,c,d,e,a,则根结点的孩子结点( )
A. 只有e
B. 有e,b
C. 有e,c
D. 无法确定

13.具有30个结点的完全二叉树的深度为( )
A. 4
B. 5
C. 6
D. 7

14.利用二叉链表存储树,则根结点的右指针是( )
A. 指向最左孩子
B. 指向最右孩子
C. 空
D. 非空

15.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ ）遍历实现编号
A. 先序
B. 中序
C. 后序
D. 从根开始按层次遍历

16.二叉树是非线性数据结构,所以( )
A. 它不能用顺序存储结构存储
B. 它不能用链式存储结构存储
C. 顺序存储结构和链式存储结构都能存储
D. 顺序存储结构和链式存储结构都不能使用

17.在一棵度为3的树中,度为3的结点有2个,度为2的结点有1个,度为1的结点有2个,那么,该树有()个叶结点
A. 4
B. 5
C. 6
D. 7

18.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是( )
A. 9
B. 11
C. 15
D. 不确定

19.设树中某结点不是根结点,则离它最近的祖先结点是( )
A. 父结点
B. 父结点的父结点
C. 该结点本身
D. 根结点

20.一棵有124个叶子结点的完全二叉树最多有( )个结点
A. 247
B. 248
C. 249
D. 250

21.在下列存储形式中，哪一个不是树的存储形式？（ ）
A. 双亲表示法
B. 孩子链表表示法
C. 孩子兄弟表示法
D. 顺序存储表示法

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

23.表达人类社会中的族谱关系最适合的数据结构为（ ）
A. 树
B. 图
C. 数组
D. 线性表

24.深度为5的二叉树至多有 ( )个结点
A. 16
B. 32
C. 31
D. 10

25.一棵有n个结点的树的所有结点的度数之和为( )
A. n-1
B. n
C. n+1
D. 2n

26.在下述结论中,正确的是( )
A. 二叉树的度为0
B. 二叉树所有结点的度均为2
C. 二叉树的左右子树可任意交换
D. 深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树的结点个数

27.由3个结点可以构造出多少种不同的二叉树( )
A. 2
B. 3
C. 4
D. 5

28.若一棵度为4的树T中，度为1、2、3、4的结点个数分别为4、3、2、2，则T中叶子结点的个数为（ ）。
A. 13
B. 14
C. 15
D. 24

29.表达学校院系等组织关系最适合的数据结构为（ ）。
A. 树
B. 图
C. 数组
D. 线性表

30.在一棵高度为k的满二叉树中，结点总数为（ ）。
A. 2k
B. 2^k−1
C. 2^k−1
D. 2^k−1+1

31.—裸完全二叉树上有98个结点，其中叶子结点的个数是（ ）。
A. 48
B. 51
C. 49
D. 50

32.某二叉树中有60个叶子结点，则该二叉树中度为2的结点个数为（ ）。
A. 61
B. 60
C. 59
D. 不一定

33.一个具有129个结点的二叉树的高h为（ ）。
A. 7
B. 8
C. 7至129之间
D. 8至129之间

34.具有 m 个结点的二叉树用三叉链式存储结构时，空指针的个数为（ ）。
A. 2m
B. m+1
C. 3m
D. m+2

35.题目：在有20个结点的二叉树的二叉链表表示中，空指针数为（ ）。
A. 不定
B. 21
C. 20
D. 9

36.若X是后序线索二叉树中的叶子结点，且X存在左兄弟结点Y，则X的右线索指向（ ）。
A. X的父结点
B. 以Y为根的子树的最左下结点
C. X的左兄弟结点Y
D. 以Y为根的子树的最右下结点

37.设哈夫曼树中有199个结点，则该哈夫曼树中有（ ）个叶子结点。
A. 99
B. 100
C. 101
D. 102

38.以下属于前缀编码的是（ ）。
A. {0,1,01,010,110}
B. {01,00,10,001,110,101}
C. {0,1101,1110,1100,1111}
D. {00,01,10,11,101}

39.n (n≥2) 个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（ ）。
A. 该树一定是—棵完全二叉树
B. 树中一定没有度为1的结点
C. 树中两个权值最小的结点一定是兄弟结点
D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值

二、填空题

1.线索二叉树的左线索指向其（ 1 ），右线索指向其（2 ）

2.已知完全二叉树第6层上有10个叶子结点，则这棵二叉树的结点总数最多是（）个

3.给定二叉树的两种遍历序列，分别是：前序遍历序列：A，B，D，C，E，G，F；中序遍历序列：D，B，A，E，G，C，F；该二叉树的后序遍历序列为（1）

4.给定如图所示二叉树T，其对应的中序线索二叉树中结点64的前驱指向结点 （1） ，结点70的后继指向结点（2） 。

5.将下列森林转化为二叉树，回答以下问题：转换完成后的二叉树的深度为 （1） ，度为1的结点个数为（2） ，叶子结点个数为 （3） 。

6.已知某图片中只可能出现八种颜色，其概率分别为0.04、0.30、0.07、0.08、0.15、0.22、0.03、0.11。构造哈夫曼树，并为这8种颜色设计哈夫曼编码。
规定：
（1）在构造哈夫曼树时，左子树结点的权值小于右子树结点的权值，相同值按从左到右顺序。
（2）进行哈夫曼编码时，左分支标0，右分支标1；

0.04:(1)
0.30:(2)
0.07:(3)
0.08:(4)
0.15:(5)
0.22:(6)
0.03:(7)
0.11:(8)

（3）当传输的图片有10000个像素时，采用定长编码共需要传送（9）个bit？采用Huffman编码需要传送（10）个bit？

三、判断题

3.给出二叉树的任意两种遍历结果，可以唯一确定这棵二叉树
A. 对
B. 错

答案解析

一、单选题解析

1.正确答案：D
解析：二叉树结点的度≤2，因此一棵二叉树的度可以小于2（例如，只有一个根结点的二叉树度为0）。

2.正确答案：D
解析：设度为0结点（叶子结点）个数为A，度为1的结点个数为B，度为2的结点个数为C，有A=C+1，A+B+C=1001，可得2C+B=1000。由完全二叉树的性质可得B=0或1，又因为C为整数，所以B=0，C=500，A=501，即有501个叶子结点。

3.正确答案：B
解析：中缀表达式是中序遍历的结果，前缀表达式是先序遍历的结果。已知二叉树的中序和前序遍历结果，可以唯一确定一颗二叉树，从而得出二叉树的后序遍历结果即后缀表达式。

4.正确答案：B
解析：已知二叉树的中序和前序遍历结果，可以唯一确定一颗二叉树，从而得出二叉树的后序遍历结果。

5.正确答案：A
解析：为了保存二叉树遍历过程中得到的每个结点的前驱和后继信息，引入了线索二叉树，以加快查找结点的前驱或后继的速度。

6.正确答案：B
解析：在有n个结点的二叉树的二叉链表表示中，空指针数为n+1。

7.正确答案：A
解析：二叉树第k层至多有2^(k-1)个结点。

8.正确答案：B
解析：根据二叉树性质，对于完全二叉树，编号大于⌊n/2⌋的结点均为叶子结点。100/2=50，因此从51号结点开始是叶子结点，最小的编号是51。

9.正确答案：A
解析：深度为h的满m叉树第k层有m^(k-1)个结点。

10.正确答案：B
解析：树的分支总数=20×4+10×3+1×2+10×1=122。树的结点总数=分支总数+1=123。叶子结点数=123-20-10-1-10=82。

11.正确答案：C
解析：空树既是树也是二叉树的一种特殊形态。

12.正确答案：A
解析：根据前序序列（根左右）和后序序列（左右根）分析，根结点为a。前序第二个结点为e，说明e是a的孩子。若e是左孩子，则根据后序序列判断右子树为空；若e是右孩子，则左子树为空。因此，根结点只有一个孩子e。

13.正确答案：B
解析：具有n个结点的完全二叉树的深度为⌊log₂n⌋+1。⌊log₂30⌋+1=4+1=5。

14.正确答案：C
解析：树转换为二叉树的右指针域用于指向兄弟结点。树的根结点没有兄弟，因此其右指针为空。

15.正确答案：C
解析：题目要求编号顺序为：左孩子 < 右孩子 < 父结点。这恰好是后序遍历（左右根）访问结点的顺序。

16.正确答案：C
解析：二叉树既可以用顺序存储结构（如数组）存储，也可以用链式存储结构（如二叉链表）存储。

17.正确答案：C
解析：分支总数=2×3+1×2+2×1=10。结点总数=分支总数+1=11。叶子结点数=11-2-1-2=6。

18.正确答案：B
解析：总结点数N = N0 + N1 + N2。在二叉树中，有N0 = N2 + 1。已知N2=10，N1=5，则N0=10+1=11。总结点数N=11+5+10=26，验证了N0=11。

19.正确答案：A
解析：在树结构中，离一个非根结点最近的祖先结点就是它的父结点。

20.正确答案：B
解析：对于完全二叉树，叶子结点数N0 = ⌈N/2⌉。要使N最大且N0=124，则N应为偶数，最大为124×2=248。

21.正确答案：D
解析：树的常用存储形式有：双亲表示法、孩子链表表示法、孩子兄弟表示法。顺序存储法通常用于完全二叉树，对一般树不适用。

22.正确答案：C
解析：n个结点的二叉树有2n个指针域，其中n-1个用于指向孩子（n个结点有n-1条边），剩余n+1个为空。线索二叉树正是利用这n+1个空指针存储线索。

23.正确答案：A
解析：族谱关系具有明显的层次和分支结构，且一个父结点可以有多个子结点，但一个子结点通常只有一个父结点，这符合树的定义。

24.正确答案：C
解析：深度为k的二叉树至多有2^k – 1个结点。2^5 – 1 = 31。

25.正确答案：A
解析：在一棵有n个结点的树中，边的总数为n-1。而所有结点的度数之和等于边数的两倍，即2×(n-1)。但注意，在树中，结点的“度”是指该结点拥有的子结点数，所有结点的度数之和恰好等于边数，即n-1。

26.正确答案：D
解析：深度相同的完全二叉树的结点数少于或等于满二叉树的结点数，这是由定义决定的。

27.正确答案：D
解析：3个结点可以构成5种不同形态的二叉树（卡特兰数C₃=5）。

28.答案：B
解析：25-4-3-2-2=14
29.答案：A
解析：层次关系是最常见的树形结构
30.答案：B
解析：二叉树的性质二
31.答案：C
解析：设度为0结点（叶子结点）个数为A，度为1的结点个数为B，度为2的结点个数为C，有A=C+1，A+B+C=1001，可得2C+B=1000。由完全二叉树的性质可得B=0或1，又因为C为整数，所以B=0，C=500，A=501，即有501个叶子结点。
32.答案：C
解析：二叉树中度为2的结点比度为0的结点少1。
33.答案：D
解析：若每层仅有一个结点，则树高h为1025；且其最小树高为完全二叉树即
log₂1025+1=11，即h在11至1025之间。
34.答案：D
解析：总指针数为 3m，一共占用的指针数位 2 (m-1) ，所以剩余 3m-2(m-1)=m+2。
35.答案：B
解析：在有20个结点的二叉树的二叉链表表示中，空指针数为20+1。
36.答案：A
解析：由后序遍历顺序为左右根，叶子结点有左兄弟，说明该结点是右孩子，那么后序遍历顺序为：该结点的父结点的左子树遍历完然后就是这叶子结点，然后就父结点，所以他的后继就是其父结点。
37.答案：B
解析：在哈夫曼树中没有度为1的结点，只有度为0（叶子结点）和度为2的结点。设叶子结点的个数为n0，度为2的结点的个数为n2，由二叉树的性质n0=n2+1，则总结点数n=n0+n2=2*n0-1，得到n0=100。
38.答案：C
解析：前缀编码指的是，任何一个字符的编码都不是同一字符串中另一个字符的编码的前缀。本题中只有C选项符合前缀编码的定义。
39.答案：A
解析：哈夫曼树的构造过程是每次选取权值最小的树作为左右子树构造—棵新的二叉树，所以树中一定没有度为1的结点。两个权值最小的结点一定是兄弟结点。任一非叶结点的权值一定不小于下一层任一结点的权值。

二、填空题解析

1.正确答案：
(1) 前驱（或前驱结点，或遍历序列中的前驱）
(2) 后继（或后继结点，或遍历序列中的后继）
解析：线索二叉树的左线索指向前驱，右线索指向后继，这里的“前驱”和“后继”是指在某种遍历序列中的直接前驱和直接后继。

2.正确答案：107
解析：完全二叉树的叶子结点集中在最后两层。第6层有10个叶子，欲使总结点数最多，则树深度应为7。第6层满时有2^(6-1)=32个结点，其中10个为叶子，则22个为分支结点。这22个分支结点会在第7层产生44个叶子结点。第1至6层的结点总数为2^6-1=63个。所以总结点数最多为63+44=107。

3.正确答案：DBGEFCA

4.正确答案：(1) 35 (2) 58

解析：写出中序遍历序列，然后进行线索化。

5.正确答案：(1) 6 (2) 6 (3) 3

6.正确答案
(1) 10011
(2) 11
(3) 1000
(4) 000
(5) 101
(6) 01
(7) 10010
(8) 001
(9) 30000
(10) 26900

解析：

(1) 哈夫曼树为：

(2) 当传输的图片有10000个像素时，采用定长编码需要用3位二进制码表示8种颜色，共需要传送3*10000=30000个bit？采用Huffman编码（不等长）计算带权路径长度为 (0.03+0.04) *5+0.07*4+ $(0.08+0.15+0.11)$(0.08+0.15+0.11) *3+ $(0.30+0.22)$(0.30+0.22) *2=2.69, 需要传送10000*2.69=26900个bit？

三、判断题解析

1.正确答案：B（错）
解析：给出二叉树的先序和中序、或者中序和后序遍历结果可以唯一确定一棵二叉树。但给定二叉树的先序和后序序列，不能唯一确定一棵二叉树（当树中结点存在单分支时无法确定左右）。