第5章 树
到目前为止,我们已经学习了线性结构和表结构。这些数据结构一般不适合于描述具
有分支结构的数据。在这种数据之间可能有祖先―后代、上级―下属、整体―部分等分支的
关系。本章引入的树形结构则是以分支关系定义的层次结构,是一类重要的非线性数据结
构,在计算机领域有着广泛应用。例如,在文件系统和数据库系统中,树是组织信息的重要
形式之一;在编译系统中,树用来表示源程序的语法结构;在算法设计与分析中,树还是刻画
程序动态性质的工具。本章讨论树、二叉树、森林,还要讨论堆与优先级队列,以及树的应用
实例,即Huffman树。
5.1 树的基本概念
树结构广泛存在于现实世界,例如,家族的家谱、公司的组织机构、书的章节等。在计算
机应用中,最为人们熟悉的就是磁盘中的文件夹,即文件目录。它包含文件和文件夹。
5.1.1 树的定义和术语
为了完整地建立有关树的基本概念,以下给出两种树的定义,即自由树(见图5.1)和有
根有序树。
自由树(freetree)。一棵自由树Tf 可定义为一个二元组Tf =(V,E ),其中V ={v1,
v2,…,vn}是由n (n>0)个元素组成的有限非空集合,称为顶点(vertex)集合,vi(1≤i≤
n)称为顶点。E = {(vi,vj)|vi,vj∈V,1≤i,j≤n}是由n-1个元素组成的序对集
合,称为边集合,E 中的元素(vi,vj)称为边(edge)或分支(branch)。E 使得Tf 成为一个
连通图(参见图论的有关定义)。
图5.1 自由树
有关自由树的研究是图论讨论的主要内容之
一,本书不讨论。本章讨论的树是有根有序树,它
们的顶点统一称为结点(node)。
有根树(rootedtree)。一棵有根树T ,简称树,
它是n(n≥0)个结点的有限集合。当n =0时,T
称为空树;否则,T 是非空树,记作
T = ., n =0
{r,T1,T2,…,Tm }, n >0 {
其中,r 是T 的一个特殊结点,称为根(root)。T1,T2,…,Tm 是除r 之外其他结点构成的
互不相交的m (m ≥0)个子集,每个子集也是一棵树,称为根的子树(subtree)。
每棵子树的根结点有且仅有一个直接前驱(即它的上层结点),但可以有0个或多个直
接后继(即它的下层结点)。m 称为r 的分支数。
图5.2给出树的逻辑表示,它形如一棵倒长的树。图5.2(a)是空树,一个结点也没有。
·174·
图5.是只有一个根结点的树,它的子树为空。图5.是有13个结点的树,其中
A
是
根结点,它一般都画在树的顶部。其余结点分成3个互不相交的子集:T1={B,E,F,
K
,L},T2={C,G},T3={D,
H
,I,J,
M
}。它们都是根结点
A
的子树。再看T1,它
的根是B,其余结点又分成2个互不相交的子集T11={E,
K
,L},T12={F},它们是T1
的子树。
2(b) 2(c)
图5.
2 树的示意图
由此可知,树的定义是一个递归的定义,即树的定义中又用到了树的概念。
除了图5.2所描述的逻辑表示外,在计算机系统和其他领域还有几种表示方法,如
图5.3所示。图5.a)
3(
图5.b) 图5.c)
3(是树的目录结构表示; 3(是树的集合文氏图表示; 3(是
树的凹入表表示;图5.d)是树的广义表表示。
图5.
3 树的其他表示方
法
下面介绍有关树的一些术语,它们在本书后续章节将经常遇到
。
(1)结点(e)。它包含数据项及指向其他结点的分支。例如在图5.c)中的树总共
nod2(
13个结点
2)结点的度
。为方便起见
(degre,每个数据项用单个字母表示
)。结点所拥有的子树棵数。
。
例如在图5.2(c)所示的树中,根A
(
·175·
的度为3,结点
E
的度为2,结点
K
,L,F,G,
M
,I,
J
的度为0。
(3)叶结点(又称终端结点。例如, 2(
leaf)。即度为0的结点, 在图5.c)所示的树中,
{
K
,L,F,G,
M
,I,J}构成树的叶结点的集合。
(4)分支结点(branc又称非终端结点。例如在图5.c)
h)。除叶结点外的其他结点, 2(
所示的树中,A,B,C,D,E,
H
就是分支结点。
(5)子女结点(child)。若结点
x
有子树,则子树的根结点即为结点
x
的子女。例如在
图52(c)所示的树中,结点
A
有3个子女,结点
B
有2个子女,结点
L
没有子女。(6(.) )父结点(prn它即为子女的父结点。例如在图5.c)
aet)。若结点
x
有子女, 2(所示
的树中,结点B,C,D,
E
有一个父结点,根结点
A
没有父结点。
(7)兄弟结点(sbig 2(所示的树
iln)。同一父结点的子女互称为兄弟。例如在图5.c)
中,结点B,C,
D
为兄弟,结点E,
F
也为兄弟,但结点F,G,
H
不是兄弟结点。
(8)祖先结点(ancestor)。从根结点到该结点所经分支上的所有结点。例如在
图5.c) 结点
L
的祖先为A,B,E。
2(所示的树中,
(9)子孙结点(descendant)。某一结点的子女,以及这些子女的子女都是该结点的子
孙。例如在图5.c)
leve
结点
B
的子孙为E,F,
K
,L。
2(所示的树中,
(10)结点所处层次(l)。简称结点的层次,即从根到该结点所经路径上的分支条
数。例如在图5.所示的树中,根结点在第1层,它的子女在第2层。树中任一结点的层
2(c)
次为它的父结点的层次加1。结点所处层次也称结点的深度。
(11)树的深度(h)。树中距离根结点最远的结点所处层次即为树的深度。空树的dept
图5.c)所示的树的深度为4。
深度为0,只有一个根结点的树的深度为1, 2(
(12)树的高度(height)。很多数据结构教科书定义树的高度等同于树的深度,本书则
从下向上定义高度。叶结点的高度为1,非叶结点的高度等于它的子女结点高度的最大值
加1,这样可定义树的高度等于根结点的高度。高度与深度计算的方向不同,但数值相等。
(13)树的度(
e)。树中结点的度的最大值。例如,图5.c)所示的树的度为3。
degr2(
(14)有序树(orderedtre)。树中结点的各棵子树T1,T2…是有次序的,即为有序树。
其中,T1为根的第1棵子树,T2为根的第2棵子树……。
(15)无序树(unorderedtre)。树中结点的各棵子树之间的次序是不重要的,可以互相
交换位置。
foresm
≥0)
(16)森林(t)。是m(棵树的集合。在自然界,树与森林是两个不同的概
念,但在数据结构中,它们之间的差别很小。删除一棵非空树的根结点,树就变成森林(不排
除空的森林);反之,若增加一个根结点,让森林中每棵树的根结点都变成它的子女,森林就
成为一棵树。
5.2
树的抽象数据类型
1.
下面给出树的抽象数据类型。利用树的抽象数据类型中提供的操作,就能实现许多应
用问题的解法。
程序5.
1 树的抽象数据类型
lT{
//(c) 对(a) 象:(r) 树(e ) 是由n(≥0)(s) 个结点组成的有限集合。在类界面中的position是树中结点的地址,
·176·
//在顺序存储方式下是下标型,在链接存储方式下是指针型。T是结点中存放数据的类型,要
//求所有结点的数据类型都是一致的
public:
positionRoot(); //返回根结点地址,若树为空,则返回0
BuildRoot(constT&value); //建立树的根结点
positionFirstChild(positionp); //返回p第一个子女地址,无子女返回0
positionNextSibling(positionp); //返回p下一兄弟地址,若无下一兄弟返回0
positionParent(positionp); //返回p父结点地址,若p为根返回0
TgetData(positionp); //函数返回结点p中存放的值
boolInsertChild(constpositionp,constT &value);
//在结点p下插入值为value的新子女,若插入失败,函数返回false,否则返回true
boolDeleteChild(positionp,inti);
//删除结点p的第i个子女及其全部子孙结点,若删除失败,则函数返回false;若删除
//成功,则函数返回true
voidDeleteSubTree(positiont); //删除以t为根结点的子树
boolIsEmpty(); //判断树是否为空。若空则返回true
voidTraversal(void(*visit)(positionp));
//遍历,visit是用户自编的访问结点p数据的函数
};
5.2 二 叉 树
二叉树(binarytree)是树形结构的一种重要类型。
5.2.1 二叉树的定义
二叉树。这个定义也是以递归形式给出的:一棵二叉树是结点的一个有限集合,该集
合或者为空,或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树
组成。
T = ., n =0
{r,TL,TR}, n >0 {
二叉树的子树TL、TR仍是二叉树,到达空子树时递归的定义结束。许多基于二叉树的
算法都利用了这个递归的特性。
二叉树的特点是每个结点最多有两个子女,分别称为该结点的左子女和右子女。就是
图5.4 二叉树的5种不同形态
说,在二叉树中不存在度大于2的结点,并且二
叉树的子树有左、右之分,其子树的次序不能颠
倒。因此,二叉树是分支数最大不超过2的有
根有序树。它可能有5种不同的形态,如图5.4
所示。图5.4(a)表示一棵空二叉树;图5.4(b)
是只有根结点的二叉树;根的左子树和右子树
都是空的;图5.4(c)是根的右子树为空的二叉树;图5.4(d)是根的左子树为空的二叉树;
·177·
图5.e) 二叉树的任意形状都是基于这5种形态经过
4(是根的两棵子树都不为空的二叉树
。
组合或嵌套而形成的
。
关于树的术语对于二叉树都适用
。
2.二叉树的性质
5.2
二叉树具有如下性质
:
性质5.1
在二叉树的第i(层最多有2i-
1
i≥1) 个结点。
【证明】用归纳法:当
i
=1时,非空二叉树在第1层只有一个根结点,21-1=20=1,
结论成立;现假定对于所有的j,1≤j<i,结论成立,即第
j
层上至多有2j-1个结点,则在第
i-1层至多有2i-2个结点。由于二叉树每个结点最多有2个子女,因此第
i
层上的最大结点
数为第i1层上最大结点数的2倍,即2×2i-2=i-1个结点,性质成立。
性质
-
5.深度为k(的二叉树最少有
k
2
个结点,最多有2k
-1个结点。
2
k≥0)
【证明】因为每层最少要有1个结点,因此,最少结点数为k。
k
=0是空二叉树的情
形,此时一个结点也没有,20-1=0,结论成立。k≥1是非空二叉树情形,具有层次
i
=1,
2,…,k。根据性质5.第
i
层最多有2i-1 则整个二叉树中所具有的最大结点数为
1, 个结点,
Σ(k) (第
i
层上最大结点数)= Σ(k) 2i-1=2k-1
i=1i=1
性质5.对任何一棵非空二叉树,如果其叶结点数为n0,度为2的非叶结点数为
3
n2,则
n0=n2+1
【证明】设二叉树中度为1的结点数为n1,因为二叉树只有度为0、度为1和度为2的
结点,所以树中结点总数为
n
=n0+n1+n2。再看二叉树中边(分支)条数e。因为二叉
树中除根结点没有父结点,进入它的边数为0之外,其他每一结点都有一个且仅有一个父结
点,进入它们的边数均为1,故二叉树中总的边数为
e
=n-1=n0+n1+n2-1。又由于
每个度为2的结点发出2条边,每个度为1的结点发出1条边,度为0的结点发出0条边,
因此总的边数为
e
=2n2+n1。将两个关于边的等式等同起来,有n0+n1+n2-1=
2n2+n1,消去n1和一个n2,得n0-1=n2,即n0=n2+1,结论成立。
其他一些性质是有关某些特殊二叉树的。为此,先定义两种特殊的二叉树。
满二叉树(uiayte)。深度为
k
的满二叉树是有21个结点的二叉树。在满
flbnrrk
二叉树中,每层结点都达到了最大个数。除最底层结点的度为0外,其他各层结点的度都为
2。图5.5(a)给出的就是高度为4的满二叉树。
图5.
5 两种特殊的二叉树
·178·
完全二叉树(completebinarytre) 如果一棵具有
n
个结点的深度为
k
的二叉树,它
的每个结点都与深度为
k
的满二叉树中编号为1~
n
的结点一一对应,则称这棵二叉树为
完全二叉树。图5.b) ~k-1层
5(给出的就是深度为4的完全二叉树。其特点:上面从第1
的所有各层的结点数都是满的,仅最下面第
k
层或是满的,或从右向左连续缺若干结点。
性质5.具有
n
个结点的完全二叉树的深度为
【证明】
4
2,
log2(n+1)。
k
-1,最少结点个数
由性质5.深度为
k
的完全二叉树最多结点个数n≤2n>2k-1-1,因此
2k-1-1<
n
≤2k-1
移项得
2k-1<
n
+1≤2k
取对数得
k-1<lgn+1)≤k
o2(
因为log2(1和
k
之间且不等于k-深度又只能是整数,因此
有
n+1)介于k-
gn+1)
1,
k=
结论成立。
lo2(
注意,此性质针对完全二叉树给出。但对如图5.
6所示的二
叉树也适合。这种二叉树称为理想平衡二叉树,其第1~k-1层
也是满的,达到最大结点个数,第
k
层的结点不一定集中在最左
边,可能分布在该层的各处。
+1,这与上述定义在n>0时
有的教科书定义
k =
6 理想平衡二叉树
等效,但
n
=0时不可用。
log2n
图5.
性质5.如果将一棵有
n
个结点的完全二叉树自顶向下,同
5
一层自左向右连续给结点编号1,2,3,…,n,然后按此结点编号将树中各结点顺序地存放
于一个一维数组中,并简称编号为
i
的结点为结点
i
(1≤i≤n),如图5.b)
下关系。
5(所示。则有以
(1)若
i
==1,则结点
i
为根,无父结点;若
i
>1,则结点
i
的父结点为结点
(2)若2×i
<=n,则结点
i
的左子女为结点2×i。
i/2。
(3)若2×i+1<=n,则结点
i
的右子女为结点2×i+1 。
(4)若结点编号
i
为奇数,且
i
!=1,它处于右兄弟位置,则它的左兄弟为结点i-1。
(5)若结点编号
i
为偶数,且
i
!=n,它处于左兄弟位置,则它的右兄弟为结点i+1 。
+1 。
(6)结点
i
所在层次为
log2i
5.3
二叉树的抽象数据类型
2.
下面给出二叉树的抽象数据类型。此定义只给出了二叉树操作的一个最小集合。可以
以它为基础增加其他相关的操作。
程序5.
2 二叉树的抽象数据类型
clasBinaryTre{ //对象:结点的有限集合,二叉树是有序树
public:
intHeight(); //返回树的深度或高度
·179·
intSize(); //返回树中结点个数
boolIsEmpty(); //判断二叉树是否为空
BinTreNode*Parent(BinTreNode*curent); //求指定结点的父结点
BinTreNode*LeftChild(BinTreNode*curent); //求指定结点的左子女
BinTreNode*RightChild(BinTreNode*cunt); //求指定结点的右子女
boolInsert(Titem); //(re) 按指定规则在树中插入新元素item
boolRve(Titem); //在树中删除元素item
bolFind(T(emo) item); //判断item是否在树中boolg(o) tData(T&item); //取得结点数据,通过item返回
BinTreN(e) ode*getRot(); //取根
voidPreOder(BinTre(o) Node*p); //前序遍历
voidInOrder(B(r) inTreNode*p); //中序遍历
voidPostOrder(BinTeNode*p); //后序遍历
};
voidLevelOrder(BinTre(r) Node*p); //层次序遍历
5.二叉树的存储表示
3
二叉树的存储结构有两种:数组方式和链表方式。
5.1
二叉树的数组存储表示
3.
二叉树的数组存储表示又称二叉树的顺序存储表示。
在数据处理过程中二叉树的大小和形态不发生剧烈的动态变化的场合,适宜采用数组
方式来表示二叉树的抽象数据类型。用数组方式存储二叉树的结构,就是将二叉树的数据
元素存储在一组连续的存储单元之内。这种方式可以用C++的数组来描述,用数组元素的
下标为索引,随机存取二叉树的结点。这种存储方案必须兼顾树形结构的特点,使各结点能
够方便地定位到它的父结点、左子女和右子女。
1.完全二叉树的数组存储表示
设有一棵完全二叉树,如图5.a) 对它所有的结点按照层次次序自顶向下,同一
7(所示,
层自左向右顺序编号1,2,…,n,就得到一个结点的顺序(线性)序列。按这个线性序列,
把这棵完全二叉树放在一个一维数组中,如图5.所示。
7(b)
在数组BinTrdta[中存放编号为
i
的完全二叉树
e.ai]
的结点。采用这种方式,可以利用完全二叉树的性质5.
5,
从一个结点的编号推算出它的父、子女、兄弟等结点的编
号,从而找到这些结点。这种存储表示是存储完全二叉树
最简单、最省存储的存储方式。
2.一般二叉树的数组表示
设有一棵一般二叉树,如图5.a) 需要将它存放
8(所示,
在一个一维数组中。为了能够简单地找到某一个结点的上
下左右的关系,也必须仿照完全二叉树那样,对二叉树的结
点进行编号。然后按其编号将它放到数组中去,如图5.
·180·
图5.7 完全二叉树的数组表示
(b)所示。在编号时,如遇到空子树,应在编号时假定有此子树进行编号,而在顺序存储时
当作有此子树那样把位置留出来。这样才能反映二叉树结点之间的相互关系,由其存储位
置找到它的父结点、子女结点、兄弟结点的位置,但这样做有可能会消耗大量的存储空间。
例如,图5.要求一个可存放31 个结点的一维数组,
9给出的单支二叉树, 但只在第0,2,6,
14,30 这几个位置存放有结点数据,其他大多数结点空间都空着,又不能压缩到一起,造成
很大空间浪费。
9 单支树
图5.8 一般二叉树的数组表示图5.
5.2
二叉树的链接存储表示
3.
数组表示法用于完全二叉树的存储表示非常有效,但表示一般二叉树,尤其是形态剧烈
变化的二叉树,存储空间的利用不是很理想。使用链接存储表示,可以克服这些缺点。
根据二叉树定义,二叉树的每个结点可以有两个分支,分别指向结点的左、右子树的根
结点(如果存在)。因此,二叉树的结点至少应当包括3个域,分别存放结点的数据data、左
子女结点指针letid和右子女结点指针rghtid, 10(所示。这种链表结构称
fChliChl如图5.a)
为二叉链表。使用这种结构,可以很方便地根据结点leftChild指针和rightChild指针找到
它的左子女和右子女,但要找到它的父结点很困难。为了便于查找任一结点的父结点,可以
在结点中再增加一个父结点指针域pt,它被称为三叉链表,如图5.b)所示。
aren10(
图5.
10 二叉树的链接存储表示
整个二叉树的链表有一个表头指针,它指向二叉树的根结点,其作用是当作树的访问
点。图5.和图5.分别是图5.所示二叉树的二叉链表和三叉链表。根据性
11(b) 11(c) 11(a)
质5.3很容易验证,在含有
n
个结点的二叉链表中有n+1 个空链指针域,这是因为在所有
结点的2n
个链指针域中只有n-1个存有边信息的缘故。三叉链表则有n+2 个空链指
·181·
针域。
图5.
11 二叉树的链接存储表示的示例
二叉链表和三叉链表可以是静态链表结构,即把链表存放在一个一维数组中,数组中每
一数组元素是一个结点,它包括了3个域:数据域data、左子女指针域leftChild和右子女指
针域rightChild。为寻找父结点方便,还可增加父指针域parent。指针域指示另一结点在数
组中的下标。也可以把链表分为两个数组存放,一个数组专存数据,另一个数组专存指针
(包括leftChild指针、rightChild指针和paren如图5.
t指针), 12所示。
图5.
12 静态链表结构
程序5.
3 利用二叉链表的二叉树类定
义
#inlde<isram.
cuoteh>
#inldtlb.
cue<sdih>
#inldseth>
cue<ar.
template<clasT>
structBinTreNode{ //二叉树结点类定义
Tdata; //数据域
BinTreNode<T> *leftChild,*rightChild; //左子女、右子女链域
BinTreNode():leftChild(NULL),rightChild(NULL){}
BinTreNode(Tx,BinTreNode<T> *l=NULL,BinTreNode<T> *r=NULL)
:data(eftChild(rightChild(r){}
x),ll)
,
}
;
template<clasT>
clasBinaryTre{ //二叉树类定
义
public:
·182·
BinaryTre():root(NULL){} //构造函数
BinaryTre(Tvalue):RefValue(value),root(NULL){} //构造函数
BinaryTre(BinaryTre<T>&s); //复制构造函数
~BinaryTre(){destroy(root);} //析构函数
boolIsEmpty(){returnroot==NULL;} //判断二叉树是否为空
BinTreNode<T> *Parent(BinTreNode<T> *curent) //返回父结点
if(root==NULL||root==curent)returnNULL;
elsereturnParent(root,curent)
;
intHeight(){returnHeight(root);} //返回树的高
度
intSize(){returnSize(root);} //返回树的结点
数
BinTreNode<T> *getRoot(){returnroot;} //取
根
voidsetRoot(BinTreNode<T> *p){root=p;} //修改
根
BinTreNode<T> *Search(Titem) //搜
索
{returnSearch(root,item);
}
intInserTitreturnInserroot
t(em){t(t,iem);} //插入新元
素
iraeirTicetBnTe(n,ot);
}
vodcetBnTe(n[]){raeiriro//从输入流读入建
树
vodpitirrnBnTe(ot);}
irnBnTe(){pitirro//用广义表输出二叉树
voidTraverse(){Traverse(root,1);} //用凹入表输出二叉树
voidcreateBinTre_pre(Tpre[]) //用扩展前序序列建树
{t,n);}
intn=0;createBinTre_pre(pre,roo
voidPreOrder(){PreOrder(root);} //前序遍
历
vodIreIrero//中序遍
历
inOdr(){nOdr(ot);
}
voidPostOrder(){PostOrder(root);} //后序遍
历
voidLevelOrder(); //层次序遍
历
voidPreOrder_iter(); //非递归前序遍
历
voidInOrder_iter(); //非递归中序遍
历
voidPostOrder_iter();
(
//非递归后序遍
历
friendbooloperator==BinaryTre<T>&s,BinaryTre<T>&t)
;
protected:
//重载操作:判等
BinTreNode<T> *root; //二叉树的根指
针
TRefValue; //数据输入停止标
志
voiddestroy(BinTreNode<T> *&subTre); //销毁子
树
voidcreateBinTre(Tin[],BinTreNode<T> *&subTre);
//从广义表串构建二叉树
voidcreateBinTre_pre(Tpre[],BinTreNode<T> *&subTre,int&n);
//从扩展前序序列构建二叉树
BinTreNode<T> *Parent(BinTreNode<T> *subTre,BinTreNode<T> *p);
//找父结
点
BinTreNode<T> *Search(BinTreNode<T> *p,Titem);//搜
索
intInsert(BinTreNode<T> *&subTre,Titem); //插
入
BinTreNode<T> *Copy(BinTreNode<T> *orignode); //复
制
intHeight(BinTreNode<T> *subTre); //求子树的高
度
intSize(BinTreNode<T> *subTre); //求子树的结点
数
·183·