第 章 树和二叉树
一、选择题
部分答案解释如下。
由 二 叉 树 结 点 的 公 式 ： ， 因 为
所以 在完全二叉树树中， 只能取 或 在本题中只能取
，故 ，因此选 。
前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以
本题的 和 均对，单支树的特点是只有一个叶子结点，故 是最合适的，选 。 或
都不全。由本题可解答 题。
左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线
索为空（无后继），共 个空链域。
．线索二叉树是利用二叉树的空链域加上线索， 个结点的二叉树有 个空链域。
二、判断题
部分答案解释如下。
．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。
．任何结点至多只有左子树的二叉树的遍历就不需要栈。
只对完全二叉树适用， 编号为 的结点的左儿子的编号为 ，右儿子是
（ ）
其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无
右孩子。
新插入的结点都是叶子结点。
在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的
结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点
（该结点的前驱指针指向祖先）。
．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线
索和后继线索为空指针。
三填空题
根结点左子树右子树 双亲链表表示法孩子链表表示法孩子兄
弟表示法
．!"#$%#&'##((!")$%#&'##*+,+$& 平
衡因子
-
-
ë#./
0û
用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结
点”。设编号为 和 1 的结点在顺序存储中的下标为 2和 3则结点 和 1 在同一层上的条件是
ë#./
2ûë#./
3û。
ë#./
ûë#./
1û44ë#./
û
0
5
-ë04û
-
-
（ 第 - 层 个 结 点 ， 总 结 点 个 数 是
， 其 双 亲 是
4
-
）
ë#./
û
%
ë4ûé#./
-ù
完全二叉树 单枝树，树中任一结点（除最后一个结点是叶子外） 只有左子女或
只有右子女。
0第七层满，加第八层１个
至多个。任意二叉树，度为１的结点个数没限制。只有完全二叉树，度为１的结点
个数才至多为 。
．
（该二叉树转换成森林，含三棵树，其第一棵树的先根次序
是 ）
先序（）中序 （）任何结点至多只有右子女的
二叉树。
*&,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（（２）（３）顺序可变）
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
%
个结点，从根开始编号为 ，则结点 的从右向左数第２
个孩子的结点编号为 -。设 为结点 的子女，则关系式- - 成立，因
是整数，故结点 的双亲 的编号为 ë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û。
按前序遍历对顶点编号，即根结点从１开始，对前序遍历序列的结点从小到大编号。
设树的结点数为 ，分枝数为 ，则下面二式成立
R
A
RA
A
由和得叶子结点数
m
i
i
1
i
n)1(
é#./
ù
