第5章 树
【例5-1】写出如图5-1所示的树的叶子结点、非终端结点、每个结点的度及树深度。
A
B C D E
F G H I J 图5-1 解：
（1）叶子结点有：B、D、F、G、H、I、J。 （2）非终端结点有：A、C、E。
（3）每个结点的度分别是：A的度为4，C的度为2，E的度为3，其余结点的度为0。 （4）树的深度为3。
【例5-2】一棵度为2的树与一棵二叉树有什么区别？
解：度为2的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树的次序不能交换。 【例5-3】树与二叉树有什么区别？
解：区别有两点：
（1）二叉树的一个结点至多有两个子树，树则不然；
（2）二叉树的一个结点的子树有左右之分，而树的子树没有次序。
【例5-4】分别画出具有3个结点的树和三个结点的二叉树的所有不同形态。
解：如图5-2(a)所示，具有3个结点的树有两种不同形态。
图5-2(a) 如图5-2(B)所示，具有3个结点的二叉树有以下五种不同形态。
图5-2(b)
【例5-5】在一棵度为M树中，度为1的结点数为N1，度为2的结点数为N2，??，度为M的结点数为NM，则该数中含有多少个叶子结点？有多少个非终端结点？
解：设度为0的结点（即终端结点）数目为n0，树中的分支数为B，树中总的结点数为N，则有：
（1）从结点的度考虑：
N= n0+ n1+ n2+??+nm
（2）从分支数目考虑：一棵树中只有一个根结点，其他的均为孩子结点，而孩子结点可以由分支数得到。所以有：
N=B+1=0×n0+1×n1+2×n2+?+m×nm+1 由以上两式，可得 n0+ n1+ n2+??+nm=0×n0+1×n1+2×n2+?+m×nm+1 从而可导出叶子结点的数目为：
n0=0×n1+1×n2+?+（m-1）×nm+1=1+i?2?(i?1)nmi
从而可以得到非终端结点的数目为
N- n0= n1+ n2+??+nm=
?ni?1mi
【例5-6】一棵含有N个结点的K叉树，可能达到的最大深度和最小深度各为多少？
解：（1）当k叉树中只有一层的分支数为k，其它层的分支数均为1时，此时的树具有最大的高度，为：n-k+1。
（2）当该k叉树为完全k叉树时，其深度最小。参照二叉树的性质4可知，其深度为：
?logkn?+1。
【例5-7】证明任何一棵满二叉树T中的分支数B满足B=2(N0-1)（其中N0为叶子结点数）。 证明：
∵T为满二叉树
∴不存在度为1的结点
设该二叉树中总的结点数为n，度为2的结点总数为n2，分支数为B 则有n＝n0+ n2 ①
又∵除了根结点外，其余n-1个结点都有一个分支进入，即有n个结点的二叉树共有n-1条边
∴n=B+1 ② 由①、②两式，可得 B+1＝n0+ n2 ③ 又由二叉树的性质3可知 n2＝n0-1 ④
由③、④两式可知 B= n0+ n0-1-1=2(n0-1) 求证成立。
a 【例5-8】如图5-3所示的二叉树，试分别写出它的顺序表示
和链接表示（二叉链表）。 c b
e d 解：
g f （1）顺序表示。
1 2 3 4 5 6 7 8 9 图5-3
10 11 a b c d e ^ ^ ^ ^ f g （2）该二叉树的二叉链表表示如图5-4所示。
a b ∧ c ∧ e ∧ d ∧ ∧ f ∧ ∧ g ∧ 图5-4
【例5-9】试找出满足下列条件的所有二叉树：
（1）先序序列和中序序列相同； （2）中序序列和后序序列相同； （3）先序序列和后序序列相同。 解：
（1）先序序列和中序序列相同的二叉树为：空树或者任一结点均无左孩子的非空二叉树；
（2）中序序列和后序序列相同的二叉树为：空树或者任一结点均无右孩子的非空二叉树；
（3）先序序列和后序序列相同的二叉树为：空树或仅有一个结点的二叉树。
【例5-10】如图5-5所示的二叉树，要求：
a （1）写出按先序、中序、后序遍历得到的结点序列。
（2）画出该二叉树的后序线索二叉树。 c b 解： （1） 先序遍历序列：ABDEFC d 中序遍历序列：DEFBAC e 后序遍历序列：FEDBCA （2）其后序线索二叉树如图5-6所示。
f
图5-5
a b c
d
e
f NULL
图5-6
【例5-11】将图5-7所示的树转换为二叉树。 A B C D E F G H I J K L M 图5-7
解：第一步，加线。第二步，抹线。第三步，旋转。过程如图5-8所示。
A A
B C E B C D E D
F G H F G H I J I J
K K L M L M
图5-8(b) 第二步 抹线 图5-8(a) 第一步 加线
A
B C D F
E
K G
L H M I
A B C E
D H J F I
J
图5-8(c) 第三步 旋转
图5-9
【例5-12】将如图5-9所示的二叉树转换为树。
解： 第一步，加线。第二步，抹线。第三步，调整。过程如图5-10所示。