第 五 章 树
5, 1 树的基本概念和术语
树型结构是一类重要的非线性数据结构,在 C语言中,从指
针应用的角度出发,介绍了一种特殊类型的树即二叉树的一些
基本概念和基本操作, 本章从更一般的角度来介绍树型数据结
构,
树的定义, 树是 n(n>=0)个结点的有限集,在一棵非空树中,
(1) 有且仅有一个特定的称为根的结点 ;
(2) 当 n>1时,其余 结点可分为 m(m>0)个互不相交的 有限集
mi TTTT,,,,,21 ??
,且 )1( miT
i ??
本身又是一棵树,称
为根的子树,
这是一个递归的 定义,即在树的定义中又用到了树,
下面给出 树型结构的一种较为直观的逻辑示意图,
(a)图是只有一个根结点的树；A
(a) (b)图是有 13个结点的树,其中 A是整棵树
的根结点,其余 结点分成三 个互不相交的A
B C
FE
K L
G H I J
D
M
(b)
子集, ? ?
? ?
? ?MJIHDT
GCT
LKFEBT
,,,,
,
,,,,
3
2
1
?
?
?
321,,TTT
是根 A的子树,且本身也
是一棵树, 例如,
1T
其根为 B,其余 结点
分成 互不相交的两个 子集, ? ?LKET,,
11 ?
? ?FT ?12,而 11T 中 E是根,{K}和 {L}是 E的两棵互不相交的
子树,其 本身又是只有一个根结点的树, 下面给出树型结
构的一些基本术语,
树的结点,包含一个数据元素及若干指向其子树的分
支,
结点的度,结点拥有的子树的棵数,
例如左图中,结点 A的度为 3,C的
度为 1,F的度为 0.
叶子,度为 0结点叫叶子,也叫终端
结点, 如 K,L,G,I,J,M都是树的叶
子,
A
B C
FE
K L
G H I J
D
M
非 终端结点,度不为 0结点,也叫分支结点, 除根结点外,分
支结点也叫内部结点,
树的度,树内各结点的度的最大值,如上图所示树的度为 3.
孩子,结点的子树的根称为该结点的孩子,相应地,该结点
称为孩子的双亲,如上图所示的树中,D为 A的子树的根,则
D是 A的孩子,A是 D的双亲,
兄弟,同一个双亲的孩子之间互称兄弟,例如,H,I,J互为兄弟
树支,连接两个结点的线段,又叫树边,
层次,从根开始定义,根
为第一层,
A
B C
FE
K L
G H I J
D
M
一层
二层
三层
四层
根的孩子为第
二层,若某结点在第 K层,
则其子树的根就在第 K+1
层,
深度,树结点的最大层次
数称为树的深度或高度, 上图所示树的深度为 4.
若树中结点的各子树从左至右是有次序的 (即不能互换 ),
则称该树为有序树,否则为无序树,
森林,是零棵或多棵树的集合, 对上图的树,只要把它的
根结点去掉,就可变成由三棵树组成的森林, 如下图,
B C
FE
K L
G H I J
D
M
5, 4 二叉树
5.4.1 二叉树的定义和性质
二叉树也称为二分树或二元树,是树型结构的一个重
要类型,
定义, 二叉树是 n>=0个结点的 有限集合,它或者是
空集 (即 n=0时 ),或者由一个根结点及两棵互不相交的分别
称为根的左子树和右子树的二叉树组成,
二叉树的定义也是递归的, 二叉树有下面五种基本
形态,
?
(a)空树
(b)只有根结点 (c)只有左子树 (d)只有右子树 (e)左右子树均不空
下面介绍二叉树的性质：
性质 1 在二叉树中,第 i 层的结点数最多为 ).1(2 1 ?? ii
证明, 应用归纳法有,1?i 时,为第 1层,只有一个根结点,
显然 122 01 ???i 正确 ; 现假定对所有的 ijj ??1,
命题成立,即第 j 层上至多有 12?j 个结点,那么可证明
ij ? 时命题也成立,由归纳假设, 第 1?i 层上至多有
22?i 个结点,因 二叉树中的每个 结点的度最大为 2,故在第 i
层上的最大结点数为第 1?i 层上的最大结点数的 2倍,即
.222 12 ?? ?? ii
性质 2深度为 k 的二叉树 至多有 )1(12 ?? kk 个 结点,
证明, 由 性质 1,深度为 k 的二叉树的 最大结点数为,
?
?
k
i 1
(第 i 层上的最大结点数 )
)1,2(121 )1(2 11
1
1 ????
?
??? ?
?
? aq
q
qa kkk
i
i ?
性质 3 对任何一棵二叉树 T,如果其终端结点数 (即叶子
数 )为
0n,度为 2的结点数为 2n,则 120 ?? nn
证明, 设 1n 为 二叉树 T中度为 1的结点数 (即此结点仅有一
棵子树,左子树或右子树,但非叶子 ),因 二叉树中所有
210 nnnn ???
结点的度均小于或等于 2,所以其结点数为,
又因为,除根 结点外,其余结点都有一条分支进入,设 B为
分支总数,则 1?? Bn,由于这些 分支是由度为 1或 2射出的
所以又有
21 2 nnB ??,从而 12 21 ??? nnn,故可得
1,12 2021210 ??????? nnnnnnn
下面介绍两种特殊形态的 二叉树,即满二叉树和完全二
叉树, 定义一棵深度为 k 且有 12 ?k 个结点的二叉树为满二叉
树,其特点是每一层上的结点数都是最大结点数,
下面这棵树就是满二叉树,对左边的满二叉树的结点进行
连续编号,并约定编号顺序是
从根结点起,自上而下,自左1
2
15
54
8 9 131211 14
3
10
6 7
至右 进行, 则可引出
另一种特殊形态的二
叉树,即完全二
叉树,
定义, 深度为
k 的有 n 个 结点的二叉树,当且仅当其每一 个 结点都与 深度
为 k 的 满二叉树中编号从 1至 n 的结点一一对应,称此二叉
树为完全二叉树, 如下图所示, 1
2
54
8 9
3
10
6 7
下图是非完全二叉树,即为一棵一般的二叉树,
有 10个结点的完全二叉树重新显示1
2
54
8 9 11
3
6 7
在下面,
1
2
54
8 9
3
10
6 7
可分析出其特点为,
1.叶子 结点只可能在第
k层及第 k -1层上出现
(k为最大层次 ).
2.对任一 结点,若其右分支下的子孙
的最大 层次为 l,则其左分支下的子孙
的最大 层次必为 l或 l+1.
3.完全二叉树可从满二
叉树中,自最高 层次向
上,且每层自右至
左顺序删除叶子 结
点而获得,
注意, 满足特点 1或 2,或满足特点 1和 2的 二
叉树不一定是完全二叉树,但若二叉树是完全二叉树,则一定
满足特点 1和 2,而从特点 3得到的二 叉树一定是完全二叉
树, 完全二叉树有两个重要的性质,
性质 4 具有 n个结点的完全二叉树的深度为 ? ? 1log 2 ?n
证明, 假设 具有 n个结点的完全二叉树的深度为 k,则由
性质 2和完全二叉树的 定义有 1212 1 ????? kk n (注意到
深度为 k,如 nk ??? 12 1,则深度为 )1?k 由上式得
kk n 22 1 ???,则 knk ???
2lo g1
,因为 k 是整数,所以
? ?,1lo g 2 ?? nk
性质 5 如果对一棵具有 n个结点的完全二叉树 (其深度为
? ? )1log 2 ?n 的结点按层序编号 (从第一层到第 ? ? 1log 2 ?n
层,每层从左到右 ),则对任一结点 )1( nii ??,有
(1) 如果 1?i,则结点是 二叉树的根,无双亲 ; 如果 1?i
则其 双亲是 结点 ? ?2/i
具有 12个结点的完全二叉树如下图所示,当
1
2
54
8 9 1211
3
10
6 7
6?i 时,
? ? ? ? 7,32/62/ ??? ii 时,
? ? ? ? ? ? 35.32/72/ ???i
显然 3是 6,7的 双亲,
(2) 如果 ni?2,则
结点 i 无左孩子为叶
子结点, 如果 ni?2,则 结点 i
的左孩子必定是,2i
(3) 如果 ni ??12,则 结点 i 无右孩子,如果 ni ??12,则 结点
i 的右孩子是 结点 12 ?i
课外习题, P.135第 2题, 第 3题
5.4.2 二叉树的存储结构
一, 二叉树的顺序存储结构 (顺序分配 )
所为顺序存储结构,是指用一组地址连续的存储单元存
储二叉树的数据元素,对上面这棵完全二叉树,可用向量
(一维数组 )作它的存储结构,如下图所示,
在顺序存储结构中,仅以结点在向量中的相对位置表示结
点之间的关系,因此适合于完全二叉树, 而对于一般二叉
树,如以顺序存储结构存储其数据元素,也必须按完全二
叉树的形式来存储,从而造成存储单元的浪费, 如有下图
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 6 7 8 9 10 11 12
一棵 一般二叉树,其对应的 顺序存储结构如下右图,
1 2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 0 0 0 0 6 7
1
2
54
3
6 7
6 7
8 9
10 11
上图中,“0”表示不存在此结点, 在
最坏的情况下,一个深度为 k且只有
k个 结点的单支树 (即树中无度为 2的结点 )却
需 12 ?k 个存储分量,k越大,浪费 越大,
二, 二叉树的链式存储结构 (链式分配 )
由二叉树的定义可知,其结点由一个数据域和分别指
向其左,右子树的两个分支构成,则表示 二叉树的链表中
的结点至少包含三个域, 数据域和左,右指针 域
lchild data rchild
用上图结点结构组成的 链表叫二叉链表,而二叉链表对下左
图所示的 二叉树的存储 结构见下右图,
A
B
ED
C
F G
A
B C
D E
F G
5.4.3 二叉树与树,森林之间的转换
可用多种形式的存储结构表示树,教材 P.98~P.100介
绍了三种形式的存储结构,在此主要介绍第二种形式,即
长子次弟表示法,也称二叉链表表示法, 以下面一棵树作
为例子,介绍 此种 表示法,
B C E
A
D
链 表中每个结点设三个域, 数
据 域, 长子指针域 (指向该结点的最左边的孩子 ) 和 次弟指
针域 (指向该结点的右邻第一个兄弟 ),如下所示,
fchild data nsib 从而 下面这棵树可用链表如下表示,
A ?
B?
C
D ??
E ??
B
C
E
A
D
再给出 一棵如下所示的二叉树
显然,其 链式存储
结构与树的长子次
弟的二叉链表存储
结构完全一致,
存储 存储
但对同一 二叉链
表的解释不一样,
解释 解释
一,二叉树与树 之间的转换
由前面树与二叉树的二叉链表存储结构的讨论可见,
只要约定一个存储规则,对于同一个二叉链表既可解释成
一般树,也可解释成相应的二叉树,反之亦然, 下面讨论
一般树与二叉树 之间 用手工相互 转换的方法,
(一 )一般树 转换为 二叉树
一棵一般树如下所示,
A
B C
FE G H
D
手工 转换成 二叉树的过程为,
1.在各 兄弟 之间加上虚线 ;
2.对每个结点,除了其最左边的一个孩
子外,抹掉该结点原先与其余孩子之
间的连线 ;
A
B C
FE G H
D
3.以树的根结点为轴心顺时针旋转,使
新加的虚线均向右斜并改成实线,原
有的连线均向左斜,
经过前面三步后,得转换成的 二叉树 如下左图,下面右图
A
B
C
F
E
G
H
D
A
B C
FE G H
D
为 转换前的一般树,
转换成的 二叉树有两个
特点, (1)根结点没有右
子树 ; (2)转换生成的 二
叉树中各结点的右孩子是原来树中该结点的
次弟,而该结点的左孩子还是原来树中该结
点的孩子,
(二 )二叉树 还原为 一般树 将二叉树 还原为 一般树的
步骤为, 1.加线, 若某结点是其双亲结点的
左孩子,则将该 结点的 右孩子以及从该右孩
子出发连续地沿着 结点的 右链不断搜索到的
右孩子都分别与该 结点的双亲结点用虚线相
连 ; 2.抹掉原 二叉树中所有 双亲结点与 右孩
的连线 ;
A
B
C
F
E
G
H
D 3.规整化成上面右图,
二,二叉树与森林 之间的转换
(一 )森林 转换为 二叉树
由三棵树组成的 森林如下图所示,
A
B C D F
E G
H I
J
其转换步骤为,
1.将各棵树转换为 二叉树 ;
A
B
C
D
F
E G
H
I
J
2.转换成的各棵 二叉树的根结点
无右子树, 然后将第二棵二叉树
作为第一棵二叉树根结点的右子
树,
A
B
C
D
F
E
G
H
I
J
第三棵二叉树作为第二棵二叉树
根结点的右子树,以此类推,
得转换后的 二叉树
如右图,且此二叉
树的根结点有右子
树,
(二 )二叉树 还原为 森林 二叉树如下左图所示,
A
B
C
D
F
E
G
H
I
J
将其还原为 森林的步骤为,
1,将根结点 A与其右孩子 E的连线以及从该
右孩子出发连续地沿着结点 E的右链不断搜
索到的所有右孩子间的连线全部 抹掉,得到
若干棵孤立的 二叉树, 如下左图,
A
B
C
D
F
E
G
H
I
J
2.将各棵孤立的 二叉树,按二叉树 还原一般
树的方法 还原为 树, 如下图,
A
B C D F
E G
H I
J
课外习题, P.135第 4题
5, 5 二叉树的遍历
在二叉树的一些应用中,常需对已生成的一棵二叉
树进行一系列操作,如查找,修改、插入、删除等, 而
在上述各种操作中,最基本的操作是逐个访问全部结点,
即遍历二叉树, 所谓遍历二叉树是指如何按某条搜索路
经对树中每个结点进行访问且仅访问一次, 对于一般的
线性结构来说这是一个容易解决的问题,而对于二叉树
这一非线性结构来说,遍历算法就复杂些, 由于二叉树
中每个结点除叶子结点外都可能有两棵子树,因次就要
寻找一种规律来系统地访问树中各个结点,
因二叉树的定义是递归的,一棵非空的二叉树可看
成由根结点,左子树和右子树这三个部分组成,因此若
能依次遍历 三个部分 中的各个结点,也就遍历了整棵二
叉树, 若以 L, T, R分别表示遍历 左子树,访问根结
结点,遍历右子树,则可有 TLR, LTR, LRT, TRL,
RTL, RLT六种遍历方案,其中前三种方案是按先左后
右的次序遍历根的两棵子树,而后三种方案是按先右后
左的次序遍历根的两棵子树,两者显然对称, 在此只讨
论前三种情况,分别称之为前序 (根 ) 遍历, 中序 (根 ) 遍
历 及 后序 (根 ) 遍历,
5.5.1 二叉链表结构的建立
建立二叉树二叉链表结构的方法中较为简单的一种
是利用完全二叉树的性质,但这种方法的缺点是对一般
二叉树来说有时会浪费大量的存储空间, 具体的算法及
程序请见教材 P.110~P.112.
5.5.2 前序遍历
前序遍历的规则为,
若二叉树非空,则进行下列操作,
1.访问根结点 ; 2.前序遍历左子树 ; 3.前序遍历右子树
以下面二叉树为例说明 前序遍历 二叉树的过程,
A
B C
FE
G H
D
A B D结点序列, G H E C F
教材 P.112上给出了前序遍历 二叉
树的递归函数,递归函数的优点是
程序简单明了,缺点是在执行递归
过程中需占用较多内存空间, 下面介绍非 递归 函数,
算法思想, 在前序遍历过程中,访问过根结点后应访问左
子树,这可沿着根结点的左指针向左子树方向走下去, 但
在访问完左子树后,应当接着向上退回,访问右子树, 但
在 二叉树的标准存储实现中,从 左子树退回根结点或从左
子树走向右子树的根结点都是不可能的, 要使程序能在访
问好根结点和左子树后,回访右子树,就要记住右子树根
结点的地址, 处于最深层的右子树根结点的地址最后登记
但它将最早取出回访,这一次序正好和栈的操作次序一致
可用栈来帮助前序遍历的非 递归 过程回访右子树,
由上面算法思想,可得如下一种前序遍历的非递归函数
void preorder(p)
NODE *p;
{ NODE *s[MAX]; int top;
top=0; s[top]=NULL;
while(p!=NULL)
{ printf(“%c”,p ->data);
if(p->rc!=NULL)
{ top++;
if(top>MAX-1)
{ printf(“栈上溢 \n”); return; }
else s[top]=p->rc;
}
if(p->lc!=NULL) p=p->lc;
else p=s[top--];
}
}
A
B C
FE
G H
D
1
2
3
4 5 6
7
8 步骤 访问的结点 栈中内容初态 ∧
1 A ∧,3
2 B ∧,3,5
3 D ∧,3,5,8
4 G ∧,3,5
5 H ∧,3
6 E ∧
7 C ∧,6
8 F ∧
结束 top=-1栈空
5.3.3 中序遍历
中序遍历的规则为,
若二叉树非空,则进行下列操作,
1.中序遍历左子树 ; 2.访问根结点 ; 3.中序遍历右子树,
以下面二叉树为例说明中序 遍历 二叉树的过程,
A
B C
FE
G H
D
结点序列,G D H B E A C F
按投影法也可得如上 结点序列
中序遍历二叉树的 递归和非递
归函数请见教材 P.113~P.115
G D H B E A C F
5.3.4 后序遍历
后 序遍历的规则为,
若二叉树非空,则进行下列操作,
1.后序遍历左子树 ; 2.后序遍历右子树 ; 3.访问根结点,
以下面二叉树为例说明 后 序 遍历 二叉树的过程,
A
B C
FE
G H
D
结点序列,G DH BE ACF
后 序遍历二叉树的 非递归函
数请见教材 P.116~P.117
上面三种对二叉树的遍
历,它们的时间复杂度均为
O(n).
补充内容, 由 二叉树的 中 序遍历 结点序列和前 序遍历
结点序列可唯一地确定一棵 二叉树 ; 而 由 二叉树的 中 序遍
历 结点序列和后 序遍历 结点序列也可唯一地确定一棵 二叉
树, 下面举例说明其方法,
设一棵二叉树的
前序遍历结点序列为,ABDEGCFH
中序遍历结点序列为,DBGEACHF 画出这棵 二叉树,
A
B
D E
G
F
C
H
前序的第一个元素一定为
整棵二叉树根结点,
故在中序遍历结点序列中,
结点 A的左边 结点必为结点
A的左子树上的 结点,
结点 A的右边 结点必为结点
A的右子树上的 结点,
再依此类推,即可画出这棵二叉树,
设一棵二叉树的后序遍历结点序列为,DGEBHFCA
中序遍历结点序列为,DBGEACHF 画出这棵 二叉树,
后序的最后一个元素一定为整棵二叉树根结点,
课外习题, P.135第 5题
P.136第 8题, 第 9题 (要求画出 二叉树 )
补充内容,树和森林的遍历
一、树的遍历
由于树中每个结点可有两棵以上的子树,因此有两种
遍历树的次序,
先序 (根 )遍历树, 先访问树的根结点,然后依次先序
遍历根的每棵子树,
例如有下示一棵树,
A
B C
FE G H
D
A
B
C
F
E
G
H
D
对其先序遍历的结点序列为,
A B E F C G D H
此树对应的二叉
树如左图,对此
二叉树进行先序
遍历的结点序列
为,
A B E F C G D H可见,树的先序遍历等价于先序
遍历该树对应的二叉树,
后序 (根 )遍历树,先依次后序遍历树的根结点的各子
树,然后访问根结点,
例如有下示一棵树,
A
B C
FE G H
D
A
B
C
F
E
G
H
D
对其后序遍历的结点序列为,
E F B G C H D A
此树对应的二叉
树如左图,对此
二叉树进行中序
遍历的结点序列
为,
E F B G C H D A
可见,树的后序遍历等价于中序遍历该树对应的二叉树,
二、森林的遍历
先序遍历森林, 若森林非空,则按下述规则遍历,
(1) 访问森林中第一棵树的根结点 ;
(2) 先序遍历第一棵树中根结点的子树森林 ;
(3) 先序遍历除去第一棵树后剩余的树构成的森林,
下图是由三棵树组成的森林 对其先序遍历的结点序列为,
ABCDEFGHIJ.
此森林对应的二叉树如下左图
A
B C D F
E G
H I
J
A
B
C
D
F
E
G
H
I
J
对此二叉树进行先序遍历的
结点序列为,ABCDEFGHIJ.
后序遍历森林, 若森林非空,则按下
述规则遍历,
(1) 后序遍历森林中第一棵树根结点
的子树森林 ;
(2) 访问森林中第一棵树的根结点 ;
(3) 后序遍历除去第一棵树后剩余的
树构成的森林,
对上面森林后序遍历的结点序列为,BCDAFEHJIG.
此森林对应的二叉树中序遍历的结点序列为,BCDAFEHJIG.
5, 7 二叉树的应用
5.7.1二叉排序树
二叉排序树是二叉树最简单的一种应用,其具体的应
用将在第七章中讨论,在此仅给出二叉排序树的定义和如
何手工生成二叉排序树,
二叉排序树的定义, 二叉排序树或者是一棵空树,或
者是一棵具有如下性质的二叉树,
(1) 若它的左子树非空,则左子树上所有结点的值均小于
根结点的值 ;
(2) 若它的右子树非空,则右子树上所有结点的值均大于
或等于根结点的值 ;
(3) 左, 右子树本身又各是一棵二叉排序树
结点可用其关键字值表示,设结点的初始序列为,
{ 10,3,19,8,18,2,7,8 },按二叉排序树的定义,建立过程如下,
10
3
8
8
18
19
7
2
对所 建立的二叉排序树进行中序遍历,得
结点序列为,2,3,7,8,8,10,18,19,为一非递
减有序的序列,
如果给出结点的初始序列就已非递减有序
则 建立的二叉排序树如下,
2
3
7
8
8
10
18
19
是一棵右单支树,
如 果给出结点的初始序列
就已递减有序,如 { 19,18,10,8,7,3,2 }
则二叉排序树为如右,
19
18
10
8
7
3
2
是棵左单支树,
由上面讨论可见,对于同一组结点
若 结点的初始序列不同,则得到的
二 叉排序树的形态也不同,但
对它们 中序遍历后得
到结点序列是一
样的,
课外习题,
P.136第 19题
5, 1 树的基本概念和术语
树型结构是一类重要的非线性数据结构,在 C语言中,从指
针应用的角度出发,介绍了一种特殊类型的树即二叉树的一些
基本概念和基本操作, 本章从更一般的角度来介绍树型数据结
构,
树的定义, 树是 n(n>=0)个结点的有限集,在一棵非空树中,
(1) 有且仅有一个特定的称为根的结点 ;
(2) 当 n>1时,其余 结点可分为 m(m>0)个互不相交的 有限集
mi TTTT,,,,,21 ??
,且 )1( miT
i ??
本身又是一棵树,称
为根的子树,
这是一个递归的 定义,即在树的定义中又用到了树,
下面给出 树型结构的一种较为直观的逻辑示意图,
(a)图是只有一个根结点的树；A
(a) (b)图是有 13个结点的树,其中 A是整棵树
的根结点,其余 结点分成三 个互不相交的A
B C
FE
K L
G H I J
D
M
(b)
子集, ? ?
? ?
? ?MJIHDT
GCT
LKFEBT
,,,,
,
,,,,
3
2
1
?
?
?
321,,TTT
是根 A的子树,且本身也
是一棵树, 例如,
1T
其根为 B,其余 结点
分成 互不相交的两个 子集, ? ?LKET,,
11 ?
? ?FT ?12,而 11T 中 E是根,{K}和 {L}是 E的两棵互不相交的
子树,其 本身又是只有一个根结点的树, 下面给出树型结
构的一些基本术语,
树的结点,包含一个数据元素及若干指向其子树的分
支,
结点的度,结点拥有的子树的棵数,
例如左图中,结点 A的度为 3,C的
度为 1,F的度为 0.
叶子,度为 0结点叫叶子,也叫终端
结点, 如 K,L,G,I,J,M都是树的叶
子,
A
B C
FE
K L
G H I J
D
M
非 终端结点,度不为 0结点,也叫分支结点, 除根结点外,分
支结点也叫内部结点,
树的度,树内各结点的度的最大值,如上图所示树的度为 3.
孩子,结点的子树的根称为该结点的孩子,相应地,该结点
称为孩子的双亲,如上图所示的树中,D为 A的子树的根,则
D是 A的孩子,A是 D的双亲,
兄弟,同一个双亲的孩子之间互称兄弟,例如,H,I,J互为兄弟
树支,连接两个结点的线段,又叫树边,
层次,从根开始定义,根
为第一层,
A
B C
FE
K L
G H I J
D
M
一层
二层
三层
四层
根的孩子为第
二层,若某结点在第 K层,
则其子树的根就在第 K+1
层,
深度,树结点的最大层次
数称为树的深度或高度, 上图所示树的深度为 4.
若树中结点的各子树从左至右是有次序的 (即不能互换 ),
则称该树为有序树,否则为无序树,
森林,是零棵或多棵树的集合, 对上图的树,只要把它的
根结点去掉,就可变成由三棵树组成的森林, 如下图,
B C
FE
K L
G H I J
D
M
5, 4 二叉树
5.4.1 二叉树的定义和性质
二叉树也称为二分树或二元树,是树型结构的一个重
要类型,
定义, 二叉树是 n>=0个结点的 有限集合,它或者是
空集 (即 n=0时 ),或者由一个根结点及两棵互不相交的分别
称为根的左子树和右子树的二叉树组成,
二叉树的定义也是递归的, 二叉树有下面五种基本
形态,
?
(a)空树
(b)只有根结点 (c)只有左子树 (d)只有右子树 (e)左右子树均不空
下面介绍二叉树的性质：
性质 1 在二叉树中,第 i 层的结点数最多为 ).1(2 1 ?? ii
证明, 应用归纳法有,1?i 时,为第 1层,只有一个根结点,
显然 122 01 ???i 正确 ; 现假定对所有的 ijj ??1,
命题成立,即第 j 层上至多有 12?j 个结点,那么可证明
ij ? 时命题也成立,由归纳假设, 第 1?i 层上至多有
22?i 个结点,因 二叉树中的每个 结点的度最大为 2,故在第 i
层上的最大结点数为第 1?i 层上的最大结点数的 2倍,即
.222 12 ?? ?? ii
性质 2深度为 k 的二叉树 至多有 )1(12 ?? kk 个 结点,
证明, 由 性质 1,深度为 k 的二叉树的 最大结点数为,
?
?
k
i 1
(第 i 层上的最大结点数 )
)1,2(121 )1(2 11
1
1 ????
?
??? ?
?
? aq
q
qa kkk
i
i ?
性质 3 对任何一棵二叉树 T,如果其终端结点数 (即叶子
数 )为
0n,度为 2的结点数为 2n,则 120 ?? nn
证明, 设 1n 为 二叉树 T中度为 1的结点数 (即此结点仅有一
棵子树,左子树或右子树,但非叶子 ),因 二叉树中所有
210 nnnn ???
结点的度均小于或等于 2,所以其结点数为,
又因为,除根 结点外,其余结点都有一条分支进入,设 B为
分支总数,则 1?? Bn,由于这些 分支是由度为 1或 2射出的
所以又有
21 2 nnB ??,从而 12 21 ??? nnn,故可得
1,12 2021210 ??????? nnnnnnn
下面介绍两种特殊形态的 二叉树,即满二叉树和完全二
叉树, 定义一棵深度为 k 且有 12 ?k 个结点的二叉树为满二叉
树,其特点是每一层上的结点数都是最大结点数,
下面这棵树就是满二叉树,对左边的满二叉树的结点进行
连续编号,并约定编号顺序是
从根结点起,自上而下,自左1
2
15
54
8 9 131211 14
3
10
6 7
至右 进行, 则可引出
另一种特殊形态的二
叉树,即完全二
叉树,
定义, 深度为
k 的有 n 个 结点的二叉树,当且仅当其每一 个 结点都与 深度
为 k 的 满二叉树中编号从 1至 n 的结点一一对应,称此二叉
树为完全二叉树, 如下图所示, 1
2
54
8 9
3
10
6 7
下图是非完全二叉树,即为一棵一般的二叉树,
有 10个结点的完全二叉树重新显示1
2
54
8 9 11
3
6 7
在下面,
1
2
54
8 9
3
10
6 7
可分析出其特点为,
1.叶子 结点只可能在第
k层及第 k -1层上出现
(k为最大层次 ).
2.对任一 结点,若其右分支下的子孙
的最大 层次为 l,则其左分支下的子孙
的最大 层次必为 l或 l+1.
3.完全二叉树可从满二
叉树中,自最高 层次向
上,且每层自右至
左顺序删除叶子 结
点而获得,
注意, 满足特点 1或 2,或满足特点 1和 2的 二
叉树不一定是完全二叉树,但若二叉树是完全二叉树,则一定
满足特点 1和 2,而从特点 3得到的二 叉树一定是完全二叉
树, 完全二叉树有两个重要的性质,
性质 4 具有 n个结点的完全二叉树的深度为 ? ? 1log 2 ?n
证明, 假设 具有 n个结点的完全二叉树的深度为 k,则由
性质 2和完全二叉树的 定义有 1212 1 ????? kk n (注意到
深度为 k,如 nk ??? 12 1,则深度为 )1?k 由上式得
kk n 22 1 ???,则 knk ???
2lo g1
,因为 k 是整数,所以
? ?,1lo g 2 ?? nk
性质 5 如果对一棵具有 n个结点的完全二叉树 (其深度为
? ? )1log 2 ?n 的结点按层序编号 (从第一层到第 ? ? 1log 2 ?n
层,每层从左到右 ),则对任一结点 )1( nii ??,有
(1) 如果 1?i,则结点是 二叉树的根,无双亲 ; 如果 1?i
则其 双亲是 结点 ? ?2/i
具有 12个结点的完全二叉树如下图所示,当
1
2
54
8 9 1211
3
10
6 7
6?i 时,
? ? ? ? 7,32/62/ ??? ii 时,
? ? ? ? ? ? 35.32/72/ ???i
显然 3是 6,7的 双亲,
(2) 如果 ni?2,则
结点 i 无左孩子为叶
子结点, 如果 ni?2,则 结点 i
的左孩子必定是,2i
(3) 如果 ni ??12,则 结点 i 无右孩子,如果 ni ??12,则 结点
i 的右孩子是 结点 12 ?i
课外习题, P.135第 2题, 第 3题
5.4.2 二叉树的存储结构
一, 二叉树的顺序存储结构 (顺序分配 )
所为顺序存储结构,是指用一组地址连续的存储单元存
储二叉树的数据元素,对上面这棵完全二叉树,可用向量
(一维数组 )作它的存储结构,如下图所示,
在顺序存储结构中,仅以结点在向量中的相对位置表示结
点之间的关系,因此适合于完全二叉树, 而对于一般二叉
树,如以顺序存储结构存储其数据元素,也必须按完全二
叉树的形式来存储,从而造成存储单元的浪费, 如有下图
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 6 7 8 9 10 11 12
一棵 一般二叉树,其对应的 顺序存储结构如下右图,
1 2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 0 0 0 0 6 7
1
2
54
3
6 7
6 7
8 9
10 11
上图中,“0”表示不存在此结点, 在
最坏的情况下,一个深度为 k且只有
k个 结点的单支树 (即树中无度为 2的结点 )却
需 12 ?k 个存储分量,k越大,浪费 越大,
二, 二叉树的链式存储结构 (链式分配 )
由二叉树的定义可知,其结点由一个数据域和分别指
向其左,右子树的两个分支构成,则表示 二叉树的链表中
的结点至少包含三个域, 数据域和左,右指针 域
lchild data rchild
用上图结点结构组成的 链表叫二叉链表,而二叉链表对下左
图所示的 二叉树的存储 结构见下右图,
A
B
ED
C
F G
A
B C
D E
F G
5.4.3 二叉树与树,森林之间的转换
可用多种形式的存储结构表示树,教材 P.98~P.100介
绍了三种形式的存储结构,在此主要介绍第二种形式,即
长子次弟表示法,也称二叉链表表示法, 以下面一棵树作
为例子,介绍 此种 表示法,
B C E
A
D
链 表中每个结点设三个域, 数
据 域, 长子指针域 (指向该结点的最左边的孩子 ) 和 次弟指
针域 (指向该结点的右邻第一个兄弟 ),如下所示,
fchild data nsib 从而 下面这棵树可用链表如下表示,
A ?
B?
C
D ??
E ??
B
C
E
A
D
再给出 一棵如下所示的二叉树
显然,其 链式存储
结构与树的长子次
弟的二叉链表存储
结构完全一致,
存储 存储
但对同一 二叉链
表的解释不一样,
解释 解释
一,二叉树与树 之间的转换
由前面树与二叉树的二叉链表存储结构的讨论可见,
只要约定一个存储规则,对于同一个二叉链表既可解释成
一般树,也可解释成相应的二叉树,反之亦然, 下面讨论
一般树与二叉树 之间 用手工相互 转换的方法,
(一 )一般树 转换为 二叉树
一棵一般树如下所示,
A
B C
FE G H
D
手工 转换成 二叉树的过程为,
1.在各 兄弟 之间加上虚线 ;
2.对每个结点,除了其最左边的一个孩
子外,抹掉该结点原先与其余孩子之
间的连线 ;
A
B C
FE G H
D
3.以树的根结点为轴心顺时针旋转,使
新加的虚线均向右斜并改成实线,原
有的连线均向左斜,
经过前面三步后,得转换成的 二叉树 如下左图,下面右图
A
B
C
F
E
G
H
D
A
B C
FE G H
D
为 转换前的一般树,
转换成的 二叉树有两个
特点, (1)根结点没有右
子树 ; (2)转换生成的 二
叉树中各结点的右孩子是原来树中该结点的
次弟,而该结点的左孩子还是原来树中该结
点的孩子,
(二 )二叉树 还原为 一般树 将二叉树 还原为 一般树的
步骤为, 1.加线, 若某结点是其双亲结点的
左孩子,则将该 结点的 右孩子以及从该右孩
子出发连续地沿着 结点的 右链不断搜索到的
右孩子都分别与该 结点的双亲结点用虚线相
连 ; 2.抹掉原 二叉树中所有 双亲结点与 右孩
的连线 ;
A
B
C
F
E
G
H
D 3.规整化成上面右图,
二,二叉树与森林 之间的转换
(一 )森林 转换为 二叉树
由三棵树组成的 森林如下图所示,
A
B C D F
E G
H I
J
其转换步骤为,
1.将各棵树转换为 二叉树 ;
A
B
C
D
F
E G
H
I
J
2.转换成的各棵 二叉树的根结点
无右子树, 然后将第二棵二叉树
作为第一棵二叉树根结点的右子
树,
A
B
C
D
F
E
G
H
I
J
第三棵二叉树作为第二棵二叉树
根结点的右子树,以此类推,
得转换后的 二叉树
如右图,且此二叉
树的根结点有右子
树,
(二 )二叉树 还原为 森林 二叉树如下左图所示,
A
B
C
D
F
E
G
H
I
J
将其还原为 森林的步骤为,
1,将根结点 A与其右孩子 E的连线以及从该
右孩子出发连续地沿着结点 E的右链不断搜
索到的所有右孩子间的连线全部 抹掉,得到
若干棵孤立的 二叉树, 如下左图,
A
B
C
D
F
E
G
H
I
J
2.将各棵孤立的 二叉树,按二叉树 还原一般
树的方法 还原为 树, 如下图,
A
B C D F
E G
H I
J
课外习题, P.135第 4题
5, 5 二叉树的遍历
在二叉树的一些应用中,常需对已生成的一棵二叉
树进行一系列操作,如查找,修改、插入、删除等, 而
在上述各种操作中,最基本的操作是逐个访问全部结点,
即遍历二叉树, 所谓遍历二叉树是指如何按某条搜索路
经对树中每个结点进行访问且仅访问一次, 对于一般的
线性结构来说这是一个容易解决的问题,而对于二叉树
这一非线性结构来说,遍历算法就复杂些, 由于二叉树
中每个结点除叶子结点外都可能有两棵子树,因次就要
寻找一种规律来系统地访问树中各个结点,
因二叉树的定义是递归的,一棵非空的二叉树可看
成由根结点,左子树和右子树这三个部分组成,因此若
能依次遍历 三个部分 中的各个结点,也就遍历了整棵二
叉树, 若以 L, T, R分别表示遍历 左子树,访问根结
结点,遍历右子树,则可有 TLR, LTR, LRT, TRL,
RTL, RLT六种遍历方案,其中前三种方案是按先左后
右的次序遍历根的两棵子树,而后三种方案是按先右后
左的次序遍历根的两棵子树,两者显然对称, 在此只讨
论前三种情况,分别称之为前序 (根 ) 遍历, 中序 (根 ) 遍
历 及 后序 (根 ) 遍历,
5.5.1 二叉链表结构的建立
建立二叉树二叉链表结构的方法中较为简单的一种
是利用完全二叉树的性质,但这种方法的缺点是对一般
二叉树来说有时会浪费大量的存储空间, 具体的算法及
程序请见教材 P.110~P.112.
5.5.2 前序遍历
前序遍历的规则为,
若二叉树非空,则进行下列操作,
1.访问根结点 ; 2.前序遍历左子树 ; 3.前序遍历右子树
以下面二叉树为例说明 前序遍历 二叉树的过程,
A
B C
FE
G H
D
A B D结点序列, G H E C F
教材 P.112上给出了前序遍历 二叉
树的递归函数,递归函数的优点是
程序简单明了,缺点是在执行递归
过程中需占用较多内存空间, 下面介绍非 递归 函数,
算法思想, 在前序遍历过程中,访问过根结点后应访问左
子树,这可沿着根结点的左指针向左子树方向走下去, 但
在访问完左子树后,应当接着向上退回,访问右子树, 但
在 二叉树的标准存储实现中,从 左子树退回根结点或从左
子树走向右子树的根结点都是不可能的, 要使程序能在访
问好根结点和左子树后,回访右子树,就要记住右子树根
结点的地址, 处于最深层的右子树根结点的地址最后登记
但它将最早取出回访,这一次序正好和栈的操作次序一致
可用栈来帮助前序遍历的非 递归 过程回访右子树,
由上面算法思想,可得如下一种前序遍历的非递归函数
void preorder(p)
NODE *p;
{ NODE *s[MAX]; int top;
top=0; s[top]=NULL;
while(p!=NULL)
{ printf(“%c”,p ->data);
if(p->rc!=NULL)
{ top++;
if(top>MAX-1)
{ printf(“栈上溢 \n”); return; }
else s[top]=p->rc;
}
if(p->lc!=NULL) p=p->lc;
else p=s[top--];
}
}
A
B C
FE
G H
D
1
2
3
4 5 6
7
8 步骤 访问的结点 栈中内容初态 ∧
1 A ∧,3
2 B ∧,3,5
3 D ∧,3,5,8
4 G ∧,3,5
5 H ∧,3
6 E ∧
7 C ∧,6
8 F ∧
结束 top=-1栈空
5.3.3 中序遍历
中序遍历的规则为,
若二叉树非空,则进行下列操作,
1.中序遍历左子树 ; 2.访问根结点 ; 3.中序遍历右子树,
以下面二叉树为例说明中序 遍历 二叉树的过程,
A
B C
FE
G H
D
结点序列,G D H B E A C F
按投影法也可得如上 结点序列
中序遍历二叉树的 递归和非递
归函数请见教材 P.113~P.115
G D H B E A C F
5.3.4 后序遍历
后 序遍历的规则为,
若二叉树非空,则进行下列操作,
1.后序遍历左子树 ; 2.后序遍历右子树 ; 3.访问根结点,
以下面二叉树为例说明 后 序 遍历 二叉树的过程,
A
B C
FE
G H
D
结点序列,G DH BE ACF
后 序遍历二叉树的 非递归函
数请见教材 P.116~P.117
上面三种对二叉树的遍
历,它们的时间复杂度均为
O(n).
补充内容, 由 二叉树的 中 序遍历 结点序列和前 序遍历
结点序列可唯一地确定一棵 二叉树 ; 而 由 二叉树的 中 序遍
历 结点序列和后 序遍历 结点序列也可唯一地确定一棵 二叉
树, 下面举例说明其方法,
设一棵二叉树的
前序遍历结点序列为,ABDEGCFH
中序遍历结点序列为,DBGEACHF 画出这棵 二叉树,
A
B
D E
G
F
C
H
前序的第一个元素一定为
整棵二叉树根结点,
故在中序遍历结点序列中,
结点 A的左边 结点必为结点
A的左子树上的 结点,
结点 A的右边 结点必为结点
A的右子树上的 结点,
再依此类推,即可画出这棵二叉树,
设一棵二叉树的后序遍历结点序列为,DGEBHFCA
中序遍历结点序列为,DBGEACHF 画出这棵 二叉树,
后序的最后一个元素一定为整棵二叉树根结点,
课外习题, P.135第 5题
P.136第 8题, 第 9题 (要求画出 二叉树 )
补充内容,树和森林的遍历
一、树的遍历
由于树中每个结点可有两棵以上的子树,因此有两种
遍历树的次序,
先序 (根 )遍历树, 先访问树的根结点,然后依次先序
遍历根的每棵子树,
例如有下示一棵树,
A
B C
FE G H
D
A
B
C
F
E
G
H
D
对其先序遍历的结点序列为,
A B E F C G D H
此树对应的二叉
树如左图,对此
二叉树进行先序
遍历的结点序列
为,
A B E F C G D H可见,树的先序遍历等价于先序
遍历该树对应的二叉树,
后序 (根 )遍历树,先依次后序遍历树的根结点的各子
树,然后访问根结点,
例如有下示一棵树,
A
B C
FE G H
D
A
B
C
F
E
G
H
D
对其后序遍历的结点序列为,
E F B G C H D A
此树对应的二叉
树如左图,对此
二叉树进行中序
遍历的结点序列
为,
E F B G C H D A
可见,树的后序遍历等价于中序遍历该树对应的二叉树,
二、森林的遍历
先序遍历森林, 若森林非空,则按下述规则遍历,
(1) 访问森林中第一棵树的根结点 ;
(2) 先序遍历第一棵树中根结点的子树森林 ;
(3) 先序遍历除去第一棵树后剩余的树构成的森林,
下图是由三棵树组成的森林 对其先序遍历的结点序列为,
ABCDEFGHIJ.
此森林对应的二叉树如下左图
A
B C D F
E G
H I
J
A
B
C
D
F
E
G
H
I
J
对此二叉树进行先序遍历的
结点序列为,ABCDEFGHIJ.
后序遍历森林, 若森林非空,则按下
述规则遍历,
(1) 后序遍历森林中第一棵树根结点
的子树森林 ;
(2) 访问森林中第一棵树的根结点 ;
(3) 后序遍历除去第一棵树后剩余的
树构成的森林,
对上面森林后序遍历的结点序列为,BCDAFEHJIG.
此森林对应的二叉树中序遍历的结点序列为,BCDAFEHJIG.
5, 7 二叉树的应用
5.7.1二叉排序树
二叉排序树是二叉树最简单的一种应用,其具体的应
用将在第七章中讨论,在此仅给出二叉排序树的定义和如
何手工生成二叉排序树,
二叉排序树的定义, 二叉排序树或者是一棵空树,或
者是一棵具有如下性质的二叉树,
(1) 若它的左子树非空,则左子树上所有结点的值均小于
根结点的值 ;
(2) 若它的右子树非空,则右子树上所有结点的值均大于
或等于根结点的值 ;
(3) 左, 右子树本身又各是一棵二叉排序树
结点可用其关键字值表示,设结点的初始序列为,
{ 10,3,19,8,18,2,7,8 },按二叉排序树的定义,建立过程如下,
10
3
8
8
18
19
7
2
对所 建立的二叉排序树进行中序遍历,得
结点序列为,2,3,7,8,8,10,18,19,为一非递
减有序的序列,
如果给出结点的初始序列就已非递减有序
则 建立的二叉排序树如下,
2
3
7
8
8
10
18
19
是一棵右单支树,
如 果给出结点的初始序列
就已递减有序,如 { 19,18,10,8,7,3,2 }
则二叉排序树为如右,
19
18
10
8
7
3
2
是棵左单支树,
由上面讨论可见,对于同一组结点
若 结点的初始序列不同,则得到的
二 叉排序树的形态也不同,但
对它们 中序遍历后得
到结点序列是一
样的,
课外习题,
P.136第 19题
