第 6章 树
数据结构（ C++描述 ）
6.6 哈夫曼树
６,５树和森林
6.4线索二叉树
6.3遍历二叉树
6.2 二叉树
6.1 树的基本概念
退出
目录
6.1 树的基本概念
6.1.1 树的定义
1．树的定义
树是由 n（ n≥0） 个结点组成的有限集合 。 若 n=0,称为空
树；若 n>0,则：
（ 1） 有一个特定的称为根 （ root） 的结点 。 它只有直接
后继, 但没有直接前驱；
（ 2） 除根结点以外的其它结点可以划分为 m（ m≥0） 个
互不相交的有限集合 T0,T1,…, Tm-1,每个集合 Ti
（ i=0,1,…,m-1） 又是一棵树, 称为根的子树, 每棵子树
的根结点有且仅有一个直接前驱, 但可以有 0个或多个直
接后继 。
由此可知, 树的定义是一个递归的定义, 即树的定义中
又用到了树的概念 。
树的结构参见图 6-1。
A
A
B
C
D
I H G F
E
J
K L
M
（ a ）空树 （ b ）仅含有根结点的树 （ c ） 含有多个结点的树
图 6 - 1 树的示意图
?
在图 6-1(c)中，树的根结点为 A，该树还可以分为三个
互不相交子集 T0,T1,T2，具体请参见图 6-2，其中
T0={B,E,F,J,K,L},T1={C,G},T2={D,H，
I,M}，其中的 T0,T1,T2都是树，称为图 6-1（ C）
中树的子树，而 T0,T1,T2又可以分解成若干棵不相
交子树。如 T0可以分解成 T00,T01两个不相交子集，
T00={E,J,K,L},T01={F}，而 T00又可以分为三个
不相交子集 T000,T001,T002，其中,T000={J}，
T001={K},T002={L}。
C
G
B
E F
J K L
D
H I
M
( a ) T 0 子树 ( b ) T 1 子树 ( c ) T 2 子树
图 6 - 2 图 6 - 1 ( C ) 的树的三个子树
2．树的逻辑结构描述
一棵树的逻辑结构可以用二元组描述为：
tree =(k,R)
k={ki∣ 1≤i≤n;n≥0,ki?elemtype}
R={r}
其中, n为树中结点个数, 若 n=0,则为一棵空树, n>
0时称为一棵非空树, 而关系 r 应满足下列条件：
（ 1） 有且仅有一个结点没有前驱,称该结点为树根 ;
（ 2） 除根结点以外,其余每个结点有且仅有一个直接前
驱 ;
（ 3） 树中每个结点可以有多个直接后继 (孩子结点 )。
例如, 对图 6-1(c )的树结构,可以二元组表示为：
K={A,B,C,D,E,F,G,H,I,J,K,L,M}
R={r}
r={(A,B),(A,C),(A,D),(B,E),(B,F),(C,G)，
(D,H),(D,I),(E,J),(E,K),(E,L),(H,M)}
3．树的基本运算
树的基本运算可以定义如下几种：
(1) inittree(&T)
初始化树 T。
(2) root(T)
求树 T的根结点 。
(3) parent(T,x)
求树 T中, 值为 x的结点的双亲 。
(4) child(T,x,i)
求树 T中, 值为 x的结点的第 i个孩子 。
(5) addchild(y,i,x)
把值为 x的结点作为值为 y的结点的第 i个孩子插入到树
中 。
(6) delchild(x,i)
删除值为 x的结点的第 i个孩子 。
(7) traverse(T)
遍历或访问树 T。
6.1.2 基本术语
1.结点
指树中的一个数据元素，一般用一个字母表示。
2.度
一个结点包含子树的数目，称为该结点的度。
3.树叶 （ 叶子 ）
度为 0的结点，称为叶子结点或树叶，也叫终端结
点。
4.孩子结点
若结点 X有子树，则子树的根结点为 X的孩子结点，也
称为孩子，儿子，子女等。如图 6-1（ c）中 A的孩子为
B,C,D。
5.双亲结点
若结点 X有子女 Y，则 X为 Y的双亲结点。
6.祖先结点
从根结点到该结点所经过分枝上的所有结点为该结点的
祖先, 如图 6-1（ c） 中 M的祖先有 A,D, H 。
7.子孙结点
某一结点的子女及子女的子女都为该结点子孙。
8.兄弟结点
具有同一个双亲的结点，称为兄弟结点。
9.分枝结点
除叶子结点外的所有结点, 为分枝结点, 也叫非终端
结点 。
10,层数
根结点的层数为 1，其它结点的层数为从根结点到该
结点所经过的分支数目再加 1。
11,树的高度 （ 深度 ）
树中结点所处的最大层数称为树的高度, 如空树的
高度为 0,只有一个根结点的树高度为 1。
12.树的度
树中结点度的最大值称为树的度 。
13,有序树
若一棵树中所有子树从左到右的排序是有顺序的，不
能颠倒次序。称该树为有序树。
14,无序树
若一棵树中所有子树的次序无关紧要，则称为无序树。
15,森林 （ 树林 ）
若干棵互不相交的树组成的集合为森林 。 一棵树可以
看成是一个特殊的森林 。
6.1.3 树的表示
1,树形结构表示法
具体参 见图 6-1 。
A
A
B
C
D
I H G F
E
J
K L M
（ a ）空树 （ b ）仅含有根结点的树 （ c ） 含有多个结点的树
图 6 - 1 树的示意图
?
2,凹入法表示法
具体参见图 6-3 。
A
B
E
J
K
L
F
C
G
D
H
M
I
图 6 - 3 图 6 - 1 (c ) 的树的凹入法表示
3,嵌套集合表示法
具体参 见图 6-4 。
A
B
E
J
K
L
F
C
G
D
H
M
I
图 6 - 4 图 6 - 1(c) 的树的集合表示
4.广义表表示法
对图 6-1（ c） 的树结构, 广义表表示法可表示为：
（ A（ B（ E（ J,K,L）, F）, C（ G）, D（ H
（ M）, I）））
6.1.4 树的性质
性质 1 树中的结点数等于所有结点的度加 1。
证明：根据树的定义, 在一棵树中, 除根结点以外, 每
个结点有且仅有一个直接前驱, 也就是说, 每个结点与
指向它的一个分支一一对应, 所以, 除根结点以外的结
点数等于所有结点的分支数 （ 即度数 ）, 而根结点无直
接前驱, 因此, 树中的结点数等于所有结点的度数加 1。
性质 2 度为 k的树中第 i层上最多有 ki-1个结点（ i≥1）。
下面用数学归纳法证明：
对于 i=1,显然成立, 假设对于 i-1层, 上述条件成立,
即第 i-1层最多有 ki-2个结点,
对于第 i层, 结点数最多为第 i-1层结点数的 k倍 （ 因为
度为 k）, 故第 i层的结点数为 ki-2*k= ki-1。
11??kk
h性质 3深度为 h的 k叉树最多有 个结点。
1
1
?
?
k
kh
1
1
?
?
k
kh
证明：由性质 2可知, 若每一层的结点数最多, 则整
个 k 叉 树 结 点 数 最 多, 共有 =k0+k1+… +kh-
1= 。
当一棵 K叉树上的结点数达到 时, 称为 满 K叉
树 。
?
?
?h
i
ik
1
1
性质 4具有 n个结点的 k叉树的最小深度为 ?logk(n(k-
1)+1)?。
1
11
?
??
k
k h
1
1
?
?
k
kh
（ 请注意, ?x? 表示取不小于 x的最小整数, 或叫做对 x上
取整 。 ）
证明：设具有 n个结点的 k叉树的深度为 h,即在该树的前
面 h-1层都是满的, 即每一层的结点数等于 ki-1个 (1≤i≤h-1)，
第 h层 （ 即最后一层 ） 的结点数可能满, 也可能不满, 这
时, 该树具有最小的深度 。 由性质 3知道, 结点数 n应满
足下面条件：
<n≤, 通过转换为,kh-1<n(k-1)+1≤kh,再取以 k为底的
对数后, 可以得到：
h-1<logk(n(k-1)+1)≤h,即有,logk(n(k-1)+1)≤h<logk(n(k-
1)+1)+1,而 h只能取整数, 所以, 该 k叉树的最小深度为
h=?logk(n(k-1)+1)? 。
6.2 二叉树
6.2.1 二叉树的定义
1,二叉树的定义
和树结构定义类似, 二叉树的定义也可以递归形式给
出：
二叉树是 n（ n≥0） 个结点的有限集, 它或者是空集
（ n=0）, 或者由一个根结点及两棵不相交的左子树和
右子树组成 。
二叉树的特点是每个结点最多有两个孩子, 或者说,
在二叉树中, 不存在度大于 2的结点, 并且二叉树是有
序树 （ 树为无序树 ）, 其子树的顺序不能颠倒, 因此,
二叉树有五种不同的形态, 参见图 6-5 。
L
R
L R
?
(a) ( b ) ( c ) ( d ) ( e )
图 6 - 5 二叉树的五种不同的形态
2,二叉树的基本运算
（ 1） inittree(&T)
二叉树的初始化。
（ 2） root(T)
求二叉树的根结点。
（ 3） parent(T,x)
求二叉树 T中值为 x的结点的双亲 。
（ 4） lchild(T,x)
求二叉树 T中值为 x的结点的左孩子。
(5) rchild(T,x)
求二叉树 T中值为 x的结点的右孩子。
(6) lbrother(T,x)
求二叉树 T中值为 x的结点的左兄弟。
(7) rbrother(T,x)
求二叉树 T中值为 x的结点的右兄弟。
(8) traverse(T)
遍历二叉树 T。
(9) createtree(&T)
建立一棵二叉树 T。
(10) addlchild(&T,x,y)
在二叉树 T中，将值为 y的结点作为值为 x的结点的左
孩子插入。
(11) addrchild(&T,x,y)
在二叉树 T中，将值为 y的结点作为值为 x的结点的
右孩子插入。
(12) dellchild(&T,x)
在二叉树 T中，删除值为 x 的结点的左孩子。
(13) delrchild(&t,x)
在二叉树 T中，删除值为 x 的结点的右孩子。
6.2.2 二叉树的性质
性质 1 若二叉树的层数从 1开始, 则二叉树的第 k层结点
数, 最多为 2k-1个 （ k>0） 。
可以用数学归纳法证明之 。
性质 2深度（高度）为 k的二叉树最大结点数为 2k-1
（ k>0）。
证明,深度为 k的二叉树, 若要求结点数最多, 则必
须每一层的结点数都为最多, 由性质 1可知, 最大结
点数应为每一层最大结点数之和 。 既为 20+21+… +2k-
1=2k-1。
性质 3 对任意一棵二叉树, 如果叶子结点个数为 n0，
度为 2的结点个数为 n2,则有 n0=n2+1。
证明：设二叉树中度为 1的结点个数为 n1，根据二叉树
的定义可知，该二叉树的结点数 n=n0+n1+n2。又因为
在二叉树中，度为 0的结点没有孩子，度为 1的结点有 1
个孩子，度为 2的结点有 2个结孩子，故该二叉树的孩
子结点数为 n0*0+n1*1+n2*2,而一棵二叉树中，除根
结点外所有都为孩子 结点，故该二叉树的结点数应为
孩子结点数加 1即,n=n0*0+n1*1+n2*2+1因此,有
n=n0+n1+n2=n0*0+n2*1+n2*2+1，最后得到 n0=n2+1。
为继续给出二叉树的其它性质，先定义两种特殊的二叉
树。
满二叉树 深度为 k具有 2 k-1个结点的二叉树, 称为满
二叉树 。
从上面满二叉树定义可知, 必须是二叉树的每一层上
的结点数都达到最大, 否则就不是满二叉树 。
完全二叉树 如果一棵具有 n个结点的深度为 k的二叉树,
它的每一个结点都与深度为 k的满二叉树中编号为 1~ n
的结点一一对应, 则称这棵二叉树为完全二叉树 。
从完全二叉树定义可知, 结点的排列顺序遵循从上到下,
从左到右的规律 。 所谓从上到下, 表示本层结点数达到
最大后, 才能放入下一层 。 从左到右, 表示同一层结点
必须按从左到右排列, 若左边空一个位置时不能将结点
放入右边 。
从满二叉树及完全二叉树定义还可以知道, 满二叉树
一定是一棵完全二叉树, 反之完全二叉树不一定是一
棵满二叉树 。 满二叉树的叶子结点全部在最底层, 而
完全二叉树的叶子结点可以分布在最下面两层 。 深度
为 4的满二叉树和完全二叉树如图 6-6所示 。
A
B C
D E F G
H I J K L M N O
A
B C
D E G
H
F
（ a ）满二叉树 (b) 完全二叉树
图 6 - 6 满二叉树和完全二叉树示意图
性质 4 具有 n个结点的完全二叉树高度为 ?log2(n)?+1
或 ?log2（ n+1） ? 。
(注意 ?x?表示取不大于 x的最大整数, 也叫做对 x下
取整, ?x?表示取不小于 x的最小整数, 也叫做对 x上
取整 。 )
证明：设该完全二叉树高度为 k,则该二叉树的前面 k-1
层为满二叉树, 共有 2k-1-1个结点, 而该二叉具有 k层,
第 k层至少至少有 1个结点, 最多有 2k-1个结点 。 因此有下
面的不等式成立,（ 2k-1 –1） +1 ≤n ≤（ 2k-1-1） +2k-1，
即有 2k-1≤n≤2k-1。 由式子后半部分可知,n≤2k-1… ① 由式
子前半部分可知 2k-1≤n… ②
由 ① 有 n+1≤2k, 同时取对数得,log2(n+1)≤k
故 k≥log2(n+1),即 k=?log2(n+1)?。 即得到第二个结论 。
由②有 2k-1≤n,同时取对数得,k≤log2n+1即 k=?log2 n?+1,
即第一个结论成立,证毕。
性质 5如果将一棵有 n个结点的完全二叉树从上到下,
从左到右对结点编号 1,2,…, n,然后按此编号将
该二叉树中各结点顺序地存放于一个一维数组中,
并简称编号为 j的结点为 j(1≤j≤n),则有如下结论成立：
（ 1） 若 j=1,则结点 j为根结点, 无双亲, 否则 j的双
亲为 ?j/2?；
（ 2） 若 2j≤n,则结点 j的左子女为 2j,否则无左子女 。
即满足 2j>n的结点为叶子结点；
（ 3） 若 2j+1≤n,则结点 j的右子女为 2j+1,否则无右
子女；
（ 4） 若结点 j序号为奇数且不等于 1,则它的左兄弟为
j-1；
（ 5） 若结点 j序号为偶数且不等于 n,它的右兄弟为
j+1；
（ 6） 结点 j所在层数 (层次 )为 ?log2j?+1；
6.2.3 二叉树的存贮结构
1,顺序存贮结构
将一棵二叉树按完全二叉树顺序存放到一个一维数组
中, 若该二叉树为非完全二叉树, 则必须将相应位置
空出来, 使存放的结果符合完全二叉树形状 。 如图 6-7
给出了顺序存贮形式 。
A B C D E F G A B C D,.,
A
B C
D E F G
A
B
C
D
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
( a) 完全二叉树的存储形式 ( b ) 非完全二叉树的存储形式
图 6 - 7 二叉树的顺序存储形式
对于一棵二叉树,若采用顺序存贮时,当它为完全二叉
树时,比较方便,若为非完全二叉树,将会浪费大量存贮
存贮单元 。 最坏的非完全二叉树是全部只有右分支,设
高度为 K,则需占用 2K-1个存贮单元,而实际只有 k个元
素,实际只需 k个存储单元 。 因此, 对于非完全二叉树,
宜采用下面的链式存储结构 。
2．二叉链表存贮结构
（ 1） 二叉链表表示
将一个结点分成三部分,一部分存放结点本身信息,另外
两部分为指针,分别存放左, 右孩子的地址 。
二叉链表中一个结点可描述为,
1 c h i l d d a t a rc h i l d
对于图 6-7所示二叉树,用二叉链表形式描述见图 6-8。
A
B C
^ D ^ ^ E ^ ^ F ^ ^ G ^
r oo t
A ^
r oo t
^ B
C ^
^ D ^
( a) 完全二叉树的链表 ( b ) 非完全二叉树的二叉链表
图 6 - 8 二叉树的二叉链表表示法
对于一棵二叉树,若采用二叉链表存贮时,当二叉树为
非完全二叉树时,比较方便,若为完全二叉树时,将会占
用较多存贮单元 (存放地址的指针 )。 若一棵二叉树有 n
个结点,采用二叉链表作存贮结构时,共有 2n个指针域,
其中只有 n-1个指针指向左右孩子,其余 n+1个指针为空,
没有发挥作用,被白白浪费掉了,(当然后面介绍的线索
可利用它 )。
（ 2） 二叉链表的数据类型
二叉链表的数据类型描述如下,
struct bitree
{ elemtype data ; //结点数据类型
bitree *lchild,*rchild;} //定义左, 右孩子为指针型
(3)二叉链表的建立
为了后面遍历二叉树方便，先介绍建立二叉链表的算
法（假设 elemtype 为 char型）。
假设二叉链表的数据类型描述如刚才所述, 为建立二叉
链表, 用一个一维表数组来模拟队列, 存放输入的结点,
但是, 输入结点时, 必须按完全二叉树形式, 才能使结
点间满足性质 5,若为非完全二叉树, 则必须给定一些
假想结点 (虚结点 ),使之符合完全二叉树形式 。 为此,
我们在输入结点值时, 存在的结点则输入它对应的字符,
不存在的结点 (虚结点 ),输入逗号, 最后以一个特殊符
号, #‖作为输入的结束,表示建二叉链表已完成 。 建成
的二叉链表可以由根指针 root唯一确定 。
算法描述如下：
#include<iostream.h>
typedef char elemtype;
struct bitree
{ elemtype data;
bitree *lchild,*rchild;};
bitree *create()
{ bitree *q[100]; //定义 q数组作为队列存放二叉链表中
结点, 100为最大容量
bitree *s; //二叉链表中的结点
bitree *root ; //二叉链表的根指针
int front=1,rear=0; //定义队列的头, 尾指针
char ch; //结点的 data域值
root=NULL;
cin>>ch;
while(ch!='#') //输入值为 #号,算法结束
{ s=NULL;
if(ch!=',') //输入数据不为逗号,表示不为虚结点,
否则为虚结点
{ s=new bitree; s->data=ch;
s->lchild=NULL; s->rchild=NULL; }
rear++;
q[rear]=s; //新结点或虚结点进队
if(rear==1) root=s;
else
{ if((s!=NULL)&&(q[front]!=NULL))
{ if(rear%2==0) q[front]->lchild=s;
//rear为偶数,s为双亲左孩子
else q[front]->rchild=s;} //rear为奇
数,s为双亲右孩子
if(rear%2==1) front++; } //出队
cin>>ch;}
return root;
}
例如，对图 6-9所示的二叉树，建立的二叉链表如
图 6-10所示。
A
B
C
D
A
B
C
D
(a) 非完全二叉树 （ b ）增加虚结点后假想为完全二叉树
图 6 - 9 一棵非完全二叉树假想为完全二叉树
(a) 非完全二叉树 ( b ) 增加虚结点后假想
A ^
root
^ B
^
C ^
^ D ^
图 6 - 10 用上述算法建成的二叉链表
对图 6-9(a)所示的二叉树, 要用算法建成图 6-10所
示的二叉树链表, 从键盘输入的数据应为：
AB,,C,,,,D#↙ 其中 #为输入结束, ↙ 为回车符 。
6.3遍历二叉树
所谓遍历二叉树, 就是遵从某种次序, 访问二叉树中
的所有结点, 使得每个结点仅被访问一次 。
这里提到的, 访问, 是指对结点施行某种操作, 操作
可以是输出结点信息, 修改结点的数据值等, 但要求
这种访问不破坏它原来的数据结构 。 在本书中, 我们
规定访问是输出结点信息 data,且以二叉链表作为二
叉树的存贮结构 。
由于二叉树是一种非线性结构，每个结点可能有一
个以上的直接后继，因此，必须规定遍历的规则,并
按此规则遍历二叉树,最后得到二叉树所有结点的一
个线性序列。
令 L,R,D分别代表二叉树的左子树, 右子树, 根结点,
则遍历二叉树有 6种规则,DLR,DRL,LDR,LRD、
RDL,RKD。 若规定二叉树中必须先左后右 (左右顺
序不能颠倒 ),则只有 DLR,LDR,LRD三种遍历规
则 。 DLR称为前根遍历 (或前序遍历, 先序遍历, 先
根遍历 ),LDR称为中根遍历 (或中序遍历 ),LRD称
为后根遍历 (或后序遍历 )。
6.3.1前根遍历
所谓前根遍历, 就是根结点最先遍历, 其次左子树,
最后右子树 。
1,递归遍历
前根遍历二叉树的递归遍历算法描述为：
若二叉树为空, 则算法结束 ;否则
（ 1） 输出根结点；
（ 2） 前根遍历左子树 ;
（ 3） 前根遍历右子树 ;
算法如下,
void preorder(bitree *root)
{ bitree *p;
p=root;
if(p!=NULL)
{cout<<p->data<<― ‖;
preorder(p->lchild);
preorder (p->rchild);}
}
2,非递归遍历
利用一个一维数组作为栈, 来存储二叉链表中结点,
算法思想为：
从二叉树根结点开始, 沿左子树一直走到末端 (左孩子
为空 )为止, 在走的过程中, 访问所遇结点, 并依次把
所遇结点进栈, 当左子树为空时, 从栈顶退出某结点,
并将指针指向该结点的右孩子 。 如此重复, 直到栈为
空或指针为空止 。
算法如下：
void preorder1(bitree *root)
{ bitree *p,*s[100];
int top=0; //top为栈顶指针
p=root;
while((p!=NULL)||(top>0))
{ while(p!=NULL)
{cout<<p->data<<" ";
s[++top]=p; p=p->lchild; }
p=s[top--]; p=p->rchild; }}
6.3.2中根遍历
所谓中根遍历, 就是根在中间, 先左子树, 然后根结
点, 最后右子树 。
1,递归遍历
中根遍历二叉树的递归遍历算法描述为：
若二叉树为空, 则算法结束；否则
⑴ 中根遍历左子树 ;
⑵ 输出根结点 ;
⑶ 中根遍历右子树 。
算法如下,
void inorder(biteee *root)
{ bitree *p;
p=root;
if (p!=NULL)
{ inorder(p->lchild);
cout<<p->data<<― ‖;
inorder(p->rchild);
}
}
2,非递归遍历
同样利用一个一维数组作栈, 来存贮二叉链表中结点,
算法思想为：
从二叉树根结点开始, 沿左子树一直走到末端 (左孩子为
空 )为止, 在走的过程中, 把依次遇到的结点进栈,待左
子树为空时,从栈中退出结点并访问,然后再转向它的右
子树 。 如此重复, 直到栈空或指针为空止 。
算法如下,
void inorder1( bitree *root)
{ bitree *p,*s[100]; //s为一个栈, top为栈顶指针
int top=0;
p=root;
while((p!=NULL)||(top>0))
{ while(p!=NULL)
{s[++top]=p;p=p->lchild;}
{p=s[top--];
cout<<p->data<<" ";
p=p->rchild; } }}
6.3.3 后根遍历
所谓后根遍历, 就是根在最后, 即先左子树, 然后右
子树, 最后根结点 。
1,递归遍历
后根遍历二叉树的递归遍历算法描述为：
若二叉树为空, 则算法结束 ;否则
（ 1） 后根遍历左子树,
（ 2） 后根遍历历子树 ;
（ 3） 访问根结点 。
算法如下,
void postorder( bitree *root)
{ bitree *p;
p=root;
if (p!=NULL)
{ postorder (p->lchild);
postorder (p->rchild);
cout<<p->data<<― ‖;
}
}
2.非递归遍历
利用栈来实现二叉树的后序遍历要比前序和中序遍历复
杂得多, 在后序遍历中, 当搜索指针指向某一个结点时,
不能马上进行访问, 而先要遍历左子树, 所以此结点应
先进栈保存, 当遍历完它的左子树后, 再次回到该结点,
还不能访问它, 还需先遍历其右子树,所以该 结点还必
须再次进栈, 只有等它的右子树遍历完后, 再次退栈时,
才能访问该结点 。 为了区分同一结点的两次进栈, 引入
一个栈次数的标志, 一个元素第一次进栈标志为 0,第
二次进标志为 1,并将标志存入另一个栈中, 当从标志
栈中退出的元素为 1时, 访问结点 。
后序遍历二叉树的非递归算法如下：
void postorder1( bitree *root)
{ bitree *p,*s1[100]; //s1栈存放树中结点
int s2[100],top=0,b; //s2栈存放进栈标志
p=root;
do
{ while(p!=NULL)
{s1[top]=p;s2[top++]=0; //第一次进栈标志为 0
p=p->lchild;}
if(top>0)
{b=s2[--top];
p=s1[top];
if(b==0)
{s1[top]=p;s2[top++]=1; //第二次进栈标志为 0
p=p->rchild;}
else
{cout<<p->data<<" ";
p=NULL;
}
}
}while(top>0);
}
例如, 可以利用上面介绍的遍历算法, 写出如图 6-11
所示二叉树的三种遍历序列为：
先序遍历序列,ABDGCEFH
中序遍历序列,BGDAECFH
后序遍历序列,GDBEHFCA
A
B C
D
E
F
G H
图 6 - 11 一棵二叉树
另外, 在编译原理中, 有用二叉 树来表示一个算术表
达式的情形 。 在一棵二叉树中, 若用操作数代表树叶,
运算符代表非叶子结点, 则这样的树可以代表一个算
术表达式 。 若按前序, 中序, 后序对该二叉树进行遍
历, 则得到的遍历序列分别称为前缀表达式 (或称波兰
式 ),中缀表达式, 后缀表达式 (递波兰式 )。 具体参见
图 6-12。
图 6-12所对应的前缀表达
式,-*abc。
图 6-12所对应的中缀表达
式,a*b-c。
图 6-12所对应的后缀
表达式,ab*c-。
a
c
b
*
-
图 6 - 12 表达式 a*b - c 代表的二叉树
二叉树所对应的遍历序列可以通过递归算法得到, 也
可以通过非递归算法得到 。 但有时要求直接写出序列,
故我们可以用图 6-13所示得到图 6-12的遍历序列 。 从二
叉树的三种递归遍历算法可以知道, 三种遍历算法不
同之处在于访问根结点和遍历左, 右子树的顺序不同,
若递归算法中去掉与递归无关的语句 ——访问根结点,
则三个遍历算法完全相同 。 于是对于二叉树的遍历,
可以看成是从根结点出发, 往左子树走, 若左子树为
空, 返回, 再进入右子树, 右子树访问完后, 再返回
根结点 。 这样一来每个结点都被访问三次, 若将按顺
序第一次访问的结点排列起来, 则得到该二叉树的先
序序列, 第二次访问的结点排列起来, 则得到该二叉
树的中序序列, 第三次访问的结点排列起来, 则得到
该二叉树的后序序列 。 对于图 6-13中, 第一次访问到
的结点用 △ 表示,第二次访问到的结点用 ○ 表示,第三次
访问的结点用 □ 表示,按虚线顺序将所有 △ 排列,则得到
先序序列为 -*abc,将所有 ○ 排列起来则得到中序序列为
a*b-c,将所有 □ 排列起来则得到后序序列 ab*c-。
1
2
* ^ c ^
^ a ^ ^ b ^
6.3.4遍历算法应用举例
例 6-5 由二叉树的前序序列和中序序列建立该二叉树
分析：若二叉树的任意两个结点的值都不相同, 则二
叉树的前序序列和中序序列能唯一确定一棵二叉树 。
另外, 由前序序列和中序序列的定义可知, 前序序列
中第一个结点必为根结点, 而在中序序列中, 根结点
刚好是左, 右子树的分界点, 因此, 可按如下方法建
立二叉树：
1.用前序序列的第一个结点作为根结点 ;
2.在中序序列中查找根结点的位置, 并以此为界将
中序序列划分为左, 右两个序列 (左, 右子树 );
3.根据左, 右子树的中序序列中的结点个数, 将前序
序列去掉根结点后的序列划分为左, 右两个序列, 它
们分别是左, 右子树的前序序列 ;
4.对左, 右子树的前序序列和中序序列递归地实施同
样方法, 直到所得左, 右子树为空 。
假设前序序列为 ABDGHCEFI,中序序列为 GDHBAECIF，
则得到的二叉树如下页所示
1。 A为根结点
A BDGH CEFI
GDHB A ECIF
BD
GH
CE
FI
A
2,B为左子树的根结点
B DGH
GDH B
CE
FI
DH
G
B
A
3,D为左子树的左子树的根
结点
A
B
G H
D
C E
F I
A
B
G H
D
C
FI E
4。 C为右子树的根结点
A
B
G H
D
C
F
I
E
5。 F为右子树的右
子树的根结点
C E FI
E C IF
例 6-6 按层次遍历一棵二叉树
对于一棵二叉树, 若规定遍历顺序为从上到下 (上层遍历
完才进入下层 ),从左到右 (同一层从左到右进行, 这样
的遍历称为按层次遍历：例 6-5的树的层次遍历序列为：
ABCDEFGHI。 下面用一个一维数组来模拟队列, 实现
二叉树的层次遍历 。
Void lorder (bitree * t)
{ bitree *q[maxsize],*p; // maxsize为最大容量
int f,r; // f,r类似于头尾指针
q[1]=t; f=r=1;
while (f<=r)
{ p=q[f]; f++; //出队
cout <<p->data;
if(p ->lchild!=NULL)
{ r++; q[r]=p->1child; } //入队
if (p->rchild!=NULL)
{ r++; q[r]=p->rchild;} //入队
} }
6.4线索二叉树
6.4.1 线索的概念
通过前面介绍的二叉树可知, 遍历二叉树实际上就是将
树中所有结点排成一个线性序列 (即非线性结构线性化 )，
在这样的线性序列中, 很容易求得某个结点在某种遍历
下的直接前驱和后继 。 然而, 有时我们希望不进行遍历
就能快速找到某个结点在某种遍历下的直接前驱和后继,
这样, 就应该把每个结点的直接前驱和直接后继记录下
来 。 为了做到这一点, 可以在原来的二叉链表结点中,
再增加两个指针域, 一个指向前驱, 一个指向后继, 但
这样做将会浪费大量存贮单元, 存贮空间的利用率相当
低 (一个结点中有 4个指针, 1个指左孩子, 1个指右孩子,
1个指前驱, 1个指后继 ),而原来的左, 右孩子域有许多
空指针又没有利用起来 。 为了不浪费存存贮空间, 我们
利用原有的孩子指针为空时来存放直接前驱和后继, 这
样的指针称为, 线索,, 加线索的过程称为线索化, 加
了线索的二叉树, 称为线索二叉树, 对应的二叉链表称
为线索二叉链表 。
在线索二叉树中，由于有了线索，无需遍历二叉树就
可以得到任一结点在某种遍历下的直接前驱和后继。
但是，我们怎样来区分孩子指针域中存放的是左、右
孩子信息还是直接前驱或直接后继信息呢?为此，在二
叉链表结点中，还必须增加两个标志域 ltag,rtag。
ltag和 rtag定义如下：
0 lchild域指向结点的左孩子
ltag=
1 lchild域指向结点在某种遍历下的直
接前驱
0 rchild域指向结点的右孩子
rtag=
1 rchild域指向结点在某种遍历下的直接后继
这样, 二叉链表中每个结点还是有 5个域, 但其中只
有 2个指针, 较原来的 4个指针要方便 。 增加线索后的
二叉链表结点结构可描述如下：
l c h i l d l t a g d a t a r t a g r c h i l d
2,线索的分类
另外, 根据遍历的不同要求, 线索二叉树可以分为：
（ 1） 前序前驱线索二叉树 (只需画出前驱 )
（ 2） 前序后继线索二叉树 (只需画出后继 )
（ 3） 前序线索二叉树 (前驱和后继都要标出 )
（ 4） 中序前驱线索二叉树 (只需画出前驱 )
（ 5） 中序后继线索二叉树 (只需画出中序后继 )
（ 6） 中序线索二叉树 (中序前驱和后继都要标出 )
（ 7） 后序前驱线索二叉树 (只需画出后序前驱 )
（ 8） 后序后继线索二叉树 (中需画出后序后驱 )
（ 9）后序线索二叉树 (后前驱和后继都要标出 )
6.4.2线索的描述
1,结点数据类型描述
struct Hbitree
{ elemtype data;
int ltag,rtag; //左, 右标志域
Hbitree *lchild,*rchild; } ;
2,线索的画法
在二叉树或二叉链表中, 若左孩子为空, 则画出它
的直接前驱, 右孩子为空时, 则画出它的直接后继,
左右孩子不为空时, 不需画前驱和后继 。 这样就得
到了线索二叉树或线索二叉链表 。
A
D
C B
0 A 0
1 B 1 0 C 1
r oot
1 D 1 ^
A
D
C B
N U LL
(a) 二叉树 (b ) 前序线索二叉树 (c) 前序线索二叉链表
图 6 - 15 前序线索示意图
前序序列为,ABCD
A
D
C B
N U LL
N U LL
（ a ） 中序二叉树 （ b ） 中序线索二叉链表
图 6 - 1 6 中序线索示意图
0 A 0
r oot
1 D 1
0 C 1
^
1 B 1
^
中序序列为,BADC
C
0 A 0
1 B 1
^ 0 C 1
1 D 1
root
D
B
A
N U LL
(a) 后序线索二叉树 ( b ) 后序线索二叉链表
图 6 - 17 后序线索示意图
后序序列为,BDCA
6.4.3 线索的算法实现
在此, 仅介绍中序线索二叉树的算法实现, 设为 P为
当前结点, pre为 p的前驱结点, 算法描述如下：
void inth (Hbitree *p)
//将 P所指二叉树中序线索化, 调用该函数之前, pre为
Null,而树中所有结点的 ltag和 rtag都为 0。
{ if (p!=NULL)
{ inth (p->lchild); 左子树线索化
if (p->lchild==NULLl)
p->ltag=1;
if (p->rchild==NULL) p->rtag;
if (pre!=NULL)
{ if(pre->rtag==1) pre->rchild=p;
if (p->ltag=1) p->lchild=pre;
}
pre=p;
inth (p->rchild); //右子树线索化
}
}
6.4.4 线索二叉树上的运算
1,线索二叉树上的查找
（ 1） 查找指定结点在中序线索二叉树中的的直接后继
若所找结点右标志 rtag=1,则右孩子域指向中序后继,
否则, 中序后继应为遍历右子树时的第一个访问结点,
即右子树中最左下的结点 （ 参见图 6-19） 。 从图 6-19
中可知, x的后继为 xk 。
X
X 1
X 2
X K
P
X 0
P
0 x
1
0 x
2
1 x
k
图 6 - 19 求中序后继示意图
（ 2） 查找指定结点在中序线索二叉树中的的直接 前
驱
若所找结点左标志 ltag=1,则左孩子域指向中序前驱,
否则, 中序前驱应为遍历左子树时的最后一个访问结
点, 即左子树中最右下的结点 （ 参见图 6-20） 。 从图
6-20中可知, x的前驱为 xk 。
X
X 1
X 2
x
k
P
0 X
P
x
1
0
x
2 0
x
k
1
图 6 - 20 求中序前驱示意图
(3) 查找指定点在前序线索二叉树中的直接后继
前序后继的查找比较方便，若Ｐ无左孩子，右链为
后继，否则左孩子为后继。
(4) 查找指定结点在后序线索二叉树中的直接前驱
后序前驱的查找也比较方便，若左孩子为空，左链指
前驱，否则，若右子树为空，左孩子指前驱，否则右
孩子为前驱。
求后序后继和前序前驱都比较麻烦, 在此不再作进一步
介绍 。
2．线索二叉树上的遍历
遍历某种次序的线索二叉树, 只要从该次序下的开始
结点出发, 反复找到结点在该次序下的后继, 直到后
继为空 。 这对于中序线索和前序线索二叉树很方便,
但对于后序线索二叉树较麻烦 (因求后序后继较麻烦 )。
故后序线索对于遍历没有什么意义 。
(1)前序遍历线索二叉树算法
void preorder2 (Hbitree *t)
Hbitree *p;
{ p=t; //找到开始结点
while (p!=NULL)
{ cout <<p->data;
p=preordernext(p); //调查函数找前序后继
}}
(2)中序遍历线索二叉树算法
void inorder2 (Hbitree *t)
{ Hbitree *p;p=t;
if (p!=NULL)
{ while (p->ltag==0) p=p->lchild; //找开始结点
while (p!=NULL)
{ cout <<p->data;
p= inordernext(p); //调用函数找中序后继
}}}
从上面算法可知, 线索二叉树上的遍历较一般二叉树
要方便得多 。 但是这种方便是以增加线索为代价的,
增加线索本身要花费大量时间 。 所以二叉树是以二链
表表示, 还是以线索二叉链表示, 可根据具体问题而
定 。
3,线索二叉树的扦入和删除
线索二树上的查找, 遍历都较一般二叉树方便, 但线
索二叉树也存在其缺点, 就扦入和删除运算而言, 线
索二叉树比一般二叉树的时间花费大, 因为除修改指
针外, 还要修改相应线索 。
线索二叉树的扦入和删除较麻烦，因此本书不再介绍
算法
６,５树和森林
６,５,１ 树的存储结构
1,双亲表示
它是以一组连续的存储单元来存放树中的结点, 每个结
点有两个域：一个是 data域, 存放结点信息, 另一个是
parent域, 用来存放双亲的位置 (指针 )。
A
D
C B
F E
H
G
a [ 0] a [ 1]
A B C D E F G H …
- 1 0 0 0 1 2 2 3 …
a [m a xs ine - 1] a [ 7]
da ta
pa r e nt
(a) 树的结构 ( b) 树的双亲表 示法
图 6 - 21 树的双亲表示示意图
该结构的具体描述见图 6-21。
2．孩子表示法
将一个结点所有孩子链接成一个单链表形，而树中有
若干个结点，故有若干个单链表，每个单链表有一个
表头结点，所有表头结点用一个数组来描述，具体描
述参见图 6-22
A
B
C
D
E ^
F ^
G ^
H ^
…
a[2]
a[3]
a[7]
a[1]
a[m axsize - 1]
…
1
2
3
^
4
^
5
6
^
7
^
图 6 - 22 树的孩子表示法（图 6 - 21 （ a ） 中树）示意图
3,双亲孩子表示法
将第 1,2两种方法结合起来, 则得到双亲孩子表示法,
具体参见图 6-23。
A - 1
B 0
C 0
D 0
E 1 ^
F 2 ^
G 2 ^
H 3 ^
4
^
1
2
3
^
5
6
^
7
^
图 6 - 23 树的双亲孩子表示法示意图
4 。 孩子兄弟表示法
类似于二叉链表, 但第一根链指向第一个孩子, 第二
根链指向下一个兄弟 。 将图 6-21(a)的树用孩子兄弟表
示法表示, 见图 6-24。
A ^
B
^
C
^ F D ^
^ G ^ ^ H ^
^ E ^
图 6 - 24 树的孩子兄弟表示法示意图
6.5.2 树, 森林和二叉树的转换
1,树转换成二叉树
可以分为三步：
（ 1） 连线
指相邻兄弟之间连线。
（ 2） 抹线
指抹掉双亲与除左孩子外其它孩子之间的连线。
（ 3） 旋转
只需将树作适当的旋转。
具体实现过程见图 6-25。
G
F
E
D
C
B
A A
B
E
C D
G
F
F
G
D
C
E
B
A
图 6 - 25 树转换成二叉树示意图
连线抹线
旋转
2,森林转换成二叉树
（ 1） 将森林中每一棵树分别转换成二叉树
这在刚才的树转换成二叉树中已经介绍过。
（ 2） 合并
使第 n棵树接入到第 n-1棵的右边并成为它的右子树, 第 n-
1 棵二叉树接入到第 n-2 棵的右边并成为它的右子树, …,
第 2棵二叉树接入到第 1棵的右边并成为它的右子树, 直到
最后剩下一棵二叉树为止 。
C
D
B
A
F
E
I
A
A
A
H
G
E
F
I
H
G
G
F
E
D
C
B
A
I
H
A
D
B
C
图 6 - 26 森林转换成二叉树示意图
合并
3,二叉树还原成树或森林
(1) 右链断开
将二叉树的根结点的右链及右链的右链等全部断开, 得到
若干棵无右子树的二叉树 。
具体操作见图 6-27(b)。
（ 2） 二叉树还原成树
将 （ 1） 中得到的每一棵二叉树都还原成树 （ 与树转换
成二叉树的步骤刚好相反 ） 。
具体操作步骤见图 6-27(c)。
G
D
A
B
C E
F
H
I
J
K
(a) 一个森林得到的二叉树
D
A
B
C E
G
F H I
J
K
( b) 断开根的右链得到 4 棵无右子树的二叉树
C
G
F H I
J
K
D
A
B
E
(c) 四棵二叉树还原成四棵树
H I
J
K
G
F
C D
A
B
E
(d ) 二叉树还原成森林
图 6 - 27 二叉树还原成森林过程
6.5.3 树和森林的遍历
在树和森林中, 一个结点可能有两棵以上的子树, 所
以不宜讨论它们的中序遍历, 即树和森林只有先序遍
历和后序遍历 。
1,先序遍历
（ 1） 树的先序遍历
若树非空，则先访问根结点，然后依次先序遍历各子树。
（ 2） 森林的先序遍历
若森林非空，则先访问森林中第一棵树的根结点，再先
序遍历第一棵树各子树，接着先序遍历第二棵树、第三
棵树,…,直到最后一棵树。
2,后序遍历
（ 1） 树的后序遍历
若树非空，则依次后序遍历各子树，最后访问根结点。
（ 2） 森林的后序遍历
按顺序后序遍历森林中的每一棵树。
另外，请注意，树和森林的先序遍历等价于它转换成的
二叉树的先序遍历，树和森林的后序遍历等价于它转换
成的二叉树的中序遍历。
6.6 哈夫曼树
6.6.1基本术语
1,路径和路径长度
在一棵树中, 从一个结点往下可以达到的孩子或子孙结
点之间的通路, 称为路径 。 通路中分支的数目称为路径
长度 。
若规定根结点的层数为 1,则从根结点到第 L层结点的路
径长度为 L-1。
2,结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值, 则这个数
值称为该结点的权 。
结点的带权路径长度为：从根结点到该结点之间的路径
长度与该结点的权的乘积。
3,树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长
度之和, 记为 wpl=, 其中 n 为叶子结点数目, wi
为第 i 个叶子结点的权值, li 为第 i 个叶子结点的路径
长度 。
?
?
n
i
iilw
1
6.6.2 哈夫曼树构造
1,哈夫曼树的定义
在一棵二叉树中, 若带权路径长度达到最小, 称这
样的二 叉树 为最 优二 叉树, 也 称为 哈夫 曼树
(Huffman tree)。
例如, 给定叶子结点的权分别为 1,3,5,7,则可以得到如
图 6-28所示的不同二叉树 。
从图 6-28可知, 图 6-28 (b)的长度最短, 图 6-28 (c)为较差
情形, 当然读者还可以自已构造出具有不同的 wpl情形来 。
5
7
1 3
1 7
5
3
1 3
7
5
( a ) w p l= 3 2 ( b ) w p l= 2 9 ( c ) w p l= 3 5
图 6 - 2 8 具有不同带 权路径长度的二叉树
2,哈夫曼树的构造
假设有 n个权值, 则构造出的哈夫曼树有 n个叶子结点 。
n个权值分别设为 w1,w2,…,wn,则哈夫曼树的构造规则为：
(1) 将 w1,w2,…,wn看成是有 n 棵树的森林 (每棵树仅有一
个结点 )；
(2) 在森林中选出两个根结点的权值最小的树合并, 作
为一棵新树的左, 右子树, 且新树的根结点权值为其左,
右子树根结点权值之和；
(3)从森林中删除选取的两棵树, 并将新树加入森林；
(4)重复 (2),(3)步，直到森林中只剩一棵树为止，该树
即为我们所求得的哈夫曼树。
下面给出哈夫曼树的构造过程, 假设给定的叶子结点的
权分别为 1,5,7,3,则构造哈夫曼树过程如图 6-29所示 。
从图 6-29可知, n 个权值构造哈夫曼树需 n-1次合并, 每
次合并, 森林中的树数目减 1,最后森林中只剩下一棵树,
即为我们求得的哈夫曼树 。
3 7 5 1 5 7
1 3
4
( a) 初如森林 ( b ) 一次合并后的森林
5
9
1 3
4
7
5
9
1 3
4
7
16
(c) 二次合并后的森林 ( d ) 三合并后的森林
图 6 - 29 哈夫曼树的构造过程
6.6.3哈夫曼树的应用
1,哈夫曼编码
通信中, 可以采用 0,1的不同排列来表示不同的字符, 称
为二进制编码 。 而哈夫曼树在数据编码中的应用, 是数据
的最小冗余编码问题, 它是数据压缩学的基础 。 若每个字
符出现的频率相同, 则可以采用等长的二进制编码, 若频
率不同, 则可以采用不等长的二进编码, 频率较大的采用
位数较少的编码, 频率较小的字符采用位数较多的编码,
这样可以使字符的整体编码长度最小, 这就是最小冗余编
码的问题 。 而哈夫曼编码就是一种不等长的二进制编
码, 且哈夫曼树是一种最优二叉树, 它的编码也是一种最
优编码, 在哈夫曼树中, 规定往左编码为 0,往右编码为 1，
则得到叶子结点编码为从根结点到叶子结点中所有路径中
0和 1的顺序排列 。
例如, 给定权 {1,5,7,3},得到的哈夫曼树及编码见
图 6-32 (假定权值就代表该字符名字 )。
7
16
9
4 5
1 3
(a) 哈夫曼树 ( b) 哈夫曼编码
图 6 - 32 构造哈夫曼树及哈夫曼编码
1 的编码 为,100
5 的编码为,11
7 的编码为,0
3 的编码为,101
2,哈夫曼译码
在通信中, 若将字符用哈夫曼编码形式发送出去, 对
方接收到编码后, 将编码还原成字符的过程, 称为哈
夫曼译码 。
数据结构（ C++描述 ）
6.6 哈夫曼树
６,５树和森林
6.4线索二叉树
6.3遍历二叉树
6.2 二叉树
6.1 树的基本概念
退出
目录
6.1 树的基本概念
6.1.1 树的定义
1．树的定义
树是由 n（ n≥0） 个结点组成的有限集合 。 若 n=0,称为空
树；若 n>0,则：
（ 1） 有一个特定的称为根 （ root） 的结点 。 它只有直接
后继, 但没有直接前驱；
（ 2） 除根结点以外的其它结点可以划分为 m（ m≥0） 个
互不相交的有限集合 T0,T1,…, Tm-1,每个集合 Ti
（ i=0,1,…,m-1） 又是一棵树, 称为根的子树, 每棵子树
的根结点有且仅有一个直接前驱, 但可以有 0个或多个直
接后继 。
由此可知, 树的定义是一个递归的定义, 即树的定义中
又用到了树的概念 。
树的结构参见图 6-1。
A
A
B
C
D
I H G F
E
J
K L
M
（ a ）空树 （ b ）仅含有根结点的树 （ c ） 含有多个结点的树
图 6 - 1 树的示意图
?
在图 6-1(c)中，树的根结点为 A，该树还可以分为三个
互不相交子集 T0,T1,T2，具体请参见图 6-2，其中
T0={B,E,F,J,K,L},T1={C,G},T2={D,H，
I,M}，其中的 T0,T1,T2都是树，称为图 6-1（ C）
中树的子树，而 T0,T1,T2又可以分解成若干棵不相
交子树。如 T0可以分解成 T00,T01两个不相交子集，
T00={E,J,K,L},T01={F}，而 T00又可以分为三个
不相交子集 T000,T001,T002，其中,T000={J}，
T001={K},T002={L}。
C
G
B
E F
J K L
D
H I
M
( a ) T 0 子树 ( b ) T 1 子树 ( c ) T 2 子树
图 6 - 2 图 6 - 1 ( C ) 的树的三个子树
2．树的逻辑结构描述
一棵树的逻辑结构可以用二元组描述为：
tree =(k,R)
k={ki∣ 1≤i≤n;n≥0,ki?elemtype}
R={r}
其中, n为树中结点个数, 若 n=0,则为一棵空树, n>
0时称为一棵非空树, 而关系 r 应满足下列条件：
（ 1） 有且仅有一个结点没有前驱,称该结点为树根 ;
（ 2） 除根结点以外,其余每个结点有且仅有一个直接前
驱 ;
（ 3） 树中每个结点可以有多个直接后继 (孩子结点 )。
例如, 对图 6-1(c )的树结构,可以二元组表示为：
K={A,B,C,D,E,F,G,H,I,J,K,L,M}
R={r}
r={(A,B),(A,C),(A,D),(B,E),(B,F),(C,G)，
(D,H),(D,I),(E,J),(E,K),(E,L),(H,M)}
3．树的基本运算
树的基本运算可以定义如下几种：
(1) inittree(&T)
初始化树 T。
(2) root(T)
求树 T的根结点 。
(3) parent(T,x)
求树 T中, 值为 x的结点的双亲 。
(4) child(T,x,i)
求树 T中, 值为 x的结点的第 i个孩子 。
(5) addchild(y,i,x)
把值为 x的结点作为值为 y的结点的第 i个孩子插入到树
中 。
(6) delchild(x,i)
删除值为 x的结点的第 i个孩子 。
(7) traverse(T)
遍历或访问树 T。
6.1.2 基本术语
1.结点
指树中的一个数据元素，一般用一个字母表示。
2.度
一个结点包含子树的数目，称为该结点的度。
3.树叶 （ 叶子 ）
度为 0的结点，称为叶子结点或树叶，也叫终端结
点。
4.孩子结点
若结点 X有子树，则子树的根结点为 X的孩子结点，也
称为孩子，儿子，子女等。如图 6-1（ c）中 A的孩子为
B,C,D。
5.双亲结点
若结点 X有子女 Y，则 X为 Y的双亲结点。
6.祖先结点
从根结点到该结点所经过分枝上的所有结点为该结点的
祖先, 如图 6-1（ c） 中 M的祖先有 A,D, H 。
7.子孙结点
某一结点的子女及子女的子女都为该结点子孙。
8.兄弟结点
具有同一个双亲的结点，称为兄弟结点。
9.分枝结点
除叶子结点外的所有结点, 为分枝结点, 也叫非终端
结点 。
10,层数
根结点的层数为 1，其它结点的层数为从根结点到该
结点所经过的分支数目再加 1。
11,树的高度 （ 深度 ）
树中结点所处的最大层数称为树的高度, 如空树的
高度为 0,只有一个根结点的树高度为 1。
12.树的度
树中结点度的最大值称为树的度 。
13,有序树
若一棵树中所有子树从左到右的排序是有顺序的，不
能颠倒次序。称该树为有序树。
14,无序树
若一棵树中所有子树的次序无关紧要，则称为无序树。
15,森林 （ 树林 ）
若干棵互不相交的树组成的集合为森林 。 一棵树可以
看成是一个特殊的森林 。
6.1.3 树的表示
1,树形结构表示法
具体参 见图 6-1 。
A
A
B
C
D
I H G F
E
J
K L M
（ a ）空树 （ b ）仅含有根结点的树 （ c ） 含有多个结点的树
图 6 - 1 树的示意图
?
2,凹入法表示法
具体参见图 6-3 。
A
B
E
J
K
L
F
C
G
D
H
M
I
图 6 - 3 图 6 - 1 (c ) 的树的凹入法表示
3,嵌套集合表示法
具体参 见图 6-4 。
A
B
E
J
K
L
F
C
G
D
H
M
I
图 6 - 4 图 6 - 1(c) 的树的集合表示
4.广义表表示法
对图 6-1（ c） 的树结构, 广义表表示法可表示为：
（ A（ B（ E（ J,K,L）, F）, C（ G）, D（ H
（ M）, I）））
6.1.4 树的性质
性质 1 树中的结点数等于所有结点的度加 1。
证明：根据树的定义, 在一棵树中, 除根结点以外, 每
个结点有且仅有一个直接前驱, 也就是说, 每个结点与
指向它的一个分支一一对应, 所以, 除根结点以外的结
点数等于所有结点的分支数 （ 即度数 ）, 而根结点无直
接前驱, 因此, 树中的结点数等于所有结点的度数加 1。
性质 2 度为 k的树中第 i层上最多有 ki-1个结点（ i≥1）。
下面用数学归纳法证明：
对于 i=1,显然成立, 假设对于 i-1层, 上述条件成立,
即第 i-1层最多有 ki-2个结点,
对于第 i层, 结点数最多为第 i-1层结点数的 k倍 （ 因为
度为 k）, 故第 i层的结点数为 ki-2*k= ki-1。
11??kk
h性质 3深度为 h的 k叉树最多有 个结点。
1
1
?
?
k
kh
1
1
?
?
k
kh
证明：由性质 2可知, 若每一层的结点数最多, 则整
个 k 叉 树 结 点 数 最 多, 共有 =k0+k1+… +kh-
1= 。
当一棵 K叉树上的结点数达到 时, 称为 满 K叉
树 。
?
?
?h
i
ik
1
1
性质 4具有 n个结点的 k叉树的最小深度为 ?logk(n(k-
1)+1)?。
1
11
?
??
k
k h
1
1
?
?
k
kh
（ 请注意, ?x? 表示取不小于 x的最小整数, 或叫做对 x上
取整 。 ）
证明：设具有 n个结点的 k叉树的深度为 h,即在该树的前
面 h-1层都是满的, 即每一层的结点数等于 ki-1个 (1≤i≤h-1)，
第 h层 （ 即最后一层 ） 的结点数可能满, 也可能不满, 这
时, 该树具有最小的深度 。 由性质 3知道, 结点数 n应满
足下面条件：
<n≤, 通过转换为,kh-1<n(k-1)+1≤kh,再取以 k为底的
对数后, 可以得到：
h-1<logk(n(k-1)+1)≤h,即有,logk(n(k-1)+1)≤h<logk(n(k-
1)+1)+1,而 h只能取整数, 所以, 该 k叉树的最小深度为
h=?logk(n(k-1)+1)? 。
6.2 二叉树
6.2.1 二叉树的定义
1,二叉树的定义
和树结构定义类似, 二叉树的定义也可以递归形式给
出：
二叉树是 n（ n≥0） 个结点的有限集, 它或者是空集
（ n=0）, 或者由一个根结点及两棵不相交的左子树和
右子树组成 。
二叉树的特点是每个结点最多有两个孩子, 或者说,
在二叉树中, 不存在度大于 2的结点, 并且二叉树是有
序树 （ 树为无序树 ）, 其子树的顺序不能颠倒, 因此,
二叉树有五种不同的形态, 参见图 6-5 。
L
R
L R
?
(a) ( b ) ( c ) ( d ) ( e )
图 6 - 5 二叉树的五种不同的形态
2,二叉树的基本运算
（ 1） inittree(&T)
二叉树的初始化。
（ 2） root(T)
求二叉树的根结点。
（ 3） parent(T,x)
求二叉树 T中值为 x的结点的双亲 。
（ 4） lchild(T,x)
求二叉树 T中值为 x的结点的左孩子。
(5) rchild(T,x)
求二叉树 T中值为 x的结点的右孩子。
(6) lbrother(T,x)
求二叉树 T中值为 x的结点的左兄弟。
(7) rbrother(T,x)
求二叉树 T中值为 x的结点的右兄弟。
(8) traverse(T)
遍历二叉树 T。
(9) createtree(&T)
建立一棵二叉树 T。
(10) addlchild(&T,x,y)
在二叉树 T中，将值为 y的结点作为值为 x的结点的左
孩子插入。
(11) addrchild(&T,x,y)
在二叉树 T中，将值为 y的结点作为值为 x的结点的
右孩子插入。
(12) dellchild(&T,x)
在二叉树 T中，删除值为 x 的结点的左孩子。
(13) delrchild(&t,x)
在二叉树 T中，删除值为 x 的结点的右孩子。
6.2.2 二叉树的性质
性质 1 若二叉树的层数从 1开始, 则二叉树的第 k层结点
数, 最多为 2k-1个 （ k>0） 。
可以用数学归纳法证明之 。
性质 2深度（高度）为 k的二叉树最大结点数为 2k-1
（ k>0）。
证明,深度为 k的二叉树, 若要求结点数最多, 则必
须每一层的结点数都为最多, 由性质 1可知, 最大结
点数应为每一层最大结点数之和 。 既为 20+21+… +2k-
1=2k-1。
性质 3 对任意一棵二叉树, 如果叶子结点个数为 n0，
度为 2的结点个数为 n2,则有 n0=n2+1。
证明：设二叉树中度为 1的结点个数为 n1，根据二叉树
的定义可知，该二叉树的结点数 n=n0+n1+n2。又因为
在二叉树中，度为 0的结点没有孩子，度为 1的结点有 1
个孩子，度为 2的结点有 2个结孩子，故该二叉树的孩
子结点数为 n0*0+n1*1+n2*2,而一棵二叉树中，除根
结点外所有都为孩子 结点，故该二叉树的结点数应为
孩子结点数加 1即,n=n0*0+n1*1+n2*2+1因此,有
n=n0+n1+n2=n0*0+n2*1+n2*2+1，最后得到 n0=n2+1。
为继续给出二叉树的其它性质，先定义两种特殊的二叉
树。
满二叉树 深度为 k具有 2 k-1个结点的二叉树, 称为满
二叉树 。
从上面满二叉树定义可知, 必须是二叉树的每一层上
的结点数都达到最大, 否则就不是满二叉树 。
完全二叉树 如果一棵具有 n个结点的深度为 k的二叉树,
它的每一个结点都与深度为 k的满二叉树中编号为 1~ n
的结点一一对应, 则称这棵二叉树为完全二叉树 。
从完全二叉树定义可知, 结点的排列顺序遵循从上到下,
从左到右的规律 。 所谓从上到下, 表示本层结点数达到
最大后, 才能放入下一层 。 从左到右, 表示同一层结点
必须按从左到右排列, 若左边空一个位置时不能将结点
放入右边 。
从满二叉树及完全二叉树定义还可以知道, 满二叉树
一定是一棵完全二叉树, 反之完全二叉树不一定是一
棵满二叉树 。 满二叉树的叶子结点全部在最底层, 而
完全二叉树的叶子结点可以分布在最下面两层 。 深度
为 4的满二叉树和完全二叉树如图 6-6所示 。
A
B C
D E F G
H I J K L M N O
A
B C
D E G
H
F
（ a ）满二叉树 (b) 完全二叉树
图 6 - 6 满二叉树和完全二叉树示意图
性质 4 具有 n个结点的完全二叉树高度为 ?log2(n)?+1
或 ?log2（ n+1） ? 。
(注意 ?x?表示取不大于 x的最大整数, 也叫做对 x下
取整, ?x?表示取不小于 x的最小整数, 也叫做对 x上
取整 。 )
证明：设该完全二叉树高度为 k,则该二叉树的前面 k-1
层为满二叉树, 共有 2k-1-1个结点, 而该二叉具有 k层,
第 k层至少至少有 1个结点, 最多有 2k-1个结点 。 因此有下
面的不等式成立,（ 2k-1 –1） +1 ≤n ≤（ 2k-1-1） +2k-1，
即有 2k-1≤n≤2k-1。 由式子后半部分可知,n≤2k-1… ① 由式
子前半部分可知 2k-1≤n… ②
由 ① 有 n+1≤2k, 同时取对数得,log2(n+1)≤k
故 k≥log2(n+1),即 k=?log2(n+1)?。 即得到第二个结论 。
由②有 2k-1≤n,同时取对数得,k≤log2n+1即 k=?log2 n?+1,
即第一个结论成立,证毕。
性质 5如果将一棵有 n个结点的完全二叉树从上到下,
从左到右对结点编号 1,2,…, n,然后按此编号将
该二叉树中各结点顺序地存放于一个一维数组中,
并简称编号为 j的结点为 j(1≤j≤n),则有如下结论成立：
（ 1） 若 j=1,则结点 j为根结点, 无双亲, 否则 j的双
亲为 ?j/2?；
（ 2） 若 2j≤n,则结点 j的左子女为 2j,否则无左子女 。
即满足 2j>n的结点为叶子结点；
（ 3） 若 2j+1≤n,则结点 j的右子女为 2j+1,否则无右
子女；
（ 4） 若结点 j序号为奇数且不等于 1,则它的左兄弟为
j-1；
（ 5） 若结点 j序号为偶数且不等于 n,它的右兄弟为
j+1；
（ 6） 结点 j所在层数 (层次 )为 ?log2j?+1；
6.2.3 二叉树的存贮结构
1,顺序存贮结构
将一棵二叉树按完全二叉树顺序存放到一个一维数组
中, 若该二叉树为非完全二叉树, 则必须将相应位置
空出来, 使存放的结果符合完全二叉树形状 。 如图 6-7
给出了顺序存贮形式 。
A B C D E F G A B C D,.,
A
B C
D E F G
A
B
C
D
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
( a) 完全二叉树的存储形式 ( b ) 非完全二叉树的存储形式
图 6 - 7 二叉树的顺序存储形式
对于一棵二叉树,若采用顺序存贮时,当它为完全二叉
树时,比较方便,若为非完全二叉树,将会浪费大量存贮
存贮单元 。 最坏的非完全二叉树是全部只有右分支,设
高度为 K,则需占用 2K-1个存贮单元,而实际只有 k个元
素,实际只需 k个存储单元 。 因此, 对于非完全二叉树,
宜采用下面的链式存储结构 。
2．二叉链表存贮结构
（ 1） 二叉链表表示
将一个结点分成三部分,一部分存放结点本身信息,另外
两部分为指针,分别存放左, 右孩子的地址 。
二叉链表中一个结点可描述为,
1 c h i l d d a t a rc h i l d
对于图 6-7所示二叉树,用二叉链表形式描述见图 6-8。
A
B C
^ D ^ ^ E ^ ^ F ^ ^ G ^
r oo t
A ^
r oo t
^ B
C ^
^ D ^
( a) 完全二叉树的链表 ( b ) 非完全二叉树的二叉链表
图 6 - 8 二叉树的二叉链表表示法
对于一棵二叉树,若采用二叉链表存贮时,当二叉树为
非完全二叉树时,比较方便,若为完全二叉树时,将会占
用较多存贮单元 (存放地址的指针 )。 若一棵二叉树有 n
个结点,采用二叉链表作存贮结构时,共有 2n个指针域,
其中只有 n-1个指针指向左右孩子,其余 n+1个指针为空,
没有发挥作用,被白白浪费掉了,(当然后面介绍的线索
可利用它 )。
（ 2） 二叉链表的数据类型
二叉链表的数据类型描述如下,
struct bitree
{ elemtype data ; //结点数据类型
bitree *lchild,*rchild;} //定义左, 右孩子为指针型
(3)二叉链表的建立
为了后面遍历二叉树方便，先介绍建立二叉链表的算
法（假设 elemtype 为 char型）。
假设二叉链表的数据类型描述如刚才所述, 为建立二叉
链表, 用一个一维表数组来模拟队列, 存放输入的结点,
但是, 输入结点时, 必须按完全二叉树形式, 才能使结
点间满足性质 5,若为非完全二叉树, 则必须给定一些
假想结点 (虚结点 ),使之符合完全二叉树形式 。 为此,
我们在输入结点值时, 存在的结点则输入它对应的字符,
不存在的结点 (虚结点 ),输入逗号, 最后以一个特殊符
号, #‖作为输入的结束,表示建二叉链表已完成 。 建成
的二叉链表可以由根指针 root唯一确定 。
算法描述如下：
#include<iostream.h>
typedef char elemtype;
struct bitree
{ elemtype data;
bitree *lchild,*rchild;};
bitree *create()
{ bitree *q[100]; //定义 q数组作为队列存放二叉链表中
结点, 100为最大容量
bitree *s; //二叉链表中的结点
bitree *root ; //二叉链表的根指针
int front=1,rear=0; //定义队列的头, 尾指针
char ch; //结点的 data域值
root=NULL;
cin>>ch;
while(ch!='#') //输入值为 #号,算法结束
{ s=NULL;
if(ch!=',') //输入数据不为逗号,表示不为虚结点,
否则为虚结点
{ s=new bitree; s->data=ch;
s->lchild=NULL; s->rchild=NULL; }
rear++;
q[rear]=s; //新结点或虚结点进队
if(rear==1) root=s;
else
{ if((s!=NULL)&&(q[front]!=NULL))
{ if(rear%2==0) q[front]->lchild=s;
//rear为偶数,s为双亲左孩子
else q[front]->rchild=s;} //rear为奇
数,s为双亲右孩子
if(rear%2==1) front++; } //出队
cin>>ch;}
return root;
}
例如，对图 6-9所示的二叉树，建立的二叉链表如
图 6-10所示。
A
B
C
D
A
B
C
D
(a) 非完全二叉树 （ b ）增加虚结点后假想为完全二叉树
图 6 - 9 一棵非完全二叉树假想为完全二叉树
(a) 非完全二叉树 ( b ) 增加虚结点后假想
A ^
root
^ B
^
C ^
^ D ^
图 6 - 10 用上述算法建成的二叉链表
对图 6-9(a)所示的二叉树, 要用算法建成图 6-10所
示的二叉树链表, 从键盘输入的数据应为：
AB,,C,,,,D#↙ 其中 #为输入结束, ↙ 为回车符 。
6.3遍历二叉树
所谓遍历二叉树, 就是遵从某种次序, 访问二叉树中
的所有结点, 使得每个结点仅被访问一次 。
这里提到的, 访问, 是指对结点施行某种操作, 操作
可以是输出结点信息, 修改结点的数据值等, 但要求
这种访问不破坏它原来的数据结构 。 在本书中, 我们
规定访问是输出结点信息 data,且以二叉链表作为二
叉树的存贮结构 。
由于二叉树是一种非线性结构，每个结点可能有一
个以上的直接后继，因此，必须规定遍历的规则,并
按此规则遍历二叉树,最后得到二叉树所有结点的一
个线性序列。
令 L,R,D分别代表二叉树的左子树, 右子树, 根结点,
则遍历二叉树有 6种规则,DLR,DRL,LDR,LRD、
RDL,RKD。 若规定二叉树中必须先左后右 (左右顺
序不能颠倒 ),则只有 DLR,LDR,LRD三种遍历规
则 。 DLR称为前根遍历 (或前序遍历, 先序遍历, 先
根遍历 ),LDR称为中根遍历 (或中序遍历 ),LRD称
为后根遍历 (或后序遍历 )。
6.3.1前根遍历
所谓前根遍历, 就是根结点最先遍历, 其次左子树,
最后右子树 。
1,递归遍历
前根遍历二叉树的递归遍历算法描述为：
若二叉树为空, 则算法结束 ;否则
（ 1） 输出根结点；
（ 2） 前根遍历左子树 ;
（ 3） 前根遍历右子树 ;
算法如下,
void preorder(bitree *root)
{ bitree *p;
p=root;
if(p!=NULL)
{cout<<p->data<<― ‖;
preorder(p->lchild);
preorder (p->rchild);}
}
2,非递归遍历
利用一个一维数组作为栈, 来存储二叉链表中结点,
算法思想为：
从二叉树根结点开始, 沿左子树一直走到末端 (左孩子
为空 )为止, 在走的过程中, 访问所遇结点, 并依次把
所遇结点进栈, 当左子树为空时, 从栈顶退出某结点,
并将指针指向该结点的右孩子 。 如此重复, 直到栈为
空或指针为空止 。
算法如下：
void preorder1(bitree *root)
{ bitree *p,*s[100];
int top=0; //top为栈顶指针
p=root;
while((p!=NULL)||(top>0))
{ while(p!=NULL)
{cout<<p->data<<" ";
s[++top]=p; p=p->lchild; }
p=s[top--]; p=p->rchild; }}
6.3.2中根遍历
所谓中根遍历, 就是根在中间, 先左子树, 然后根结
点, 最后右子树 。
1,递归遍历
中根遍历二叉树的递归遍历算法描述为：
若二叉树为空, 则算法结束；否则
⑴ 中根遍历左子树 ;
⑵ 输出根结点 ;
⑶ 中根遍历右子树 。
算法如下,
void inorder(biteee *root)
{ bitree *p;
p=root;
if (p!=NULL)
{ inorder(p->lchild);
cout<<p->data<<― ‖;
inorder(p->rchild);
}
}
2,非递归遍历
同样利用一个一维数组作栈, 来存贮二叉链表中结点,
算法思想为：
从二叉树根结点开始, 沿左子树一直走到末端 (左孩子为
空 )为止, 在走的过程中, 把依次遇到的结点进栈,待左
子树为空时,从栈中退出结点并访问,然后再转向它的右
子树 。 如此重复, 直到栈空或指针为空止 。
算法如下,
void inorder1( bitree *root)
{ bitree *p,*s[100]; //s为一个栈, top为栈顶指针
int top=0;
p=root;
while((p!=NULL)||(top>0))
{ while(p!=NULL)
{s[++top]=p;p=p->lchild;}
{p=s[top--];
cout<<p->data<<" ";
p=p->rchild; } }}
6.3.3 后根遍历
所谓后根遍历, 就是根在最后, 即先左子树, 然后右
子树, 最后根结点 。
1,递归遍历
后根遍历二叉树的递归遍历算法描述为：
若二叉树为空, 则算法结束 ;否则
（ 1） 后根遍历左子树,
（ 2） 后根遍历历子树 ;
（ 3） 访问根结点 。
算法如下,
void postorder( bitree *root)
{ bitree *p;
p=root;
if (p!=NULL)
{ postorder (p->lchild);
postorder (p->rchild);
cout<<p->data<<― ‖;
}
}
2.非递归遍历
利用栈来实现二叉树的后序遍历要比前序和中序遍历复
杂得多, 在后序遍历中, 当搜索指针指向某一个结点时,
不能马上进行访问, 而先要遍历左子树, 所以此结点应
先进栈保存, 当遍历完它的左子树后, 再次回到该结点,
还不能访问它, 还需先遍历其右子树,所以该 结点还必
须再次进栈, 只有等它的右子树遍历完后, 再次退栈时,
才能访问该结点 。 为了区分同一结点的两次进栈, 引入
一个栈次数的标志, 一个元素第一次进栈标志为 0,第
二次进标志为 1,并将标志存入另一个栈中, 当从标志
栈中退出的元素为 1时, 访问结点 。
后序遍历二叉树的非递归算法如下：
void postorder1( bitree *root)
{ bitree *p,*s1[100]; //s1栈存放树中结点
int s2[100],top=0,b; //s2栈存放进栈标志
p=root;
do
{ while(p!=NULL)
{s1[top]=p;s2[top++]=0; //第一次进栈标志为 0
p=p->lchild;}
if(top>0)
{b=s2[--top];
p=s1[top];
if(b==0)
{s1[top]=p;s2[top++]=1; //第二次进栈标志为 0
p=p->rchild;}
else
{cout<<p->data<<" ";
p=NULL;
}
}
}while(top>0);
}
例如, 可以利用上面介绍的遍历算法, 写出如图 6-11
所示二叉树的三种遍历序列为：
先序遍历序列,ABDGCEFH
中序遍历序列,BGDAECFH
后序遍历序列,GDBEHFCA
A
B C
D
E
F
G H
图 6 - 11 一棵二叉树
另外, 在编译原理中, 有用二叉 树来表示一个算术表
达式的情形 。 在一棵二叉树中, 若用操作数代表树叶,
运算符代表非叶子结点, 则这样的树可以代表一个算
术表达式 。 若按前序, 中序, 后序对该二叉树进行遍
历, 则得到的遍历序列分别称为前缀表达式 (或称波兰
式 ),中缀表达式, 后缀表达式 (递波兰式 )。 具体参见
图 6-12。
图 6-12所对应的前缀表达
式,-*abc。
图 6-12所对应的中缀表达
式,a*b-c。
图 6-12所对应的后缀
表达式,ab*c-。
a
c
b
*
-
图 6 - 12 表达式 a*b - c 代表的二叉树
二叉树所对应的遍历序列可以通过递归算法得到, 也
可以通过非递归算法得到 。 但有时要求直接写出序列,
故我们可以用图 6-13所示得到图 6-12的遍历序列 。 从二
叉树的三种递归遍历算法可以知道, 三种遍历算法不
同之处在于访问根结点和遍历左, 右子树的顺序不同,
若递归算法中去掉与递归无关的语句 ——访问根结点,
则三个遍历算法完全相同 。 于是对于二叉树的遍历,
可以看成是从根结点出发, 往左子树走, 若左子树为
空, 返回, 再进入右子树, 右子树访问完后, 再返回
根结点 。 这样一来每个结点都被访问三次, 若将按顺
序第一次访问的结点排列起来, 则得到该二叉树的先
序序列, 第二次访问的结点排列起来, 则得到该二叉
树的中序序列, 第三次访问的结点排列起来, 则得到
该二叉树的后序序列 。 对于图 6-13中, 第一次访问到
的结点用 △ 表示,第二次访问到的结点用 ○ 表示,第三次
访问的结点用 □ 表示,按虚线顺序将所有 △ 排列,则得到
先序序列为 -*abc,将所有 ○ 排列起来则得到中序序列为
a*b-c,将所有 □ 排列起来则得到后序序列 ab*c-。
1
2
* ^ c ^
^ a ^ ^ b ^
6.3.4遍历算法应用举例
例 6-5 由二叉树的前序序列和中序序列建立该二叉树
分析：若二叉树的任意两个结点的值都不相同, 则二
叉树的前序序列和中序序列能唯一确定一棵二叉树 。
另外, 由前序序列和中序序列的定义可知, 前序序列
中第一个结点必为根结点, 而在中序序列中, 根结点
刚好是左, 右子树的分界点, 因此, 可按如下方法建
立二叉树：
1.用前序序列的第一个结点作为根结点 ;
2.在中序序列中查找根结点的位置, 并以此为界将
中序序列划分为左, 右两个序列 (左, 右子树 );
3.根据左, 右子树的中序序列中的结点个数, 将前序
序列去掉根结点后的序列划分为左, 右两个序列, 它
们分别是左, 右子树的前序序列 ;
4.对左, 右子树的前序序列和中序序列递归地实施同
样方法, 直到所得左, 右子树为空 。
假设前序序列为 ABDGHCEFI,中序序列为 GDHBAECIF，
则得到的二叉树如下页所示
1。 A为根结点
A BDGH CEFI
GDHB A ECIF
BD
GH
CE
FI
A
2,B为左子树的根结点
B DGH
GDH B
CE
FI
DH
G
B
A
3,D为左子树的左子树的根
结点
A
B
G H
D
C E
F I
A
B
G H
D
C
FI E
4。 C为右子树的根结点
A
B
G H
D
C
F
I
E
5。 F为右子树的右
子树的根结点
C E FI
E C IF
例 6-6 按层次遍历一棵二叉树
对于一棵二叉树, 若规定遍历顺序为从上到下 (上层遍历
完才进入下层 ),从左到右 (同一层从左到右进行, 这样
的遍历称为按层次遍历：例 6-5的树的层次遍历序列为：
ABCDEFGHI。 下面用一个一维数组来模拟队列, 实现
二叉树的层次遍历 。
Void lorder (bitree * t)
{ bitree *q[maxsize],*p; // maxsize为最大容量
int f,r; // f,r类似于头尾指针
q[1]=t; f=r=1;
while (f<=r)
{ p=q[f]; f++; //出队
cout <<p->data;
if(p ->lchild!=NULL)
{ r++; q[r]=p->1child; } //入队
if (p->rchild!=NULL)
{ r++; q[r]=p->rchild;} //入队
} }
6.4线索二叉树
6.4.1 线索的概念
通过前面介绍的二叉树可知, 遍历二叉树实际上就是将
树中所有结点排成一个线性序列 (即非线性结构线性化 )，
在这样的线性序列中, 很容易求得某个结点在某种遍历
下的直接前驱和后继 。 然而, 有时我们希望不进行遍历
就能快速找到某个结点在某种遍历下的直接前驱和后继,
这样, 就应该把每个结点的直接前驱和直接后继记录下
来 。 为了做到这一点, 可以在原来的二叉链表结点中,
再增加两个指针域, 一个指向前驱, 一个指向后继, 但
这样做将会浪费大量存贮单元, 存贮空间的利用率相当
低 (一个结点中有 4个指针, 1个指左孩子, 1个指右孩子,
1个指前驱, 1个指后继 ),而原来的左, 右孩子域有许多
空指针又没有利用起来 。 为了不浪费存存贮空间, 我们
利用原有的孩子指针为空时来存放直接前驱和后继, 这
样的指针称为, 线索,, 加线索的过程称为线索化, 加
了线索的二叉树, 称为线索二叉树, 对应的二叉链表称
为线索二叉链表 。
在线索二叉树中，由于有了线索，无需遍历二叉树就
可以得到任一结点在某种遍历下的直接前驱和后继。
但是，我们怎样来区分孩子指针域中存放的是左、右
孩子信息还是直接前驱或直接后继信息呢?为此，在二
叉链表结点中，还必须增加两个标志域 ltag,rtag。
ltag和 rtag定义如下：
0 lchild域指向结点的左孩子
ltag=
1 lchild域指向结点在某种遍历下的直
接前驱
0 rchild域指向结点的右孩子
rtag=
1 rchild域指向结点在某种遍历下的直接后继
这样, 二叉链表中每个结点还是有 5个域, 但其中只
有 2个指针, 较原来的 4个指针要方便 。 增加线索后的
二叉链表结点结构可描述如下：
l c h i l d l t a g d a t a r t a g r c h i l d
2,线索的分类
另外, 根据遍历的不同要求, 线索二叉树可以分为：
（ 1） 前序前驱线索二叉树 (只需画出前驱 )
（ 2） 前序后继线索二叉树 (只需画出后继 )
（ 3） 前序线索二叉树 (前驱和后继都要标出 )
（ 4） 中序前驱线索二叉树 (只需画出前驱 )
（ 5） 中序后继线索二叉树 (只需画出中序后继 )
（ 6） 中序线索二叉树 (中序前驱和后继都要标出 )
（ 7） 后序前驱线索二叉树 (只需画出后序前驱 )
（ 8） 后序后继线索二叉树 (中需画出后序后驱 )
（ 9）后序线索二叉树 (后前驱和后继都要标出 )
6.4.2线索的描述
1,结点数据类型描述
struct Hbitree
{ elemtype data;
int ltag,rtag; //左, 右标志域
Hbitree *lchild,*rchild; } ;
2,线索的画法
在二叉树或二叉链表中, 若左孩子为空, 则画出它
的直接前驱, 右孩子为空时, 则画出它的直接后继,
左右孩子不为空时, 不需画前驱和后继 。 这样就得
到了线索二叉树或线索二叉链表 。
A
D
C B
0 A 0
1 B 1 0 C 1
r oot
1 D 1 ^
A
D
C B
N U LL
(a) 二叉树 (b ) 前序线索二叉树 (c) 前序线索二叉链表
图 6 - 15 前序线索示意图
前序序列为,ABCD
A
D
C B
N U LL
N U LL
（ a ） 中序二叉树 （ b ） 中序线索二叉链表
图 6 - 1 6 中序线索示意图
0 A 0
r oot
1 D 1
0 C 1
^
1 B 1
^
中序序列为,BADC
C
0 A 0
1 B 1
^ 0 C 1
1 D 1
root
D
B
A
N U LL
(a) 后序线索二叉树 ( b ) 后序线索二叉链表
图 6 - 17 后序线索示意图
后序序列为,BDCA
6.4.3 线索的算法实现
在此, 仅介绍中序线索二叉树的算法实现, 设为 P为
当前结点, pre为 p的前驱结点, 算法描述如下：
void inth (Hbitree *p)
//将 P所指二叉树中序线索化, 调用该函数之前, pre为
Null,而树中所有结点的 ltag和 rtag都为 0。
{ if (p!=NULL)
{ inth (p->lchild); 左子树线索化
if (p->lchild==NULLl)
p->ltag=1;
if (p->rchild==NULL) p->rtag;
if (pre!=NULL)
{ if(pre->rtag==1) pre->rchild=p;
if (p->ltag=1) p->lchild=pre;
}
pre=p;
inth (p->rchild); //右子树线索化
}
}
6.4.4 线索二叉树上的运算
1,线索二叉树上的查找
（ 1） 查找指定结点在中序线索二叉树中的的直接后继
若所找结点右标志 rtag=1,则右孩子域指向中序后继,
否则, 中序后继应为遍历右子树时的第一个访问结点,
即右子树中最左下的结点 （ 参见图 6-19） 。 从图 6-19
中可知, x的后继为 xk 。
X
X 1
X 2
X K
P
X 0
P
0 x
1
0 x
2
1 x
k
图 6 - 19 求中序后继示意图
（ 2） 查找指定结点在中序线索二叉树中的的直接 前
驱
若所找结点左标志 ltag=1,则左孩子域指向中序前驱,
否则, 中序前驱应为遍历左子树时的最后一个访问结
点, 即左子树中最右下的结点 （ 参见图 6-20） 。 从图
6-20中可知, x的前驱为 xk 。
X
X 1
X 2
x
k
P
0 X
P
x
1
0
x
2 0
x
k
1
图 6 - 20 求中序前驱示意图
(3) 查找指定点在前序线索二叉树中的直接后继
前序后继的查找比较方便，若Ｐ无左孩子，右链为
后继，否则左孩子为后继。
(4) 查找指定结点在后序线索二叉树中的直接前驱
后序前驱的查找也比较方便，若左孩子为空，左链指
前驱，否则，若右子树为空，左孩子指前驱，否则右
孩子为前驱。
求后序后继和前序前驱都比较麻烦, 在此不再作进一步
介绍 。
2．线索二叉树上的遍历
遍历某种次序的线索二叉树, 只要从该次序下的开始
结点出发, 反复找到结点在该次序下的后继, 直到后
继为空 。 这对于中序线索和前序线索二叉树很方便,
但对于后序线索二叉树较麻烦 (因求后序后继较麻烦 )。
故后序线索对于遍历没有什么意义 。
(1)前序遍历线索二叉树算法
void preorder2 (Hbitree *t)
Hbitree *p;
{ p=t; //找到开始结点
while (p!=NULL)
{ cout <<p->data;
p=preordernext(p); //调查函数找前序后继
}}
(2)中序遍历线索二叉树算法
void inorder2 (Hbitree *t)
{ Hbitree *p;p=t;
if (p!=NULL)
{ while (p->ltag==0) p=p->lchild; //找开始结点
while (p!=NULL)
{ cout <<p->data;
p= inordernext(p); //调用函数找中序后继
}}}
从上面算法可知, 线索二叉树上的遍历较一般二叉树
要方便得多 。 但是这种方便是以增加线索为代价的,
增加线索本身要花费大量时间 。 所以二叉树是以二链
表表示, 还是以线索二叉链表示, 可根据具体问题而
定 。
3,线索二叉树的扦入和删除
线索二树上的查找, 遍历都较一般二叉树方便, 但线
索二叉树也存在其缺点, 就扦入和删除运算而言, 线
索二叉树比一般二叉树的时间花费大, 因为除修改指
针外, 还要修改相应线索 。
线索二叉树的扦入和删除较麻烦，因此本书不再介绍
算法
６,５树和森林
６,５,１ 树的存储结构
1,双亲表示
它是以一组连续的存储单元来存放树中的结点, 每个结
点有两个域：一个是 data域, 存放结点信息, 另一个是
parent域, 用来存放双亲的位置 (指针 )。
A
D
C B
F E
H
G
a [ 0] a [ 1]
A B C D E F G H …
- 1 0 0 0 1 2 2 3 …
a [m a xs ine - 1] a [ 7]
da ta
pa r e nt
(a) 树的结构 ( b) 树的双亲表 示法
图 6 - 21 树的双亲表示示意图
该结构的具体描述见图 6-21。
2．孩子表示法
将一个结点所有孩子链接成一个单链表形，而树中有
若干个结点，故有若干个单链表，每个单链表有一个
表头结点，所有表头结点用一个数组来描述，具体描
述参见图 6-22
A
B
C
D
E ^
F ^
G ^
H ^
…
a[2]
a[3]
a[7]
a[1]
a[m axsize - 1]
…
1
2
3
^
4
^
5
6
^
7
^
图 6 - 22 树的孩子表示法（图 6 - 21 （ a ） 中树）示意图
3,双亲孩子表示法
将第 1,2两种方法结合起来, 则得到双亲孩子表示法,
具体参见图 6-23。
A - 1
B 0
C 0
D 0
E 1 ^
F 2 ^
G 2 ^
H 3 ^
4
^
1
2
3
^
5
6
^
7
^
图 6 - 23 树的双亲孩子表示法示意图
4 。 孩子兄弟表示法
类似于二叉链表, 但第一根链指向第一个孩子, 第二
根链指向下一个兄弟 。 将图 6-21(a)的树用孩子兄弟表
示法表示, 见图 6-24。
A ^
B
^
C
^ F D ^
^ G ^ ^ H ^
^ E ^
图 6 - 24 树的孩子兄弟表示法示意图
6.5.2 树, 森林和二叉树的转换
1,树转换成二叉树
可以分为三步：
（ 1） 连线
指相邻兄弟之间连线。
（ 2） 抹线
指抹掉双亲与除左孩子外其它孩子之间的连线。
（ 3） 旋转
只需将树作适当的旋转。
具体实现过程见图 6-25。
G
F
E
D
C
B
A A
B
E
C D
G
F
F
G
D
C
E
B
A
图 6 - 25 树转换成二叉树示意图
连线抹线
旋转
2,森林转换成二叉树
（ 1） 将森林中每一棵树分别转换成二叉树
这在刚才的树转换成二叉树中已经介绍过。
（ 2） 合并
使第 n棵树接入到第 n-1棵的右边并成为它的右子树, 第 n-
1 棵二叉树接入到第 n-2 棵的右边并成为它的右子树, …,
第 2棵二叉树接入到第 1棵的右边并成为它的右子树, 直到
最后剩下一棵二叉树为止 。
C
D
B
A
F
E
I
A
A
A
H
G
E
F
I
H
G
G
F
E
D
C
B
A
I
H
A
D
B
C
图 6 - 26 森林转换成二叉树示意图
合并
3,二叉树还原成树或森林
(1) 右链断开
将二叉树的根结点的右链及右链的右链等全部断开, 得到
若干棵无右子树的二叉树 。
具体操作见图 6-27(b)。
（ 2） 二叉树还原成树
将 （ 1） 中得到的每一棵二叉树都还原成树 （ 与树转换
成二叉树的步骤刚好相反 ） 。
具体操作步骤见图 6-27(c)。
G
D
A
B
C E
F
H
I
J
K
(a) 一个森林得到的二叉树
D
A
B
C E
G
F H I
J
K
( b) 断开根的右链得到 4 棵无右子树的二叉树
C
G
F H I
J
K
D
A
B
E
(c) 四棵二叉树还原成四棵树
H I
J
K
G
F
C D
A
B
E
(d ) 二叉树还原成森林
图 6 - 27 二叉树还原成森林过程
6.5.3 树和森林的遍历
在树和森林中, 一个结点可能有两棵以上的子树, 所
以不宜讨论它们的中序遍历, 即树和森林只有先序遍
历和后序遍历 。
1,先序遍历
（ 1） 树的先序遍历
若树非空，则先访问根结点，然后依次先序遍历各子树。
（ 2） 森林的先序遍历
若森林非空，则先访问森林中第一棵树的根结点，再先
序遍历第一棵树各子树，接着先序遍历第二棵树、第三
棵树,…,直到最后一棵树。
2,后序遍历
（ 1） 树的后序遍历
若树非空，则依次后序遍历各子树，最后访问根结点。
（ 2） 森林的后序遍历
按顺序后序遍历森林中的每一棵树。
另外，请注意，树和森林的先序遍历等价于它转换成的
二叉树的先序遍历，树和森林的后序遍历等价于它转换
成的二叉树的中序遍历。
6.6 哈夫曼树
6.6.1基本术语
1,路径和路径长度
在一棵树中, 从一个结点往下可以达到的孩子或子孙结
点之间的通路, 称为路径 。 通路中分支的数目称为路径
长度 。
若规定根结点的层数为 1,则从根结点到第 L层结点的路
径长度为 L-1。
2,结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值, 则这个数
值称为该结点的权 。
结点的带权路径长度为：从根结点到该结点之间的路径
长度与该结点的权的乘积。
3,树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长
度之和, 记为 wpl=, 其中 n 为叶子结点数目, wi
为第 i 个叶子结点的权值, li 为第 i 个叶子结点的路径
长度 。
?
?
n
i
iilw
1
6.6.2 哈夫曼树构造
1,哈夫曼树的定义
在一棵二叉树中, 若带权路径长度达到最小, 称这
样的二 叉树 为最 优二 叉树, 也 称为 哈夫 曼树
(Huffman tree)。
例如, 给定叶子结点的权分别为 1,3,5,7,则可以得到如
图 6-28所示的不同二叉树 。
从图 6-28可知, 图 6-28 (b)的长度最短, 图 6-28 (c)为较差
情形, 当然读者还可以自已构造出具有不同的 wpl情形来 。
5
7
1 3
1 7
5
3
1 3
7
5
( a ) w p l= 3 2 ( b ) w p l= 2 9 ( c ) w p l= 3 5
图 6 - 2 8 具有不同带 权路径长度的二叉树
2,哈夫曼树的构造
假设有 n个权值, 则构造出的哈夫曼树有 n个叶子结点 。
n个权值分别设为 w1,w2,…,wn,则哈夫曼树的构造规则为：
(1) 将 w1,w2,…,wn看成是有 n 棵树的森林 (每棵树仅有一
个结点 )；
(2) 在森林中选出两个根结点的权值最小的树合并, 作
为一棵新树的左, 右子树, 且新树的根结点权值为其左,
右子树根结点权值之和；
(3)从森林中删除选取的两棵树, 并将新树加入森林；
(4)重复 (2),(3)步，直到森林中只剩一棵树为止，该树
即为我们所求得的哈夫曼树。
下面给出哈夫曼树的构造过程, 假设给定的叶子结点的
权分别为 1,5,7,3,则构造哈夫曼树过程如图 6-29所示 。
从图 6-29可知, n 个权值构造哈夫曼树需 n-1次合并, 每
次合并, 森林中的树数目减 1,最后森林中只剩下一棵树,
即为我们求得的哈夫曼树 。
3 7 5 1 5 7
1 3
4
( a) 初如森林 ( b ) 一次合并后的森林
5
9
1 3
4
7
5
9
1 3
4
7
16
(c) 二次合并后的森林 ( d ) 三合并后的森林
图 6 - 29 哈夫曼树的构造过程
6.6.3哈夫曼树的应用
1,哈夫曼编码
通信中, 可以采用 0,1的不同排列来表示不同的字符, 称
为二进制编码 。 而哈夫曼树在数据编码中的应用, 是数据
的最小冗余编码问题, 它是数据压缩学的基础 。 若每个字
符出现的频率相同, 则可以采用等长的二进制编码, 若频
率不同, 则可以采用不等长的二进编码, 频率较大的采用
位数较少的编码, 频率较小的字符采用位数较多的编码,
这样可以使字符的整体编码长度最小, 这就是最小冗余编
码的问题 。 而哈夫曼编码就是一种不等长的二进制编
码, 且哈夫曼树是一种最优二叉树, 它的编码也是一种最
优编码, 在哈夫曼树中, 规定往左编码为 0,往右编码为 1，
则得到叶子结点编码为从根结点到叶子结点中所有路径中
0和 1的顺序排列 。
例如, 给定权 {1,5,7,3},得到的哈夫曼树及编码见
图 6-32 (假定权值就代表该字符名字 )。
7
16
9
4 5
1 3
(a) 哈夫曼树 ( b) 哈夫曼编码
图 6 - 32 构造哈夫曼树及哈夫曼编码
1 的编码 为,100
5 的编码为,11
7 的编码为,0
3 的编码为,101
2,哈夫曼译码
在通信中, 若将字符用哈夫曼编码形式发送出去, 对
方接收到编码后, 将编码还原成字符的过程, 称为哈
夫曼译码 。
