第 章 树和二叉树
一、选择题
部分答案解释如下。
由二叉树结点的公式：， 因为 所以
在完全二叉树树中， 只能取 或 在本题中只能取 ，故 ，因此选 。
前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的
和 均对，单支树的特点是只有一个叶子结点，故 是最合适的，选 。 或 都不全。由本题可
解答 题。
左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空
（无后继），共 个空链域。
．线索二叉树是利用二叉树的空链域加上线索， 个结点的二叉树有 个空链域。
二、判断题
部分答案解释如下。
．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。
．任何结点至多只有左子树的二叉树的遍历就不需要栈。
只 对 完 全 二 叉 树 适 用 ， 编 号 为 的 结 点 的 左 儿 子 的 编 号 为 ! ， 右 儿 子 是
（ !）
其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右孩子。
新插入的结点都是叶子结点。
在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该
结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指
针指向祖先）。
．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继
线索为空指针。
三填空题
根结点左子树右子树 双亲链表表示法孩子链表表示法孩子兄弟表示法
．"#$%& $'($$))"#*%&$ '($$+,-,%'平衡因子
.
.
ë$/0
1û
用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。设编
号为 和 2 的结点在顺序存储中的下标为 3和 4则结点 和 2 在同一层上的条件是 ë$/0
3ûë$/0
4û。
ë$/0
ûë$/0
2û55ë$/0
û
1
6
.ë15û
.
.
（第 . 层 个 结 点 ， 总 结 点 个 数 是
， 其 双 亲 是
5
.
） ë$/0
û
&
ë5ûé$/0
.ù
完全二叉树 单枝树，树中任一结点（除最后一个结点是叶子外）只有左子女或只有右子
女。
1第七层满，加第八层１个
至多个。任意二叉树，度为１的结点个数没限制。只有完全二叉树，度为１的结点个数才至
多为 。
．
（该二叉树转换成森林，含三棵树，其第一棵树的先根次序是 ）
先序（）中序 （）任何结点至多只有右子女的二叉树。
+'-7&8%0
．（）略 二叉排序树 二叉树 前序
先根次序（）中根次序 双亲的右子树中最左下的叶子结点 5
（9 的后继是经 9 的双亲 : 的右子树中最左下的叶结点） 前驱 后继
:;$%& $'9:9编者注：本题按中序线索化
带权路径长度最小的二叉树，又称最优二叉树
（不唯一）
本题①是表达式求值，②是在二叉排序树中删除值为 9 的结点。首先查找 9，若没有 9，则结束。
否则分成四种情况讨论：9 结点有左右子树；只有左子树；只有右子树和本身是叶子。
</34/'7*=7>+$4;?%& $'</34/*'7*=7>+$4;@%& $'@@A@无此运算符
47B";?%& $' 47B"1C?? D;@%& $' D 47B";@%& $'
47B";47B!*;47B
IF41?E1(BFELSE(BF(B4;$(B4;*
IF41?1BGA@4!#1?1B#E1+$$F8+$37
ELSE1%&.4;$,BH%&.4;*,BH1
"#*%& $'"#$%& $'"#$%& $'II"#$%& $'II"#*%& $'
4#*%& $'J($$ 4#*%& $'J($$ 1 %/(44#$%& $' %/(44
+
+
*
+ f hg
*
+
a
b
c
+
d e
#*%& $'
"&7 0&4"#$%& $'&7 0&4"#*%& $'$&*&
"!#1?+''9"+''94*77*;*%& $'
34+%.K4"L4"34+%.K4"L"4"
M本算法将二叉树的左右子树交换
② 7N355初始化，申请结点 3;7941? 553 是带头结点的链栈
3;794;'+4+ 55取栈顶元素 3;794F";79455栈顶指针下移
' 3"/37" 55回收空间 ";794F3;794 55将新结点入链栈
"(3&3";*%& $'55先沿树的左分支向下，将 " 的右子女入栈保存
1AE7B"4:3O 3&7F4*(755已完成 O 3&4*(7（或 3;7941?）
7N4, G 4;$%& $', , G4;*%& $',
<(3&3"6"#'+4+%&E" 3##%&
*73($4H"F";$ .HDFD;"*7（（２）（３）顺序可变）
4/"34+%.K4/"L"#*%& $'4/"34+%.K4/"L"#$%& $'
． !219!:K L!#K.L.9
%*7+4E ?9.3;$%& $'%*7+4E ?2.:3;*%& $'
"(3&3-4（）"/"3（）"(3&3";*%& $'55" 的右子树进栈
．""#$%& $'55沿左子树向下 （）""#*%& $'
．（）&$#&*&*&$
4/"#4,55沿左分枝向下 （）4/"55退栈
．"F";$%& $'（）（ ）"FP'+4+K34/"L;*%& $'34/"
,""/355根结点 （）*"/3 "/3*"/3Q "/3 "/3""/3
4/"#34+%.K4/"LF';* 0&4';$784!#1?4/"F4/"左子树非空
"!#4&*55未循环结束 （）"#$4+0"#$%& $'
"#*4+0))"#*%& $'J4&*""#*%& $'""#*%& $'
若 ";*4+0则 ";*%& $'为后继，否则 " 的后继是 " 的右子树中最左下的结点
D";*%& $'D;$4+0D;$%& $'
．（）4*77#$%& $'($$"*7#*%& $'
"*7#*4+0"*7#* 0&44*77H4*77#* 0&4注（）和（）顺序可换
．（）/'7#*R+0,9-4,9/'7#* 0&4
四．应用题
．树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是
说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树
的一些算法去解决树和森林中的问题。
树和二叉树的区别有三：一是二叉树的度至多为 ，树无此限制；二是二叉树有左右子树之分，
即使在只有一个分枝的情况下， 也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为
空，树一般不允许为空（个别书上允许为空）。
树和二叉树逻辑上都是树形结构，区别有以上题 所述三点。二叉树不是树的特例。
．线性表属于约束最强的线性结构，在非空线性表中，只有一个“第一个”元素，也只有一个“最
后一个”元素；除第一个元素外，每个元素有唯一前驱；除最后一个元素外，每个元素有唯一后继。
树是一种层次结构，有且只有一个根结点，每个结点可以有多个子女，但只有一个双亲（根无双亲），
从这个意义上说存在一（双亲）对多（子女）的关系。广义表中的元素既可以是原子，也可以是子
表，子表可以为它表共享。从表中套表意义上说，广义表也是层次结构。从逻辑上讲，树和广义表
均属非线性结构。但在以下意义上，又蜕变为线性结构。如度为 的树，以及广义表中的元素都是
原
子时。另外，广义表从元素之间的关系可看成前驱和后继，也符
合线性表，但这时元素有原子，也有子表，即元素并不属于同一
数据对象。
．方法有二。一是对该算术表达式（二叉树）进行后序遍历，
得到表达式的后序遍历序列，再按后缀表达式求值；二是递归
求出左子树表达式的值，再递归求出右子树表达式的值，最后
按根结点运算符（、、,、5等）进行最后求值。
．该算术表达式转化的二叉树如右图所示。 第 题图
．（#）个结点的 ' 度树共有 ' 个链域，除根结点外，每个结点均有一个指针所指，故
该树的空链域有 '' 个。
．证明：设二叉树度为 和 的结点数及总的结点数分别为 ，和 ，则 S
再设二叉树的分支数为 除根结点外，每个结点都有一个分支所指，则 SSS
度为零的结点是叶子，没有分支，而度为 的结点有两个分支，因此（）式可写为
,SSSSS
由（）、（ ）得 代入（），并由（ ）和（）得 ,。 证毕。
．.
&
& 为层数
（）因为该树每层上均有 6
&
个结点，从根开始编号为 ，则结点 的从右向左数第２个孩子的
结点编号为 . 。设 为结点 的子女，则关系式 .!! . 成立，因 是整数，故结点
的双亲 的编号为 ë5.û 。
结点 #的前一结点编号为 （其最右边子女编号是,.），故结点 的第
个孩子的编号是,. 。
根据以上分析，结点 有右兄弟的条件是，它不是双亲的从右数的第一子女，即 T.J
，其右兄弟编号是 。
．最低高度二叉树的特点是，除最下层结点个数不满外，其余各层的结点数都应达到各层的最
大值。设 个结点的二叉树的最低高度是 &，则 应满足
&
!!
&
关系式。解此不等式，并
考虑 & 是整数，则有 &ë$/0û，即任一结点个数为 的二叉树的高度至少为 A$/0。
．
本题等价于高度为 的满二叉树有多少叶子结点，从根结点到各叶子结点的单枝树是不同
的二叉树。
．。由于本题求二叉树的结点数最多是多少，第 层共有
个结点，已知有 个叶
子，其余 个结点均为分支结点。它在第八层上有 个叶子结点。所以该二叉树的结点数最多
可达
。注意；本题并未明说完全二叉树的高度，但根据题意，只能 层。
．（
）
．证明：设度为 和 的结点数是 和 ，则二叉树结点数 为 BSSSS
由于二叉树根结点没有分枝所指，度为 和 的结点各有 个和 个分枝，度为 的结点没有
分枝，故二叉树的结点数 与分枝数 有如下关系
,SSSSSSSSS
由（）和（），得 B。即 个结点的二叉树，若叶子结点数是 B，则非叶子结点中
有（B）个度为 ，其余度为 。
．根据顺序存储的完全二叉树的性质，编号为 的结点的双亲的编号是 ë 5û，故 K L和 K2L的最
近公共祖先可如下求出：
while 5J25
if #2 5Helse225H
退出 while 后，若 5则最近公共祖先为根结点，否则最近公共祖先是 5。
．1 个结点的 6 叉树，最大高度 1（只有一个叶结点的任意 . 叉树）。设最小高度为 ，第
! !层的结点数 6
，则 1..
S.
，由此得 ë$/0
6
16û
结点个数在 到 的满二叉树且结点数是素数的数是 ，其叶子数是 。
．设分枝结点和叶子结点数分别是为
.
和
，因此有
.
另外从树的分枝数 与结点的关系有 6,
.
由（）和（）有
.
656
用顺序存储结构存储 个结点的完全二叉树。编号为 的结点，其双亲编号是 ë 5û 时无双
亲，其左子女是 若 !否则 无左子女，右子女是 若 !否则无右子女。
根据完全二叉树的性质，最后一个结点（编号为 ）的双亲结点的编号是 ë5û，这是最后一个
分枝结点，在它之后是第一个终端（叶子）结点，故序号最小的叶子结点的下标是 ë5û。
按前序遍历对顶点编号，即根结点从１开始，对前序遍历序列的结点从小到大编号。
设树的结点数为 ，分枝数为 ，则下面二式成立
S
B
SB
B
由和得叶子结点数
m
i
i
1
i
n)1(
é$/0
ù
该结论不成立。对于任一 +U可在 中找到最近祖先 8。+ 在 8 的左子树上。对于从 8 到根结点
路径上所有 -U，有可能 8 在 - 的右子树上，因而 + 也就在 - 的右子树上，这时 +＞-，因此 +＜-
不成立。同理可以证明 -!% 不成立。而对于任何 +V%V 均有 +!%。
个结点的 B 次树，共有 ,B 个指针。除根结点外，其余 个结点均有指针所指，故空指针
数为 ,B,B。证毕。
证明 设度为 和 及叶子结点数分别为
，
和
，则二叉树结点数 为
再看二叉树的分支数，除根结点外，其 余结点都有一个分支进入，设 为分支总数，则
。度为 和 的结点各有 个和 个分支，度为 的结点没有分支，故
由（）和（），得
。
参见题 ．
设完全二叉树中叶子结点数为 ，则根据完全二叉树的性质，度为 的结点数是 ，而完全二
叉树中，度为 的结点数至多为 ，所以具有 个叶子结点的完全二叉树结点数是
或 （ 有 或 无 度 为 的 结 点 ） 。 由 于 具 有 或 个 结 点 的 完 全 二 叉 树 的 深 度 是
ë$/0
û ë$/0
û ， 即 é$/0
ù 故 个 叶 结 点 的 非 满 的 完 全 二 叉 树 的 高 度 是
é$/0
ù。（最下层结点数 #）。
根据二叉树度为 结点个数等于叶子结点个数减 的性质，故具有 个叶子结点且非叶子结
点均有左左子树的二叉树的结点数是 。
证明：当 时，
（
）
，公式成立。设当 时公式成立，证明当 时公式仍成
