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所示。
A A
B B D C D C F H F H E E
I J J I
第一步 第二步
图5-10
【例5-13】将如图5-11所示的森林转换成二叉树。 A C D
I B E J G F
图5-11
解： 步骤略，结果如图5-12所示。
A
C B
A B C E F I
D H J
第三步
H K L D
H E
F I
L G J
K
图5-12
【例5-14】假定用于通信的电文由8个字符A、B、C、D、E、F、G、H组成，各字母在电文中出现的概率为5％、25％、4％、7％、9％、12％、30％、8％，试为这8个字母设计哈夫曼编码。
解： 根据题意，设这8个字母对应的权值分别为（5，25，4，7，9，12，30，8），并且n=8。
（1）设计哈夫曼树的步骤如图5-13所示。
5 25 4 7 9 12 30 8 第一步：
第二步： 25 7 9 12 30 8 9
4 5
第三步： 15 9 25 9 12 30
7 8 4 5
43 第七步： 57
27 30 18 25
12 15 9 9
7 8 4 5
100 第八步：
43 57
18 30 25 27 15 9 9 12
8 4 5 7
图5-13
（2）设计哈夫曼编码
利用第八步得到的哈夫曼树，规定左分支用0表示，右分支用1表示，字母A、B、C、D、E、F、G、H的哈夫曼编码如下表示：
A:0011 B:01 C:0010 D:1010 E:000 F:100 G:11 H:1011
习题5
一、单项选择题
1. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ 1. C）个。
A. 4 B. 5 C. 6 D. 7
2. 假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（2. B ）个。