第 章 树和二叉树
一、选择题
部分答案解释如下。
由 二 叉 树 结 点 的 公 式 : , 因 为
所以 在完全二叉树树中, 只能取 或 在本题中只能取
,故 ,因此选 。
前序序列是“根左右”,后序序列是“左右根”,若要这两个序列相反,只有单支树,所以
本题的 和 均对,单支树的特点是只有一个叶子结点,故 是最合适的,选 。 或
都不全。由本题可解答 题。
左子树为空的二叉树的根结点的左线索为空(无前驱),先序序列的最后结点的右线
索为空(无后继),共 个空链域。
.线索二叉树是利用二叉树的空链域加上线索, 个结点的二叉树有 个空链域。
二、判断题
部分答案解释如下。
.只有在确定何序(前序、中序、后序或层次)遍历后,遍历结果才唯一。
.任何结点至多只有左子树的二叉树的遍历就不需要栈。
只对完全二叉树适用, 编号为 的结点的左儿子的编号为 ,右儿子是
( )
其中序前驱是其左子树上按中序遍历的最右边的结点(叶子或无右子女),该结点无
右孩子。
新插入的结点都是叶子结点。
在二叉树上,对有左右子女的结点,其中序前驱是其左子树上按中序遍历的最右边的
结点(该结点的后继指针指向祖先),中序后继是其右子树上按中序遍历的最左边的结点
(该结点的前驱指针指向祖先)。
.非空二叉树中序遍历第一个结点无前驱,最后一个结点无后继,这两个结点的前驱线
索和后继线索为空指针。
三填空题
根结点左子树右子树 双亲链表表示法孩子链表表示法孩子兄
弟表示法
.!"#$%#&'##((!")$%#&'##*+,+$& 平
衡因子
-
-
ë#./
0û
用顺序存储二叉树时,要按完全二叉树的形式存储,非完全二叉树存储时,要加“虚结
点”。设编号为 和 1 的结点在顺序存储中的下标为 2和 3则结点 和 1 在同一层上的条件是
ë#./
2ûë#./
3û。
ë#./
ûë#./
1û44ë#./
û
0
5
-ë04û
-
-
( 第 - 层 个 结 点 , 总 结 点 个 数 是
, 其 双 亲 是
4
-
)
ë#./
û
%
ë4ûé#./
-ù
完全二叉树 单枝树,树中任一结点(除最后一个结点是叶子外) 只有左子女或
只有右子女。
0第七层满,加第八层1个
至多个。任意二叉树,度为1的结点个数没限制。只有完全二叉树,度为1的结点
个数才至多为 。
.
(该二叉树转换成森林,含三棵树,其第一棵树的先根次序
是 )
先序()中序 ()任何结点至多只有右子女的
二叉树。
*&,6%7$/
.()略 二叉排序树 二叉树 前序
先根次序()中根次序 双亲的右子树中最左下的叶子结点
4
(8 的后继是经 8 的双亲 9 的右子树中最左下的叶结点) 前驱 后继
9:#$%#&898 编者注:本题按中序线索
化
带权路径长度最小的二叉树,又称最优二叉树
(不唯一)
本题①是表达式求值,②是在二叉排序树中删除值为 8 的结点。首先查找 8,若没有
8,则结束。否则分成四种情况讨论:8 结点有左右子树;只有左子树;只有右子树和本身
是叶子。
;.23.&6)<6=*#3:>$%#&;.23.)&6)<6=*#3:?$%#&??@? 无此运
算符
36A!:>$%#& 36A!0B>> C:?$%#& C 36A!:?$%#&
36A!:36A ):36A
IF30>D0'AEELSE'AE'A3:#'A3:)
IF30>0AF@?3 "0>0A"D0*##E7*#26
ELSE0$%-3:#+AG$%-3:)+AG0
!")$%#& !"#$%#& !"#$%#& HH!"#$%#&
HH!")$%#&
3")$%#&I'## 3")$%#&I'## 0 $.'33"#$%#&
$.'33")$%#&
!%6/%3!"#$%#&%6/%3!")$%#&#%)%
! "0>*&&8!*&&83)66):)$%#&
23*$-J3!K3!23*$-J3!K!3!
L本算法将二叉树的左右子树交换
② 6M244初始化,申请结点 2:6830> 442 是带头结点的链栈
2:683:&*3* 44取栈顶元素 2:683E!:68344栈顶指针下移
&2!.26! 44回收空间 !:683E2:683 44将新结点入链栈
!'2%2!:)$%#&44先沿树的左分支向下,将 ! 的右子女入栈保存
0@D6A!392 N2%6E3)'644 已 完 成 N2%3)'6 ( 或
2:6830>)
6M3 +F 3:#$%#&+ +F 3:)$%#&+
;'2%2!5!"&*3*$%D!2""$%
)62'#3G!E!:#-GCEC:!)6((2)(3)顺序可变)
3.!23*$-J3.!K!")$%#&3.!23*$-J3.!K!
"#$%#&
. 108 9JK "J-K-8
$)6*3D>8-2:#$%#&$)6*3D>1-92:)$%#&
!'2%2,3()!.!2()!'2%2!:)$%#&44! 的右子树进栈
.!!"#$%#&44沿左子树向下 ()!!")$%#&
.()%#"%)%)%#
3.!"3+44沿左分枝向下 ()3.!44退栈
.!E!:#$%#&()( )!EO&*3*J23.!K:)$%#&23.!
+!!.244根结点 ())!.2!.2)!.2P!.2!.2!!.2
3.!"23*$-J3.!KE&:)/%3&:#673 "0>3.!E3.!左
子树非空
! "3%)44未循环结束 ()!"#3*/!"#$%#&
!")3*/((!")$%#&I3%)!!")$%#&!!")$%#&
若 !:)3*/则 !:)$%#&为后继,否则 ! 的后继是 ! 的右子树中最左下的结点
C!:)$%#&C:#3*/C:#$%#&
.()3)66"#$%#&'##!)6")$%#&
+
+
*
+ f hg
*
+
a
b
c
+
d e
!)6")3*/!)6")/%33)66G3)66")/%3注()和()顺序
可换
.().&6")Q*/+8,3+8.&6")/%3
四.应用题
.树的孩子兄弟链表表示法和二叉树二叉链表表示法,本质是一样的,只是解释不
同,也就是说树(树是森林的特例,即森林中只有一棵树的特殊情况)可用二叉树唯一表
示,并可使用二叉树的一些算法去解决树和森林中的问题。
树和二叉树的区别有三:一是二叉树的度至多为 ,树无此限制;二是二叉树有左右
子树之分,即使在只有一个分枝的情况下, 也必须指出是左子树还是右子树,树无此限制
三是二叉树允许为空,树一般不允许为空(个别书上允许为空)。
树和二叉树逻辑上都是树形结构,区别有以上题 所述三点。二叉树不是树的特例。
.线性表属于约束最强的线性结构,在非空线性表中,只有一个“第一个”元素,也只
有一个“最后一个”元素;除第一个元素外,每个元素有唯一前驱;除最后一个元素外,每
个元素有唯一后继。树是一种层次结构,有且只有一个根结点,每个结点可以有多个子女
但只有一个双亲(根无双亲),从这个意义上说存在一(双亲)对多(子女)的关系。广义
表中的元素既可以是原子,也可以是子表,子表可以为它表共享。从表中套表意义上说,
广义表也是层次结构。从逻辑上讲,树和广义表均属非线性结构。但在以下意义上,又蜕
变为线性结构。如度为 的树,以及广义表中的元素都是原
子时。另外,广义表从元素之间的关系可看成前驱和后继,也符
合线性表,但这时元素有原子,也有子表,即元素并不属于同一
数据对象。
.方法有二。一是对该算术表达式(二叉树)进行后序遍历,
得到表达式的后序遍历序列,再按后缀表达式求值;二是递归
求出左子树表达式的值,再递归求出右子树表达式的值,最后
按根结点运算符(、、+、4等)进行最后求值。
.该算术表达式转化的二叉树如右图所示。 第 题图
.(")个结点的 & 度树共有 & 个链域,除根结点外,每个结点均有一个指针
所指,故该树的空链域有 && 个。
.证明:设二叉树度为 和 的结点数及总的结点数分别为 ,和 ,则
R
再设二叉树的分支数为 除根结点外,每个结点都有一个分支所指,则 R
RR
度为零的结点是叶子,没有分支,而度为 的结点有两个分支,因此()式可写为
+RRRRR
由()、( )得 代入(),并由( )和()得 +。 证
毕。
.-
%
% 为层数
()因为该树每层上均有 5
%
个结点,从根开始编号为 ,则结点 的从右向左数第2
个孩子的结点编号为 -。设 为结点 的子女,则关系式- - 成立,因
是整数,故结点 的双亲 的编号为 ë4-û。
结点 "的前一结点编号为 (其最右边子女编号是+-),故结点
的第 个孩子的编号是+-。
根据以上分析,结点 有右兄弟的条件是,它不是双亲的从右数的第一子女,即
S-I,其右兄弟编号是 。
.最低高度二叉树的特点是,除最下层结点个数不满外,其余各层的结点数都应达
到各层的最大值。设 个结点的二叉树的最低高度是 %,则 应满足
%
%
关系
式。解此不等式,并考虑 % 是整数,则有 %ë#./û,即任一结点个数为 的二叉树的
高度至少为 @#./。
.
本题等价于高度为 的满二叉树有多少叶子结点,从根结点到各叶子结点的单
枝树是不同的二叉树。
.。由于本题求二叉树的结点数最多是多少,第 层共有
个结点,已知有
个叶子,其余 个结点均为分支结点。它在第八层上有 个叶子结点。所以该二叉
树的结点数最多可达
。注意;本题并未明说完全二叉树的高度,但根
据题意,只能 层。
.(
)
. 证 明 : 设 度 为 和 的 结 点 数 是 和 , 则 二 叉 树 结 点 数 为
ARRRR
由于二叉树根结点没有分枝所指,度为 和 的结点各有 个和 个分枝,度为 的
结点没有分枝,故二叉树的结点数 与分枝数 有如下关系
+RRRRRRRRR
由()和(),得 A。即 个结点的二叉树,若叶子结点数是 A,则非叶
子结点中有(A)个度为 ,其余度为 。
.根据顺序存储的完全二叉树的性质,编号为 的结点的双亲的编号是 ë4û,故 JK和
J1K的最近公共祖先可如下求出:
while4I14
if"14Gelse114G
退出 while 后,若 4则最近公共祖先为根结点,否则最近公共祖先是 4。
.0 个结点的 5 叉树,最大高度 0(只有一个叶结点的任意 - 叉树)。设最小高度为
,第 层的结点数 5
,则 0--
R-
,由此得 ë#./
5
05
û
结点个数在 到 的满二叉树且结点数是素数的数是 ,其叶子数是 。
.设分枝结点和叶子结点数分别是为
-
和
,因此有
-
另外从树的分枝数 与结点的关系有 5+
-
由()和()有
-
545
用顺序存储结构存储 个结点的完全二叉树。编号为 的结点,其双亲编号是 ë4û
时无双亲,其左子女是 若 否则 无左子女,右子女是 若 否
则无右子女。
根据完全二叉树的性质,最后一个结点(编号为 )的双亲结点的编号是 ë4û,这是
最后一个分枝结点,在它之后是第一个终端(叶子)结点,故序号最小的叶子结点的下标
是 ë4û。
按前序遍历对顶点编号,即根结点从1开始,对前序遍历序列的结点从小到大编号。
设树的结点数为 ,分枝数为 ,则下面二式成立
R
A
RA
A
由和得叶子结点数
m
i
i
1
i
n)1(
é#./
ù