第六章树与二叉树
一．选择题
1．下面关于二叉树的结论正确的是____________。
A．二叉树中，度为0 的结点个数等于度为2 的结点个数加1。
B．二叉树中结点个数必大于0。
C．完全二叉树中，任何一个结点的度，或者为0，或者为2。
D．二叉树的度是2。
分析：该题目主要考查二叉树逻辑结构的特点。正确答案为A。二叉树中叶
子结点的个数为n0 ，度为 2 的结点的个数为n2，度为1 的结点个数为n1，
树中结点总数为n，则n= n0+ n2+ n1。除根节点没有双亲外，每个结点都有
且仅有一个双亲，所以有n-1= n1+ 2n2 作为孩子的结点，因此有n0= n2+1。
二叉树中结点个数可以为0，称为空树，所以B 错。满二叉树中，任何一个
结点的度，或者为0，或者为2。完全二叉树中，任何一个结点的度，或者
为0，或者为1，或者为2。所以C 错。二叉树的度可以是0、1、2。所以D 错。
2．设X 是树T 中的一个非根结点，B 是T 所对应得二叉树，在B 中，X 是
其双亲的右孩子，下列结论正确的是____________。
A．在树T 中，Ｘ是其双亲的第一个孩子。B．在树T 中，Ｘ一定无右边
兄弟。
C．在树T 中，Ｘ一定是叶子结点。D．在树T 中，Ｘ一定有左边
兄弟。
分析：该题目主要考查树和二叉树的转换。根据树和二叉树转换的规则可
以得到D 为正确答案。
3．一棵三叉树中，已知度为3 的结点数等于度为2 的结点数，且树中叶结
点的数目为13，则度为2 的结点数目为____________。
A．4 B．2 C．3 D．5
分析：该题目主要考查多叉树逻辑结构的特点。根据选择题第1 小题的思
路，有n0+n1+n2+n3=n，n-1=n1+2n2+3n3，n0、n1、n2、n3 分别为度是0，1，2，3 的结点数，n 为树的结点总数。在本题中，n0=13，n2=n3。正确答案为A。4．设n、m 为一棵二叉树上的两个结点，在中序遍历时，n 在m 之前的条件
是____________。
A．n 在m 右方B．n 是m 祖先C．n 在m 左方D．n 是m 子
孙
分析：该题目主要考查二叉树的遍历。根据二叉树的形态和中序遍历算法，
当n 在m 左边时，结点n 首先被遍历。当n 是m 祖先时，它们之间的关系
无法确定，不妨假设n 是根结点，m 是其左孩子，则m 在n 之前；m 是其右
孩子，则n 在m 之前。正确答案为C。
5．对一个满二叉树，m 个树枝，n 个结点，深度为h，则____________。
A．n=h+m B．h+m=2n C．m=h-1 D．n=2 h -1
分析：该题目主要考查满二叉树的定义，根据满二叉树定义，正确答案为D。6．一棵有n 个结点的k 叉树，树中所有结点的度之和为____________。
A．n-1 B．kn C．n 2 D．2n
分析：该题目主要考查树的结点和度之间的关系。由树的度的定义可知结
点的度即为与之相连的子结点的个数，而只有根结点不是连在其他的结点
上，所以和为n-1。答案为A。
7．以二叉链表作为二叉树的存储结构，在有n 个结点的二叉链表中(n>0)，
链表中空链域的个数为____________。
A．2n-1 B．n-1 C．n+1 D．2n+1
分析：该题目主要考查二叉树的链式存储结构。每个结点共有两个链域，
即共有2n 个链域，n 个结点构成的二叉树中至少有n-1 个链接指针才能将
n 个结点连接在一起，即已经用去n-1 个指针域，则空链域为2n-(n-1)=n+1 个。答案为C。
8．设森林中有3 棵树，其中第1、第2 和第3 棵树的结点个数分别为n1、n2 、n3 ，则与森林对应的二叉树中根结点的右子树上的结点个数是
____________。
A．n1 B．n1+ n2 C．n3 D．n2+n3
分析：该题目主要考查森林和二叉树之间的转换关系。森林中的第一棵树
对应于二叉树根结点及其左子树，第2 和第 3 棵树对应于二叉树中根结点
的右子树，则其结点个数为n2+n3。答案为D。
9．将含有150 个结点的完全二叉树从根这一层开始，每一层从左到右依次
对结点进行编号，根结点的编号为1，则编号为69 的结点的双亲结点的编
号为____________。
A．33 B．34 C．35 D．36
分析：该题目主要考查完全二叉树的逻辑结构。由二叉树的性质5 可知，
结点69 的双亲结点编号为。所以答案为B。
10．在一棵二叉树结点的先序序列、中序序列、后序序列中，所有叶子结
点的先后顺序__________。
A．都不相同B．先序和中序相同，而与后序不同
C．完全相同D．中序和后序相同，而与先序不同
分析：该题目主要考查二叉树的遍历。无论哪种遍历所得的序列都是在“左”、“右”两结点的空隙中插入“根”结点的排列，即左、右结点的顺序固定不变，改变的是“根”结点，叶子结点的先后顺序都不变。答案为C。11．如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径
长度最小，则该树称为____________。
A．哈夫曼树B．平衡二叉树C．二叉树D．完全二叉树
分析：该题目主要考查哈夫曼树的定义。利用哈夫曼树算法构造出的具有
最小带权外部路径长度的扩充二叉树，所构造的二叉树对于给定的权值，
带权路径长度最小。答案为A。
12．树的先根序列和其对应的二叉树的
是一样的，树的后根序列和
其对应的二叉树的
是一样的。
A．先序序列B．中序序列C．后序序列D．按层次遍历序
列
分析：该题目主要考查树和二叉树的转换关系。考虑树的根结点及其n 个
子树，当转换为二叉树后，根结点和最左子树的根结点的位置不变,而其它
子树的根结点都成为其相邻左子树根结点的右孩子。这样的转换是递归过
程。观察这样的结构变化，得到答案为A，B。
13．若一个具有N 个顶点，K 条边的无向图是一个森林(N>K),则该森林中必
有_____棵树。
A．K B．N C．N-K D．1
分析：该题目主要考查森林的概念，树的顶点和边的关系。设此森林中有m
棵树，每棵树具有的顶点数为vi (1≤i≤m)，则
v1+v2+…+vm=N (1)
(v1-1)+(v2-1)+…+(vm-1)=K (2)
(1)-(2)得：m=N-K。所以答案是C。
14．欲实现任意二叉树的后序遍历的非递归算法而不必使用栈结构，最佳
方案是二叉树采用___________存储结构。
A．三叉链表B．广义表C．二叉链表D．顺序
分析：该题目主要考查二叉树的存储结构和非递归遍历算法。此题答案为A。三叉链表是将双亲表示法和孩子兄弟表示法结合起来，既能方便地从双亲
查找孩子，又能方便地从孩子查找双亲。
15．一棵二叉树满足下列条件：对任一结点，若存在左、右子树，则其值
都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采
用___________遍历方式就可以得到这棵二又树上所有结点的递减序列。
A．先序B．中序C．后序D．层次
分析：该题目主要考查二叉树的遍历。由于中序遍历的顺序是先中序遍历
左子树，再访问根结点，最后中序遍历右子树。这样可以保证，对任一结
点其左孩子总在它的左边，其右孩子总在它的右边。当二叉树满足题述条
件时，其中序序列一定是个递减序列。答案为B。
16．对含有___________个结点的非空二叉树，采用任何一种遍历方式，其
结点访问序列均相同。
A．0 B．1 C．2 D．不存在这样的二叉树
分析：该题目主要考查二叉树的三种遍历次序的关系。三种遍历方式的不
同点，在于访问根结点的时机不同。当一棵二叉树仅含一个根结点时，不
管采用哪种遍历方式，所得到的结点序列总是相同的。此题答案为B。
17．对___________进行相应的遍历仍需要栈的支持。
A．先序线索树B．中序线索树
C．后序线索树D．A 与B
分析：该题目主要考查线索树的遍历。由于后序
遍历先访问子树后访问根结点，从本质上要求运
行栈中存放祖先的信息，即使对二叉树进行后序
线索化，仍然不能脱离栈的支持对此二叉树进行
遍历，比如图6.3 所示的后序线索树，没有栈的支持就无法对其进行后序
遍历。
当访问到结点②时，由于没有线索指向②的后序后继③，而且没有指
图6.3后序线索树
针返回到②的父结点④，因此对此二叉线索树的后序遍历无法进行，除非
使用栈。
然而对于先序线索树进行先序遍历或者中序线索树进行中序遍历，则
可以不使用栈就能够遍历，值得提到的是中序线索树，又称为对称线索树，
对它不仅可以方便地进行中序遍历，而且能够在没有栈的支持的情况下，
对其进行先序和后序遍历。所以答案为C。
18．已知n 个结点的二叉树具有最小路径长度时，其深度为k，那么第k 层上的结点数为________。
A. n-2 k-2 +1
B. n-2 k-1 +1
C. n-2 k +1
D. n-2 k-1
分析：该题目主要考查二叉树的形态和最小路径长度的关系。结点数确定
的二叉树具有最小路径长度时，形态上类似于完全二叉树，最大层次k 上
的结点任意分布，其它k-1 层上的结点构成了一个满二叉树。所以可以根
据二叉树的性质2，得到从 1 层到k-1 层上的结点总数为2 k-1 -1，从而第k 层上的结点数为n-2 k-1 +1。答案为B。
二．判断题
1．按中序遍历二叉树时，某个结点(有右子树)的直接后继是它的右子树中
第一个被访问的结点。
正确
分析：该题目主要考查二叉树的中序遍历。这种说法正确。因为中序遍历
按LDR 的顺序进行，若以某结点为其直接后继，必须是右子树中第一个被
访问的结点。
2．有1 个以上结点的二叉树，已知先序和后序遍历序列，能唯一确定一棵
二叉树。
错误
分析：该题目主要考查二叉树的遍历的性质。这种说法不正确。如已知先
序为12，后序遍历为21，则可以有两棵二叉树。
图6.4
两个不同的二叉树
3．完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。
正确
分析：该题目主要考查完全二叉树的逻辑结构。深度为k 的，有n 个结点
的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1 到n 的结点一一对应时，称为完全二叉树。根据此定义，若完全二叉树中某结
点无左孩子，则其必定没有右孩子，因此是叶结点。所以这种说法是正确
的。
4．将一棵树转换成二叉树后，根结点没有左子树。
错误
分析：该题目主要考查树和二叉树的转换。树转换成二叉树满足“左孩子，
右兄弟”规则。只有当树结点个数为1 时，树转换成二叉树后，根结点没
有左子树。
6．用二叉树的先序遍历和中序遍历可以导出二叉树的后序遍历。
正确
分析：该题目主要考查二叉树的遍历和逻辑结构。用二叉树的先序遍历和
中序遍历可以确定二叉树的逻辑结构，就可以进一步导出二叉树的后序遍
历。通常已知二叉树的先序遍历和后序遍历，无法确定一棵二叉树。
7．若一个叶子结点是某二叉树中序遍历序列的最后一个结点，那么它也是
该二叉树的先序遍历序列的最后一个结点。
正确
分析：该题目主要考查二叉树的遍历。当一个叶子结点是某二叉树中序遍
历的最后一个结点，则它一定位于二叉树的右子树上最右端，无论先序遍
历或中序遍历，右子树上的最右端的叶子结点肯定最后访问。若题目中的
叶子结点替换成普通结点，则命题不成立。
三．填空题
1．森林T 转化为二叉树B，B 中某结点在森林中为叶子结点的条件为
___________。
答案：B 中左子树为空的结点
分析：该题目主要考查森林和二叉树的转化。当B 中左子树为空时，意味
着该结点没有孩子结点。
2．N 个结点的二叉树按某种遍历规则对结点从1 到N 依次递增编号，如果(1) 任一结点的编号等于它的左子树中的最小编号减1，则为
___________遍历；
(2) 某结点右子树中最小编号等于左子树中的最大编号加1，则为
___________遍历。
答案：先序，后序。
分析：该题目主要考查二叉树的结构和遍历。对于先序遍历，因为首先访
问根结点，再先序遍历左子树，最后先序遍历右子树，所以根结点编号等
于左子树的根结点编号减1。对于后序遍历，因为首先后序遍历左子树，然
后后序遍历右子树，最后访问根结点，所以右子树中最小编号等于左子树
中的最大编号加1。
3．一棵高度为H 的满K 叉树，按层次从1 开始编号，则；
(1) 第i 层结点的数目为：___________；
(2) 编号为n 的结点的父结点的编号为：___________；
(3) 编号为n 的结点的第i 个孩子的编号为：___________；
(4) 编号为n 的结点有右兄弟的条件是：___________，右兄弟的编号
为____________。
答案：(1)K i---1)+1+i (4)n≤-
*K
n+1
分析：该题目主要考查对二叉树定义和性质的理解。对满K 叉树的而言，
它与二叉树的基本性质是相同的，区别是K 值，当K=2 时，K 叉树为二叉树。结合二叉树性质，通过归纳，可以得到上述答案。
4．如果某二叉树中有30 个叶结点，另有30 个结点仅有一个孩子结点，则
该二叉树中共有___________个结点。
答案：89
分析：该题目主要考查二叉树结点之间的关系。设i、j、k 分别为二叉树
中度为0、1、2 的结点数目，则n=i+j+k。根据二叉树的性质，i=k+1，有
n=i+j+i-1=30+30+30-1=89，所以二叉树中有个89 结点。
5．由带权为3，9，6，2，5 的5 个叶子结点构成一棵哈夫曼树，则带权路
径长度为_______。
答案：55
分析：该题目主要考查哈夫曼树的概念。解本题的关键是建立这5 个叶子
结点的哈夫曼树。
6．设F 是一个森林，B 是由F 转换得到的二叉树，F 中有n 个非终端结点，
则B 中右指针域空的结点有_____个。
答案：n+1
分析：该题目主要考查森林和二叉树的转化。
7．设n 为哈夫曼树的叶子结点数目，则该哈夫曼树共有___________个结
点。
答案：2n－1
分析：该题目主要考查哈夫曼树的结构。哈夫曼树虽然带有权值，但其形
式仍然是一棵普通的二叉树，二叉树的性质仍然适用于它。不过哈夫曼树
中没有单分支结点，它只有双分支结点和叶结点，因此，由二叉树的性质
可得出一个推论：N＝
1
2n
。其中，N 表示哈夫曼树的结点总数，
n
表示哈夫
曼树中的叶结点数。因此正确答案为
1
2n
。
8．n 个结点的完全二叉树，编号最大的非叶结点是___________号结点，编
号最小的叶结点是___________号结点。
答案：
分析：该题目主要考查完全二叉树的结构。n 个结点的完全二叉树，编号最
大的叶结点就是n 号结点，它的双亲结点就是编号最大的非叶结点。根据
完全二叉树的性质，n 的双亲为。编号最大的非叶结点的右边一个结
点，即号结点，是编号最小的叶结点。
9．完全二叉树的第7 层有8 个结点，则此完全二叉树的叶子结点数为____。768 个结点的完全二叉树有____个叶子结点？19 个结点的哈夫曼树有
______个叶子结点？
答案：36 386 10
分析：本题主要考查完全二叉树和哈夫曼树的结构。由性质1 可知：第7
层上最多有2 7-1 =64 个结点。因此，该完全二叉树的第7 层上有64-8=56 个
空子树。第7 层一定是最高层。这样，它共有56/2+8=36 个叶子结点。
n 个结点完全二叉树的叶子结点数为，768/2=386 个叶子结点。
19 个结点的哈夫曼树有叶子结点n0, 满足n＝2n0-1，可得叶子结点数为
10。
四．应用题
1．设一棵度为k 的树中有n1 个度为1 的结点，n2 个度为2 的结点，…，nk 个度为k 的结点，求该树上有多少叶子结点？
分析与解答：该题目主要考查树的基本概念和结构。
根据两个等式：求结点总数：n=n0+n1+n2+…+nk
求树枝总数：n-1= n1+2n2+…+knk
因此，0 n =1+ 2 n +2 3 n +… +(k-
2 i i ] n ) 1 i [(
2．将图6.5 所示的树转换为二叉树。
分析与解答：该题目主要考查树和二叉树的转化。
如图6.6(a,b,c)所示。
图6.6
3．满足下列条件的非空二叉树具有什么形状？
(1) 先序和中序相同；
(2) 中序和后序相同；○L ○I ○F ○G ○H ○J ○A
○C ○ D ○B ○E
○K ○M
图6.5树
○L ○I ○ F ○G ○H ○J ○A
○C ○ D ○B ○E
○K ○M
(a) 加线后
(b) 抹线后○L
○I ○F ○G ○H ○J ○ A
○C ○ D ○B ○E
○K ○M
○A
○C ○ B
○D
○
F
○K ○G ○ E
○M ○L ○H
○J ○I
(c) 旋转后
(3) 先序和后序相同；
分析与解答：该题目主要考查二叉树的结构和遍历的性质。
(1) 先序和中序相同：只有一个结点或没有左子树的二叉树(右单支树)；
(2) 中序和后序相同：只有一个结点或没有右子树的二叉树(左单支树)；
(3) 先序和中序相同：只有一个结点的二叉树。
4．已知二叉树左右子树都含有m 个结点，当m=3 时，试构造满足如下要求的所有二叉树。
(1) 左右子树的先序与中序序列相同。
(2) 左子树的中序与后序序列相同，右子树的先序与中序序列相同。
分析与解答：该题目由上题引申得到，主要考查二叉树的结构和遍历的性质，如图6.7 所示。
(1) (2)
图6.7
5．试证明：任一棵高度为h>1 的二叉树，其内部结点(除根、叶子之外的结点)的数目小于2 h-1 -1，而叶子结点数目小于或等于2 h-1 。
分析与解答：该题目主要考查二叉树的逻辑结构。
性质2：n≤2 h -1，即n0+n1+n2≤2 h -1 (a)
性质3：n0=n2+1 (b)
考查高度为h 时结点最多的二叉树——满二叉树：其n1=0。这样，(a)
式简化为：
n0+n2≤2 h -1 (c)
由(b)和(c)，可求得：n0≤2 h-1 ，n2≤2 h-1 -1(n2 中包含一个根结点)，因此，对于高度为h(>1)的任意二叉树，叶结点的数目n0≤2 h-1 (满二叉树时取等号)；而内部结点的数目=n1+n2-1≤2 h-1 -1+(n1-1)<2 h-1 -1。
6．一棵有11个结点的二叉树的存储情况如图6.8所示，Left[i]和Right[i]
分别为i 结点左、右孩子，根结点为序号3 的结点。画出该二叉树并给出先序、中序和后序遍历该树的结点序列。
1 2 3 4 5 6 7 8 9 10 11
6 ∧
7 ∧
8 ∧5 ∧2 ∧∧Left[i]
m f a k b l c r d s e Data[i]
∧∧9 ∧10 4 11 ∧ 1 ∧∧Right[i]
图6.8 二叉树的存储情况
分析与解答：该题目主要考查二叉树的静态链表存储结构以及二叉树的性
质5。该二叉树的表示如图 6.9 所示。其各种遍历如下：
先序遍历：acbrsedfmlk
中序遍历：rbsceafdlkm
后序遍历：rsbecfklmda
图6.9
7．二叉树结点数值采用顺序存储结构，如图6.10 所示。
图6.10 顺序存储结构的二叉树
(1)画出二叉树表示；1 2 3 4 5 6 7 8 9 1
0 1
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 20
e a
f d
g c j
h
i b
○c ○a
○b ○ d
○r ○l ○s ○ e ○m ○ f
○k
(2)写出先序遍历，中序遍历和后序遍历的结果；
(3)写出结点值c 的父结点，其左、右孩子；
(4)画出把此二叉树和还原成森林的图。
分析与解答：该题目主要考查二叉树的顺序存储结构(即将二叉树看成完全
二叉树)和遍历，着重考察二叉树的性质5。
(1)该二叉树如图6.11 所示。
图6.11
(2)本题二叉树的各种遍历结果如下：
先序遍历：eadcbjfghi
中序遍历：abcdjefhgi
后序遍历：bcjdahigfa
(3)根据二叉树的性质5 可知，指点值为c 的存储位置为10，故其父结点的位置为10/2=5，其父结点值为d；同样，其左孩子的存储位置为2*10=20，值为b，而右孩子的存储位置为2*10+1=21，值为空，则没有右孩子。(4)还原成的森林如图6.12 所示。
图6.12 图6.11 所对应的森林
8．对如图6.13 所示的森林：
○e
○a ○ f
○d
○g
○c
○j
○h
○i
○b
○f ○i ○ e
○a
○b ○j ○ d
○c
○h ○g
(1)求各树的先根序列和后根序列。
(2)求森林的前序序列和后序序列。
(3)将此森林转换为相应的二叉树。
(4)给出(a)所示树的双亲表示法、孩子表示法及孩子兄弟表示法等3 种存
储结构，并指出哪些存储结构易于求祖先，哪些易于求指定结点的后代？
分析与解答：该题目主要考查树和森林的遍历，森林和二叉树的转换。(1) 各树的先根序列和后根序列，如表6-1 所示。
表6-1
树a b c
先根序列ABCDEF GHIJK LMPQRNO
后根序列BDEFCA IJKHG QRPMNOL
(2) 森林的前序序列和后序序列。
前序序列：ABCDEFGHIJKLMPQRNO
后序序列：BDEFCAIJKHGQRPMNOL
(3) 森林所对应的二叉树如图6.14 所示。
将森林转换为二叉树的方法：各树的根互为兄弟，设左边的孩子为长子；然后从最左边的树开始，按长子为左孩子、右邻兄弟为右孩子的方法转换。○A
○B ○ C
○F ○E ○D
(a) ○G
○K ○J ○H
○I
(b) ○L
○R ○Q
○
P
○O ○N ○M
(c)
图
6.13
(4) ①孩子表示法、双亲表示法、孩子兄弟表示法分别如图6.15(a,b,c)
所示。
(a) (b) data parent
1 A 0
2 B 1
3 C 1
4 D 3
5 E 3
6 F 3
○
A
○L
○
H
○
F
○
C
○
G ○B
○
K
○
D
○
J
○
I
○
N
○
R
○
E
○
M
○Q
○
P
○
O
图6.14 由森林转换得到的二叉树
data child
1 A
2 B ∧
3 C
4 D ∧
5 E ∧
6 F ∧
2
5
4
3 ∧
6 ∧
∧B
A ∧
∧E
∧D
C ∧
∧F ∧
(c)
图6.15
双亲表示法易于求祖先。孩子表示法、孩子兄弟表示法易于求后代。
9．设二叉树的存储结构如图6.16 所示，其中bt 为二叉树的根指针，lchild，rchild 分别为左右孩子的指针域，data 为结点的数据域(存放结点本身的
信息)。请完成下列各步：
(1) 画出二叉树的树形结构。
(2) 画出该二叉树的后序线索化二叉树。
分析与解答：该题目主要考查二叉树的存储结构及线索化。
(1) 该二叉树的树形结构图，如图6.17(a)所示。
图6.16 二叉树静态链表结构
(2) 后序线索化二叉树如图6.17(b)所示。
(a) 对应的二叉树(b)后序线索化1 2 3 4 5 6 7 8 9 10
lchild 0 0 2 3 7 5 8 0 10 1
data j h f d b a c e g i
rchild 0 0 0 9 4 0 0 0 0 0
bt
○a
○b
○f ○d
○e ○c
○h ○g
○j ○i
图6.17 第9 题解答
10．设电文由6 个字符A，B，C，D，E，F 组成，它们在电文中出现的次数分别为：10,4,8,3，2,7。试画出用于编码的哈夫曼树，并列出每个字符的
编码。
分析与解答：该题目主要考查哈夫曼树及应用。对应的哈夫曼树如图6.18
所示：
图6.18
对应的哈夫曼编码为A(10)：11 B(4)：100 C(8)：01
D(3)：1011 E(2)：1010 F(7)：00
11．如图6.19 所示的哈夫曼树可得到字母F,G,H,I 和J 的编码，
(1)设某字母串经编码后为“1”，译出原串，
(2)说明哈夫曼编码和ASCII 编码的异同。
(3)为什么采用哈夫曼编码？
分析与解答：该题目主要考查哈夫曼树及应用。
(1) 根据图6.19，可以得到原串是GIHJG。
(2) 相同点：都是用0、1 代码来表示字母或数字。图6.19
不同点：不同的哈夫曼编码代表一个字母的位数不固定，哈夫曼编码
是前缀编码；ASCII 码是8 位表示的固定长度的编码。
(3) 采用哈夫曼编
○2 ○34
○19
○8 ○7 ○15
○4 ○10 ○9
○3 ○5
0 0 1
1 1
0 1
F G H
I J
码能提高编码效率，也能提高存储和传输效率。
12．已知二叉树的存储结构为二叉链表，阅读下面算法。
typedef struct node {
DateType data;
struct node *next;
}ListNode;
typedef ListNode *LinkList;
LinkList Leafhead=NULL;
void Inorder(BTree T)
{ LinkList s;
if (T)
{ Inorder(T->lchild); 图6.20
if ((!T->lchild ) && (!T->rchild))
{ s=(ListNode*)malloc(sizeof(ListNode));
s->data=T->data;
s->next=Leafhead;
Leafhead=s;
}
Inorder(T->rchild);
}
}
对于如图6.20 所示的二叉树：
(1) 画出执行上述算法后所建立的结构。
(2) 说明该算法的功能。
分析与解答：该题目主要考查二叉树遍历的应用。
○E
○A
○B ○ C
○D
○H ○ F
○G
(1) 执行上述算法后所建立的结构为如图6.21 所示的链表。
图6.21
(2) 该算法的功能是用中序遍历递归算法对二叉树进行遍历，将二叉树
中叶结点数据域的值作为单链表结点的值，并用头插法建立一个以Leafhead 为头指针的逆序单链表(即按二叉树中叶结点数据从右至左链接
成一个链表)。
13．假设二叉树t 的结点有4 个字段，它们分别是：data、1child、rchild、parent，其中data 存放结点值，1child 和rchild 分别指向左子结点和右
子结点，parent 指向父结点。在下列程序中，非递归函数mid_order(t)实
现了对二叉树t 的中序遍历。
typedef struct node{
int data;
struct node *lchild, *rchild;
struct node *parent;
}Node;
void mid_order(Node *t)
{ Node *p, *q;
p=NULL; q=t;
do{
while(q!= NULL)
{
(1)
;
q=q->lchild; F
D ∧
H
G
leafhead
}
if ( (2)
)
{ printf(“%5d”, p->data);
(3)
;
}
while (p!= NULL&& q==NULL)
{
do{
q=p;
(4)
;
}while (p!= NULL&& q==p->rchild);
if (p!= NULL)
{ printf(“5%d”,p->data);
(5)
;
}
}
}while( (6)
)；
printf (“\n”);
}
分析与解答：该题目主要考查二叉树遍历的非递归算法。让p 为q 的父指
针，首先沿着二叉树的左孩子指针找到最左下角的孩子，然后判断其左子
树是否为空，不为空则遍历右子树，否则沿着parent 指针向上，直到parent 为空为止。
(1)p=q;(2)p(3)q=p->rchild(4)p=q->parent(5)q=p->rchild (6)p
14．一棵以孩子兄弟表示法存储，递归算法numberofleaf 计算并返回根为
r 的树中叶子结点的个数(NULL 代表空指针)。
typedef struct tnode {
struct tnode *firstson,*nextbrother;
}TNode;
int numberofleaf(TNode *r)
{ int num;
if(r==NULL) num=0;
else if(r->firstson==NULL)
num= (1)
+
numberrofleaf(r->nextbrother);
else (2)
;
return(num);
}
分析与解答：该题目主要考查树遍历的应用和孩子兄弟表示法存储结构。
此题要求熟悉树的孩子兄弟表示法与二叉链表的联系和区别，必须了解树
的孩子兄弟表示法中叶结点的特点。若根结点指针为空，则叶结点数目为0。只有那些firstson 为空的结点是叶结点。因而问题的答案为：
(1) 1; (2) num=numberofleaf(r->firstson)+
numberofleaf(r->nextbrother)
五．算法设计题
1．已知深度为h 的二叉树以一维数组BT[1..2 h -1]作为其存储结构。请写
一算法，求该二叉树中叶结点的个数。
分析：该题目主要考查二叉树的顺序存储结构。以二叉树对应的完全二叉
树的层次次序在数组BT 中存放二叉树的结点值，若BT[i]不为零，则完全
二叉树层次次序中第i 个位置对应的二叉树结点存在，否则，结点不存在。
在二叉树的顺序存储结构中，结点i 的左孩子(若存在)的编号为2i，右孩
子(若存在)的编号为2i+1。对于顺序存储结构的二叉树适合层次遍历。
算法描述如下：
int leafnum(int BT[ ] , int h)
{ int len,i,count;
len=pow(2,h)-1; /*获取顺序表的长度*/
count=0;
for (i=1;i<=len;i++)
if (BT[i]!=0) /*i 位置存在结点，再判断是否为叶
子结点*/
{ if (i*2>len)
/*当前结点的左孩子位置已经大于存储区长度，所以没有孩
子，必定是叶子结点*/
count++;
else if ((BT[i*2+1]==0)&&(BT[i*2]==0))/*当前结点没
有左孩子和右孩子*/
count++;
}
return(count);
}
2．设两棵二叉树的根结点地址分别为P 及Q，采用二叉链表的形式存储这二棵树上所有的结点。请编写程序，判断它们是否相似。
分析：该题目主要考查二叉树遍历算法的应用。所谓二棵二叉树s 和t 相似，要求：它们都为空或都只有一个根结点；或它们的根结点及左右子树
均相似。
依题意，本题的递归函数定义如下：
(1) 若s=t=NULL，则f(s,t)=true;
(2) 若s 与t 一个为NULL 而另一个不为
NULL，则f(s,t)=false;
(3) 若s 与t 均不为NULL ，则f
(s,t)=f(s->left , t->left)和f(s->right , t->right)的“与”运算的
结果。
算法描述如下：
int like(BTree s, BTree t)
{ int like1,like2;
if ((s==NULL) && (t==NULL)) /*都是空树，则相似*/
return (1);
else if ((s==NULL) || (t==NULL)) /*否则，只有一个为空树，另
一个不是，则不相似*/
return(0);
else /*都不是空树时*/
{ like1=like(s->lchild, t->lchild); /*判断左子树
是否相似*/
like2=like(s->rchild, t->rchild); /*判断右子树是
否相似*/
return (like1 && like2); /*左右子树都相似时，才
返回1，表示相似*/
}
}
3．设具有n 个结点的完全二叉树采用顺序结构存储在顺序表BT[1..n]中，请编写算法由该顺序存储结构建立此二叉树的二叉链表存储结构。
分析：该题目主要考查二叉树的存储结构和遍历。在完全二叉树的顺序存
储结构中，对于任意一个结点BT[k]，其左孩子为BT[2k],其左孩子为
BT[2k+1]。因此，可以从根结点BT[1]开始，按照下列递归过程逐个建立各个结点BT[k]的二叉链表的结点结构。
(1) 以BT[k]作为根结点的值，建立二叉树的
根结点root；
(2) 从BT[2k]开始，建立二叉树的左子树，
并将root 的左孩子指针指向左子树的根；
(3) 从BT[2k+1]开始，建立二叉树的右子树，
并将root 的右孩子指针指向右子树的根。
基于这个思想，可以编写算法buildbtree(BT,i,n)，其中i 为根结点元
素在顺序表BT 中的位置，n 为顺序表的长度，算法返回二叉链表的根结点指针。不失一般性，设二叉树中结点值为整型。
这个算法实际上是在对二叉树进行先序遍历过程中来逐步建立二叉链表
的每个结点。因此，该算法的结构类似于二叉树的先序遍历的递归算法，但在这里遍历的二叉树是一个采用顺序存储的完全二叉树。
算法描述如下：
BTree buildbtree(int BT[],int i,int n)
{ BTree r;
if (i>n)
return(NULL); /*位置超过存储区域，算法
结束*/
else
{
r=(BTree) malloc(sizeof (Bnode)); /*给新结点分配空间*/
r->data=BT[i]; /*获得i 位置的数
据*/
r->lchild=buildbtree(BT,2*i,n); /*建立当前结点的
左子树*/
r->rchild=buildbtree(BT,2*i+1,n); /*建立当前结点的
右子树*/
return(r);
}
}
4．编写递归算法，在二叉树中求位于先序序列中第k 位置的结点值。
分析：该题目主要考查二叉树遍历的应用，只需要对先序遍历算法进行局部改进即可。
算法描述如下：
int c ; /*计数器c 作为全局变量处理,初始
值为0*/
void Get_PreSeq(BTree T,int k) /* 先序序列为k 的结点的
值*/
{ if (T)
{ c++; /*每访问一个子树的根都会使先序序号
计数器加1*/
if (c= =k)
{ printf ("Value is %d\n",T->data);
exit (1);
}
else
{ Get_PreSeq(T->lchild,k); /*在左子树中查
找*/
Get_PreSeq(T->rchild,k); /*在右子树中查
找*/
}
}
}
5．设二叉树的存储结构为二叉链表，试写出算法，求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。
分析：该题目主要考查二叉树遍历的应用。本题采用图的深度优先遍历算
法思想，设立两个数组，其一存放已经发现的最长路径，其二存放当前的
最长路径；若当前路径长度大于已发现的路径长度，则修改已经发现的路径。另外要判断到达叶子结点的时机。
依据上述分析，本题的算法如下：
int depths(BTree T,DataType a[], int *MaxLen, DataType b[], int
*CurrentLen)
{ /*将T 中的首次发现的最长路径存放在a 中，调用前MaxLen 和CurrentLen 为0*/
if(T==NULL) /*若到达某个叶子结点,检查路径长度*/
{
if (CurrentLen>MaxLen) /*当前路径为最长路径*/
{
for (j=0;j a[j]=b[j]; /*当前路径存入a*/ MaxLen= CurrentLen; } } else { b[++CurrentLen]=T->data; /*记录当前的结点*/ depths(T->lchild, a, &MaxLen, b, &CurrentLen); depths(T->rchild, a, &MaxLen, b, &CurrentLen); CurrentLen --; /*访问了左右孩子后,返回到父结点, 所以路径长度减1*/ } } 6．已知一棵二叉树用二叉链表存储，t 指向根结点，p 指向树中任一结点，设计算法，输出从t 到p 之间路径上的结点。 分析：本题有两种方法求解，第一种方法是利用后序遍历的非递归算法， 在遍历到p 结点后，栈中保存的结点就是t 到p 之间路径上的结点。第二种方法是利用二叉树的先序遍历，但不是简单地进行先序遍历，而是仅遍 历从根结点到给定的结点p 为止，也是采用非递归算法来实现，其主要思想是： (1) 当前结点为根结点； (2) 当前结点不为空且不为p，则进栈，当前结点指向左孩子，重复此 过程，直到当前结点为p 或为空；若当前结点为p，转(4)，若当前结 点为空，转(3)； (3) 若是空栈，则没找到p，算法结束。若不是空栈，则取栈顶元素。 若栈顶元素的右孩子没有被访问过，当前结点为右孩子，转(2)；若栈 顶元素的右孩子被访问过或为空，则栈顶元素出栈，继续(3)；(4) 打印栈中数据，算法结束。 算法描述如下： /*定义栈元素的数据类型*/ typedef struct { Bnode *node; int flag; /* flag 为0 表示node 的右孩子还没有被访问，为1 表示node 的右孩子被访问*/ }DataType; void Path(BTree t, Bnode *p) { Bnode *q; PSeqStack S; /*定义一个顺序栈*/ DataType Sq; S=Init_SeqStack( ); /* 栈初始化*/ q=t; /*通过先序遍历发现p*/ while((q!= NULL||!Empty_SeqStack(S)) && q!=p)) /*扫描左孩子，且相应的结点不为p 且不为空结点*/ { if(q!= NULL) { Sq.node= q; Sq.flag=0; /*表示右孩子还没有被访问*/ Push_SeqStack(S, Sq); /*将q 指针以及flag 压入栈中*/ q=q->lchild; } else { Pop_SeqStack(S,&Sq); /*出栈，得到栈顶元素 */ q = Sq.node; if((Sq.flag==0)&&(q->rchild))/*若右孩子还没有被访 问，并且其有右孩子*/ { Sq.flag=1; /*表示右孩子已被访问 */ Push_SeqStack(S,Sq); /*再次将q 指针以及flag 压入栈中*/ q=q->rchild; } } } if(q==p) /*找到p，栈底到栈顶为t 到p 的路径*/ while (!Empty_SeqStack(S)); { Pop_SeqStack(S,&Sq); printf(Sq.node->data);/*输出路径，要根据data 域具体的 类型书写printf 语句*/ } else printf(“树中没有p 结点”); } 第六章树和二叉树 一．选择题 1. 以下说法错误的是。 A.树形结构的特点是一个结点可以有多个直接前趋 B.线性结构中的一个结点至多只有一个直接后继 C.树形结构可以表达(组织)更复杂的数据 D.树(及一切树形结构)是一种"分支层次"结构 2. 如图6-2所示的4 棵二叉树中，不是完全二叉树。 图6-2 4 棵二叉树 3. 在线索化二叉树中，t 所指结点没有左子树的充要条件是。 A. t->left == NULL B. t->ltag==1 C. t->ltag==1 且t->left==NULL D .以上都不对 4. 以下说法错误的是。 A.二叉树可以是空集 B.二叉树的任一结点最多有两棵子树 C.二叉树不是一种树 D.二叉树中任一结点的两棵子树有次序之分 5. 以下说法错误的是。 A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B.在三叉链表上，二叉树的求双亲运算很容易实现 C.在二叉链表上，求根，求左、右孩子等很容易实现 D.在二叉链表上，求双亲运算的时间性能很好 6. 如图6-3所示的4 棵二叉树，是平衡二叉树。 图6-3 4 棵二叉树 7. 如图6-4所示二叉树的中序遍历序列是。 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 图6-4 1 棵二叉树 8. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是。 A. acbed B. decab C. deabc D. cedba 9. 如果T2 是由有序树T 转换而来的二叉树，那么T 中结点的前序就是T2 中结点的。 A. 前序 B.中序 C. 后序 D. 层次序 10. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 11. 将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为。 A.42 B.40 C.21 D.20 12. 一棵二叉树如图6-5所示，其后序遍历的序列为。 A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh 习题六树和二叉树 一、单项选择题 1．以下说法错误的是（） A. 树形结构的特点是一个结点可以有多个直接前趋 B. 线性结构中的一个结点至多只有一个直接后继 C. 树形结构可以表达（组织）更复杂的数据 D. 树（及一切树形结构）是一种”分支层次”结构 E. 任何只含一个结点的集合是一棵树 2. 下列说法中正确的是（） A. 任何一棵二叉树中至少有一个结点的度为2 B. 任何一棵二叉树中每个结点的度都为2 C. 任何一棵二叉树中的度肯定等于2 D. 任何一棵二叉树中的度可以小于2 3. 讨论树、森林和二叉树的关系，目的是为了（） A. 借助二叉树上的运算方法去实现对树的一些运算 B. 将树、森林按二叉树的存储方式进行存储 C. 将树、森林转换成二叉树 D. 体现一种技巧，没有什么实际意义4．树最适合用来表示（） A. 有序数据元素 B .无序数据元素 C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B ．11 C ．15 D ．不确定 6. 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1, M2和M3与森林F 对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B ．M1+M2 C ．M3 D ．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A．250 B ．500 C ．254 D ．505 E ．以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为（） A. 不确定 B . 2n C . 2n+1 D . 2n-1 9．二叉树的第I 层上最多含有结点数为（） I I-1 I-1 I A．2I B ．2 I-1 -1 C ．2 I-1 D ．2 I -1 10．一棵二叉树高度为h, 所有结点的度或为0，或为2，则这棵二叉树最少有（）结点A．2h B ．2h-1 C ．2h+1 D ．h+1 11. 利用二叉链表存储树，则根结点的右指针是（）。 A.指向最左孩子 B .指向最右孩子 C .空D .非空 12．已知一棵二叉树的前序遍历结果为为（）。 A．CBEFDA B ．FEDCBA 13．已知某二叉树的后序遍历序列是（）。 ABCDEF中序遍历结果 为 C ．CBEDFA D dabec, 中序遍历序列是 CBAEDF则后序遍历的结 果 ．不定 debac , 它的前序遍历是 一、填空题 1. 不相交的树的聚集称之为森林。 2. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是_树可采用孩子-兄弟链表（二叉链表）做存储结构，目的是利用二叉树的已有算法解决树的有关问题。 3. 深度为k的完全二叉树至少有2 k-1个结点。至多有2 k-1个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是2 k-2+1。 4. 在一棵二叉树中，度为零的结点的个数为n ，度为2的结点的个 数为n 2，则有n = n 2 +1。 5. 一棵二叉树的第i（i≥1）层最多有2 i-1个结点；一棵有n（n>0）个结点的满二叉树共有（n+1）/2个叶子和（n-1） /2个非终端结点。 6.现有按中序遍历二叉树的结果为abc，问有5种不同形态的二叉树 可以得到这一遍历结果。 7. 哈夫曼树是带权路径长度最小的二叉树。 8. 前缀编码是指任一个字符的编码都不是另一个字符编码的前缀的一种编码方法，是设计不等长编码的前提。 9. 以给定的数据集合{4，5，6，7，10，12，18}为结点权值构造的Huffman树的加权路径长度是 165 。 10. 树被定义为连通而不具有回路的（无向）图。 11. 若一棵根树的每个结点最多只有两个孩子，且孩子又有左、右之分，次序不能颠倒，则称此根树为二叉树。 12. 高度为k，且有个结点的二叉树称为二叉树。 2k-1 满 13. 带权路径长度最小的二叉树称为最优二叉树，它又被称为树。 Huffman 14. 在一棵根树中，树根是为零的结点，而为零的结点是结点。 入度出度树叶 15. Huffman树中，结点的带权路径长度是指由到之间的路径长度与结点权值的乘积。 结点树根 16. 满二叉树是指高度为k，且有个结点的二叉树。二叉树的每一层i上，最多有个结点。 2k-1 2i-1 二、单选题 1. 具有10个叶结点的二叉树中有 (B) 个度为2的结点。 (A)8 (B)9 (C)10 (D)11 2．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用_（3）次序的遍历实现编号。 （1）先序（2）中序 （3）后序（4）从根开始按层遍历 3. 由2、3、4、7作为结点权值构造的哈夫曼树树的加权路径长度 B 。 A、33 B、30 C、36 D、40 4. 高度为6的满二叉树，总共有的结点数是 B 。 A、15 B、63 C、20 D、25 5. 下面描述根树转换成二叉树的特性中，正确的是 C 。 A、根树转换成的二叉树是唯一的，二叉树的根结点有左、右孩子。 B、根树转换成的二叉树是不唯一的，二叉树的根结点只有左孩子。 C、根树转换成的二叉树是唯一的，二叉树的根结点只有左孩子。 D、根树转换成的二叉树是不唯一的，二叉树的根结点有左、右孩子。 6. 如图所示的4棵二叉树中，不是完全二叉树的是。 A、○ B、○ ○○○○ ○○○○○○ 第６章树和二叉树习题答案 1．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。 答：树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。 树和二叉树的区别有三：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下，也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。 2．请分析线性表、树、广义表的主要结构特点，以及相互的差异与关联。 答：线性表属于约束最强的线性结构，在非空线性表中，只有一个“第一个”元素，也只有一个“最后一个”元素；除第一个元素外，每个元素有唯一前驱；除最后一个元素外，每个元素有唯一后继。树是一种层次结构，有且只有一个根结点，每个结点可以有多个子女，但只有一个双亲（根无双亲），从这个意义上说存在一（双亲）对多（子女）的关系。广义表中的元素既可以是原子，也可以是子表，子表可以为它表共享。从表中套表意义上说，广义表也是层次结构。从逻辑上讲，树和广义表均属非线性结构。但在以下意义上，又蜕变为线性结构。如度为1的树，以及广义表中的元素都是原子时。另外，广义表从元素之间的关系可看成前驱和后继，也符合线性表，但这时元素有原子，也有子表，即元素并不属于同一数据对象。 3．在二叉树的Ｌlink-Rlink存储表示中，引入“线索”的好处是什么？ 答：在二叉链表表示的二叉树中，引入线索的目的主要是便于查找结点的前驱和后继。因为若知道各结点的后继，二叉树的遍历就变成非常简单。二叉链表结构查结点的左右子女非常方便，但其前驱和后继是在遍历中形成的。为了将非线性结构二叉树的结点排成线性序列，利用结点的空链域，左链为空时用作前驱指针，右链为空时作为后继指针。再引入左右标记ltag 和rtag ，规定ltag=0，lchild 指向左子女,ltag=1时,lchild指向前驱；当rtag=0时 ,rchild指向右子女，rtag=1时，rchild 指向后继。这样，在线索二叉树（特别是中序线索二叉树）上遍历就消除了递归，也不使用栈。 4．已知一棵二叉树的中序遍历结点排列为DGBAECHIF，后序遍历结点排列为GDBEIHFCA，（1）试画出该二叉树； （2）试画出该二叉树的中序线索树； （3）试画出该二叉树对应的森林； 答： I F H E C 题（3） 第6 章树和二叉树 6.1 已知一棵树如图所示，回答下列问题： (1) 哪个是根结点? (2) 哪些是叶子结点? (3) 哪个是结点 G 的双亲? (4) 哪些是结点 G 的祖先? (5) 哪些是结点 B 的孩子? (6) 哪些是结点B的子孙? (7) 哪些是结点 E 的兄弟? (8) 结点 B 和 H 的层次号分别是什么 ? (9) 树的深度是多少? (10) 以结点 C 为根的子树的深度是多少? 【6.1 解】： (1) A (2) K, F,G,H,I,J (3) B (4) B,A (5) E,F,G (6) E,F,G,K (7) F,G (8) 2, 3 (9) 4 (10) 2 6.2 在结点个数为n(n>1)的各棵树中，最小的高度是多少？它有多少个叶结点？多少个分支结点？最大的高度树是多少？它有多少个叶结点？多少个分去结点？【6.2解】结点个数为n时，高度最小的树高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1，有n层；它有1个叶结点，n-1个分支结点。 6.3简述树与二叉树的区别？【6.3解】二叉树的度最大为2，而树的度可以大于2； 二叉树的每个结点的孩子有左、右之分，而树中结点的孩 子无左右之分。 6.4 n(n>1)个结点的各棵二叉树中，最小的高度（h≥1）多少？最大的高度是多少？【6.4解】最小高度为：??n2 log+1,此时树为完全二叉树；最大高度为n，比如一棵斜二叉树。 6.5如果一棵树有n1个度为1的结点，有n2个度为2的结点，…，n m个度为m的结点，试问有多少个度为0的结点？试推导之。【6.5解】 设叶子结点数为n0，则树中结点数和总度数分别为: 结点数=n0+n1+n2+...+n m 总度数=n1+2n2+...+m×n m 结点数等于总度数加1，所以得到：n0=∑ = + - m i i n i 2 1 ) )1 ( ( 6.6如果已知一棵二叉树有20个叶子结点，有10个结点仅有左孩子，15个结点仅有右孩子，求出该二叉树的结点数目。【解】由题知：n0=20，n1=10+15=25 n2=n0-1=19，∴ n=n0+n1+n2=64 6.7 已知某完全二叉树有100个结点，试 用三种不同的方法求出该二叉树的叶子结 点数。 【解】50 6.8已知一棵具有n个结点的完全二叉树被顺序存储于一维数组T[n+1]中(从1号单元开始顺序存放结点)，试编定个算法打印编号为i的结点的双亲和所有子女。【6.8解】 template 第六章树和二叉树 一、选择题 1.在线索化二叉树中,t所指结点没有左子树的充要条件是（） （A）t-〉left==NULL （B）t-〉ltag==1 （C）t-〉ltag=1且t-〉left=NULL（D）以上都不对 参考答案：B 2.二叉树按某种顺序线索化后,任一结点均有指向其前趋和后继的线索,这种说法 （A）正确（B）错误（C）不同情况下答案不确定 参考答案：B 3.二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法（） (A)正确 (B)错误（C）不同情况下答案不确定 参考答案：A 4.由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树,这种说法（） （A）正确（B）错误（C）不同情况下答案不确定 参考答案：B 5.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为（）。 （A）2h （B）2h-1（C）2h+1（D）h+1 参考答案：B 6.已知某二叉树的后序遍历序列是dabec。中序遍历序列是debac,它的前序遍历序列是（）。 （A）acbed （B）decab（C）deabc （D）cedba 参考答案：D 7.如果T2是由有序树T转换而来的二叉树,那么T中结点的前序就是T2中结点的（） （A）前序（B）中序（C）后序（D）层次序 参考答案：A 8.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是（）。 （A）bdgcefha （B）gdbecfha （C）bdgaechf （D）gdbehfca 参考答案：D 9.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（） （A）正确（B）错误（C）不同情况下答案不确定 参考答案：B 10.按照二叉树的定义,具有3个结点的二叉树有（）种。 （A）3（B）4（C）5（D）6 参考答案：C 11.在一非空二叉树的中序遍历序列中,根结点的右边（） （A）只有右子树上的所有结点（B）只有右子树上的部分结点 （C）只有左子树上的部分结点（D）只有左子树上的所有结点 参考答案：A 12.树最适合用来表示（）。 （A）有序数据元素（B）无序数据元素 （C）元素之间具有分支层次关系的数据（D）元素之间无联系的数据 参考答案：C 13.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（） （A）不发生改变（B）发生改变（C）不能确定D.以上都不对 参考答案：A 14.实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最佳方案是二叉树采用（）存储结构。 （A）二叉链表（B）广义表存储结构（C）三叉链表（D）顺序存储结构 参考答案：C 15.对一个满二叉树,m个树叶,n个结点,深度为h,则（） （A）n=h+m （B）h+m=2n（C）m=h-1（D）n=2h-1 参考答案：D 16.如果某二叉树的前序为stuwv,中序为uwtvs,那么该二叉树的后序为（） （A）uwvts （B）vwuts（C）wuvts （D）wutsv 参考答案：C 第六章树与二叉树 一．选择题 1．下面关于二叉树的结论正确的是____________。 A．二叉树中，度为0 的结点个数等于度为2 的结点个数加1。 B．二叉树中结点个数必大于0。 C．完全二叉树中，任何一个结点的度，或者为0，或者为2。 D．二叉树的度是2。 分析：该题目主要考查二叉树逻辑结构的特点。正确答案为A。二叉树中叶 子结点的个数为n0 ，度为 2 的结点的个数为n2，度为1 的结点个数为n1， 树中结点总数为n，则n= n0+ n2+ n1。除根节点没有双亲外，每个结点都有 且仅有一个双亲，所以有n-1= n1+ 2n2 作为孩子的结点，因此有n0= n2+1。 二叉树中结点个数可以为0，称为空树，所以B 错。满二叉树中，任何一个 结点的度，或者为0，或者为2。完全二叉树中，任何一个结点的度，或者 为0，或者为1，或者为2。所以C 错。二叉树的度可以是0、1、2。所以D 错。 2．设X 是树T 中的一个非根结点，B 是T 所对应得二叉树，在B 中，X 是 其双亲的右孩子，下列结论正确的是____________。 A．在树T 中，Ｘ是其双亲的第一个孩子。B．在树T 中，Ｘ一定无右边 兄弟。 C．在树T 中，Ｘ一定是叶子结点。D．在树T 中，Ｘ一定有左边 兄弟。 分析：该题目主要考查树和二叉树的转换。根据树和二叉树转换的规则可 以得到D 为正确答案。 3．一棵三叉树中，已知度为3 的结点数等于度为2 的结点数，且树中叶结 点的数目为13，则度为2 的结点数目为____________。 A．4 B．2 C．3 D．5 分析：该题目主要考查多叉树逻辑结构的特点。根据选择题第1 小题的思 路，有n0+n1+n2+n3=n，n-1=n1+2n2+3n3，n0、n1、n2、n3 分别为度是0，1，2，3 的结点数，n 为树的结点总数。在本题中，n0=13，n2=n3。正确答案为A。4．设n、m 为一棵二叉树上的两个结点，在中序遍历时，n 在m 之前的条件 是____________。 A．n 在m 右方B．n 是m 祖先C．n 在m 左方D．n 是m 子 孙 分析：该题目主要考查二叉树的遍历。根据二叉树的形态和中序遍历算法， 当n 在m 左边时，结点n 首先被遍历。当n 是m 祖先时，它们之间的关系 无法确定，不妨假设n 是根结点，m 是其左孩子，则m 在n 之前；m 是其右 孩子，则n 在m 之前。正确答案为C。 5．对一个满二叉树，m 个树枝，n 个结点，深度为h，则____________。 A．n=h+m B．h+m=2n C．m=h-1 D．n=2 h -1 分析：该题目主要考查满二叉树的定义，根据满二叉树定义，正确答案为D。6．一棵有n 个结点的k 叉树，树中所有结点的度之和为____________。 A．n-1 B．kn C．n 2 D．2n 分析：该题目主要考查树的结点和度之间的关系。由树的度的定义可知结 E F D G A B / + + * - C * 第六章 树和二叉树 一、选择题 1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( D ) A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE 2. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ C ） A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 3. 在下述结论中，正确的是（ D ） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右 子树可任意交换; ④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A ．①②③ B ．②③④ C ．②④ D ．①④ 4. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ A ） A ．m-n B ．m-n-1 C ．n+1 D ．条件不足，无法确定 5．设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F 对应的二叉树根结点的右子树上的结点个数是（ D ）。 A ．M1 B ．M1+M2 C ．M3 D ．M2+M3 6. 设给定权值总数有n 个，其哈夫曼树的结点总数为( D ) A ．不确定 B ．2n C ．2n+1 D ．2n-1 7．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( B )结点 A ．2h B ．2h-1 C ．2h+1 D ．h+1 8. 一棵具有 n 个结点的完全二叉树的树高度（深度）是（ A ） A ．?logn ?+1 B ．logn+1 C ．?logn ? D ．logn-1 9．深度为h 的满m 叉树的第k 层有（ A ）个结点。(1= 第六章课后习题 6、1、各层的结点数目是：K 2、编号为n的结点的双亲结点是：<=(n-2)/k的最大整数 3、编号为n的结点的第i个孩子结点编号是：k*(n-1)+1+i 4、编号为n的结点有右兄弟的条件是：(n-1)能被k整除 右兄弟的编号是：n+1. 7、1、先序序列和中序序列相同：空二叉树或没有左子树的二叉树。 2、中序序列和后序序列相同：空二叉树或没有右子树的二叉树。 3、先序序列和后序序列相同：空二叉树或只有根的二叉树。 9、中序序列：BDCEAFHG和后序序列：DECBHGFA的二叉树为： A B F C G D E H 先序序列：ABCDEFGH 算法设计： 3、typedef struct { int data[100]; int top; }seqstack; seqstack *s; Perorder(char a[],int n) { int i=1,count=1; s->top=-1; if(n==0)return(0); else { if(I<=n) { s->top++; s->data[s->top]=a[I]; } while(count 第6章 树和二叉树（参考答案） 6.1 (1)根结点a 6.2 三个结点的树的形态： 三个结点的二叉树的形态： （1） （1） （2） （4） （5） 6．3 设树的结点数是n ，则 n=n0+n1+n2+……+nm+ (1) 设树的分支数为B ，有 n=B+1 n=1n1+2n2+……+mnm+1 (2) 由（1）和（2）有： n0=n2+2n3+……+(m-1)nm+1 6.4 (1) k i-1 (i 为层数) (2) (n-2)/k+1 (3) (n-1)*k+i+1 (4) (n-1)%k !=0; 其右兄弟的编号 n+1 6.5（1）顺序存储结构 注：#为空结点 6.6 (1) 前序 ABDGCEFH (2) 中序 DGBAECHF (3) 后序 GDBEHFCA 6.7 (1) 空二叉树或任何结点均无左子树的非空二叉树 (2) 空二叉树或任何结点均无右子树的非空二叉树 (3) 空二叉树或只有根结点的二叉树 6.8 int height(bitree bt) // bt是以二叉链表为存储结构的二叉树，本算法求二叉树bt的高度 { int bl,br; // 局部变量，分别表示二叉树左、右子树的高度 if (bt==null) return(0); else { bl=height(bt->lchild); br=height(bt->rchild); return(bl>br? bl+1: br+1); // 左右子树高度的大者加1（根） } }// 算法结束 6.9 void preorder(cbt[],int n,int i); // cbt是以完全二叉树形式存储的n个结点的二叉树，i是数 // 组下标，初始调用时为1。本算法以非递归形式前序遍历该二叉树 { int i=1,s[],top=0; // s是栈，栈中元素是二叉树结点在cbt中的序号 // top是栈顶指针，栈空时top=0 if (n<=0) { printf(“输入错误”);exit（0）；} while (i<=n ||top>0) { while(i<=n) {visit(cbt[i]); // 访问根结点 if (2*i+1<=n) s[++top]=2*i+1; //若右子树非空，其编号进栈 i=2*i;// 先序访问左子树 } if (top>0) i=s[top--]; // 退栈，先序访问右子树 } // END OF while (i<=n ||top>0) }// 算法结束 //以下是非完全二叉树顺序存储时的递归遍历算法，“虚结点”用‘*’表示void preorder(bt[],int n,int i); // bt是以完全二叉树形式存储的一维数组，n是数组元素个数。i是数 // 组下标，初始调用时为1。 { if (i<=n && bt[i]!=’*’) { visit(bt[i]); preorder(bt,n,2*i); preorder(bt,n,2*i+1); }// 算法结束 6.10 int equal(bitree T1,bitree T2); // T1和T2是两棵二叉树，本算法判断T1和T2是否等价 // T1和T2都是空二叉树则等价 // T1和T2只有一棵为空，另一棵非空，则不等价 // T1和T2均非空，且根结点值相等，则比较其左、右子树 第6章树和二叉树 一、选择题 1. 在下述结论中，正确的是（） ①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④ 2．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个 A．4 B．5 C．6 D．7 3．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A． 250 B． 500 C．254 D．505 E．以上答案都不对 4. 一个具有1025个结点的二叉树的高h为（） A．11 B．10 C．11至1025之间 D．10至1024之间 5．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。 A．前序 B．中序 C．后序 D．按层次 6．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。A．CBEFDA B． FEDCBA C． CBEDFA D．不定 7．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树8．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（） A．都不相同B．完全相同 C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同 二、判断题 1. 二叉树是度为2的有序树。 2. 完全二叉树一定存在度为1的结点。 3．用树的前序遍历和中序遍历可以导出树的后序遍历。 4．由一棵二叉树的前序序列和后序序列可以唯一确定它。 5．完全二叉树中，若一个结点没有左孩子，则它必是树叶。 三、填空题 1．在二叉树中，指针p所指结点为叶子结点的条件是___ ___。15．设只含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为__ ____,最小结点数为___ ___。 2．高度为8的完全二叉树至少有_____ _个叶子结点。 3．一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是(1) _；编号是i的结点所在的层次号是(2) __（根所在的层次号规定为1层）。 4．由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。 #define MAX 100 typedef struct Node {char info; struct Node *llink, *rlink; }TNODE; 第6章树和二叉树答案 一、选择题 1、已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( D ) A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 2、算术表达式a+b*（c+d/e）转为后缀表达式后为（ B ） A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++ 3.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ D ） A．5 B．6 C．7 D．8 4.在下述结论中，正确的是（ D ） ①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④ 5.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的 结点个数是（ A ） A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定 6.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ） A．9 B．11 C．15 D．不确定 7.在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的 结点数为（ C ）个 A．4 B．5 C．6 D．7 8.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树 根结点的右子树上的结点个数是（ D ）。【北方交通大学 2001 一、16 （2分）】 A．M1 B．M1+M2 C．M3 D．M2+M3 9.具有10个叶结点的二叉树中有（ B）个度为2的结点， A．8 B．9 C．10 D．ll 10.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（E ） A． 250 B． 500 C．254 D．505 E．以上答案都不对 11.设给定权值总数有n 个，其哈夫曼树的结点总数为( D) A．不确定 B．2n C．2n+1 D．2n-1 12.有关二叉树下列说法正确的是（ B ） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 13.二叉树的第I层上最多含有结点数为（ C ） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 14.一个具有1025个结点的二叉树的高h为（ C ） A．11 B．10 C．11至1025之间 D．10至1024之间 15.一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( B )结点 一、判断题 （√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （×）2.二叉树中每个结点的两棵子树的高度差等于1。 （√）3.二叉树中每个结点的两棵子树是有序的。 （×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 （×）5.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1） （×）6.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （×）7.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i —1个结点。（应2i-1） （√）8.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （√）9.具有12个结点的完全二叉树有5个度为2的结点。 ( ) 10、哈夫曼树中没有度为1的结点，所以必为满二叉树。 ( )11、在哈夫曼树中，权值最小的结点离根结点最近。 ( )12、线索二叉树是一种逻辑结构。 （√）13、深度为K的完全二叉树至少有2K-1个结点。 (√ )14、具有n个结点的满二叉树，其叶结点的个数为（n+1）/2。 (√ )15、前序和中序遍历用线索树方式存储的二叉树，不必使用栈。 (╳ )16、哈夫曼树是带权路径长度最短的树，路径上权值较大的点离根较远。 （√）17、在二叉树结点的先序序列和后序序列中，所有叶子结点的先后顺序完全相同。（√）18、二叉树的遍历操作实际上是将非线性结构线性化的过程 （√）19、树的先根遍历序列与其所转化的二叉树的先序遍历序列相同。 （╳）20、树的后根遍历序列与其所转化的二叉树的后序遍历序列相同。 二、填空 1．由３个结点所构成的二叉树有 5 种形态。 2. 线索二叉树的左线索指向其_前驱_____，右线索指向其__后继____。 3．一棵具有257个结点的完全二叉树，它的深度为 9 。 4、如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数 为_69_____。 5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。另外，最后一结点为2i属于 左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空 右不空的情况，所以非空右子树数＝0. 6. 一棵含有n个结点的k叉树，可能达到的最大深度为n，最小深度为 2 。 第六章树及二叉树 一、判断正误 1、完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。（√） 2、二叉树中每个结点的两棵子树的高度差等于1。（×） 3、二叉树中每个结点的两棵子树是有序的。（√） 4、二叉树中每个结点有两棵非空子树或有两棵空子树。（×） 5、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（×） 6、二叉树是度为2的有序树。（×） 7、二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（×） 8、线索二叉树的优点是便于在中序下查找前驱结点和后继结点。（√） 9、树与二叉树是两种不同的树型结构。（√） 10、哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。（√） 11、一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的 结点前序遍历和后序遍历是一致的。(× ) 12、在哈夫曼树中，权值最小的结点离根结点最近。(× ) 13、对一棵二叉树进行层次遍历时，应借助于一个栈。(× ) 14、深度为K的完全二叉树至少有2K-1个结点。（√） 15、具有n个结点的满二叉树，其叶结点的个数为（n+1）/2。(√ ) 16、二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树 的特殊情况。(× ) 17、完全二叉树一定存在度为1的结点。(× ) 18、二叉树的遍历只是为了在应用中找到一种线性次序。(√ ) 19、二叉树的叶子结点在前序遍历和后序遍历下，皆以相同的相对位 置出现。(√ ) 20、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。(× ) 二、填空 1、二叉树由根结点、左子树、右子树_三个基本单元组成。 2、在二叉树中，指针p所指结点为叶子结点的条件是p->lchild==null && p->rchlid==null。 3、一棵具有257个结点的完全二叉树，它的深度为9。 4、某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_69_。(20+(20-1)+30) 5、设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。 6、一棵含有n个结点的k叉树，可能达到的最大深度为n，最小深度为 2 。 7、若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 F E G H D C B 。 8、具有256个结1`点的完全二叉树的深度为__9___。 9、高度为8的完全二叉树至少有__64___个叶子结点。(2ˆ7-1+1）/2 一、基础知识题 6.1设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，求树T中的叶子数。 【解答】设度为m的树中度为0,1,2,…,m的结点数分别为n0, n1, n2,…, nm，结点总数为n，分枝数为B，则下面二式成立 n= n0+n1+n2+…+nm (1) n=B+1= n1+2n2 +…+mnm+1 (2) 由(1)和(2)得叶子结点数n0=1+ 即： n0=1+(1-1)*4+(2-1)*2+(3-1)*1+(4-1)*1=8 6.2一棵完全二叉树上有1001个结点，求叶子结点的个数。 【解答】因为在任意二叉树中度为2 的结点数n2和叶子结点数n0有如下关系：n2=n0-1,所以设二叉树的结点数为n, 度为1的结点数为n1，则 n= n0+ n1+ n2 n=2n0+n1-1 1002=2n0+n1 由于在完全二叉树中，度为1的结点数n1至多为1，叶子数n0是整数。本题中度为1的结点数n1只能是0，故叶子结点的个数n0为501. 注：解本题时要使用以上公式，不要先判断完全二叉树高10，前9层是满二叉树，第10层都是叶子，……。虽然解法也对，但步骤多且复杂，极易出错。 6.3 一棵124个叶结点的完全二叉树，最多有多少个结点。 【解答】由公式n=2n0+n1-1,当n1为1时，结点数达到最多248个。 6.4．一棵完全二叉树有500个结点，请问该完全二叉树有多少个叶子结点？有多少个度为1的结点？有多少个度为2的结点？如果完全二叉树有501个结点，结果如何？请写出推导过程。 【解答】由公式n=2n0+n1-1，带入具体数得，500=2n0+n1-1，叶子数是整数，度为1的结点数只能为1，故叶子数为250，度为2的结点数是249。 若完全二叉树有501个结点，则叶子数251，度为2的结点数是250，度为1的结点数为0。 6.5 某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数是多少。 【解答】由公式n=2n0+n1-1，得该二叉树的总结点数是69。 6.6 求一棵具有1025个结点的二叉树的高h。 【解答】该二叉树最高为1025（只有一个叶子结点），最低高为11。因为210-1<1025<211-1，故1025个结点的二叉树最低高为11。 6.7 一棵二叉树高度为h，所有结点的度或为0，或为2，则这棵二叉树最少有多少结点。 【解答】第一层只一个根结点，其余各层都两个结点，这棵二叉树最少结点数是2h-1。 6.8将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度是多少。 【解答】设含n个结点的完全三叉树的高度为h，则有 实验一:二叉树的三种遍历方法的非递归实现 要求:1各种遍历方法的实现方法(前序、中序、后序) 2对应的测试函数,要求建立二叉树 3.按照树旋转90度后打印显示二叉树 4直接按照树的形状打印显示二叉树(层次遍历算法) 实验二二叉排序树 要求：1建立二叉排序树 2建立好的二叉排序树进行中序遍历 实验三Huffman编码的实现 要求：1根据Huffman编码的原理,编写一个程序,由用户输入结点值和权值,输出它的Huffman编码. 实验四建立一棵树 要求1输入树的边建立对应的树， 2输出从树根到所有的叶子结点的路径， 3．同时分层输出树中所有的边 作业1求二叉树中位于先序序列中第K个位置结点的值 作业2计算二叉树中叶子结点的数目 作业3二叉树中所有结点的左右子树进行交换 作业4二叉树中结点元素值为x为根结点的子树的深度 作业5二叉树中删除结点元素值为x为根结点的子树 作业6利用顺序存储的完全二叉树建立二叉链表 作业7求一棵以孩子兄弟链表表示的树的度 作业8求一棵以孩子兄弟链表表示的树的叶子个个数 作业9输出一棵以孩子兄弟链表表示的树中所有的边 作业10按层次顺序（从左到右）遍历二叉树 作业11逆转90度按层次顺序打印二叉树 作业12一个堆中插入一个元素后调整为堆 作业13判定给定的二叉树是否为二叉排序树 以下定义保存在bittree.h #ifndef bitree #define bitree typedef char TElemType; typedef struct BiTNode {TElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; #endif 以下定义保存在sqstack.h #include 数据结构-6 树和二叉树
数据结构第六章树和二叉树习题及答案
第六章树和二叉树习题及答案
第6章 树和二叉树-习题-答案
第6章树和二叉树
数据结构习题及答案 (4)
第六章树与二叉树
数据结构第6章 树习题+答案
数据结构第六章 树和二叉树课后习题答案
数据结构与算法第六章课后答案第六章 树和二叉树
第6章树和二叉树(1)
第六章树习题答案
第6章 树和二叉树练习题及答案
第六章 树及二叉树
第6章_数据结构习题题目及答案_树和二叉树_参考答案
第六章 树和二叉树实验指导
相关主题
文本预览