第5章树和二叉树
前面介绍了几种常见的线性结构,本章介绍的树和二叉树与第6章介绍的
图属于非线性数据结构。线性结构中的每个元素有唯一的前驱元素和唯一的后
继元素,而非线性结构中元素间前驱和后继的关系并不具有唯一性。其中,树中
结点间的关系是前驱结点唯一而后继结点不唯一,即结点间是一对多的关系;图
中结点的前驱结点和后继结点都不唯一,即结点间是多对多的关系。树的应用
非常广泛,特别是在需要进行大量数据处理的时候,如在文件系统、编译系统、目
录组织等方面,显得更加突出。
本章学习重难点:
第
5
章 树和二叉树
5.树
1
树是一种非线性的数据结构,树中的元素之间具有一对多的层次关系。
5.1.1 树的定义
树(
e)是n(个结点的有限集合。其中,当n=0时,称为空树;当n>0时,称为
非空树。树满足以下条件:
trn≥0)
(1)有且只有一个称为根(t)的结点。
roo
(2)当n>1时,其余n-1个结点可以划分为
m
个有限集合T1,T2,…,Tm
,且这
m
个
有限集合互不相交,其中Ti(1≤i≤m)又是一棵树,称为根的子树。
图5-1给出了一棵树的逻辑结构,它像一棵倒立的树。
图5-
1
树的逻辑结构
在图5-1中,
A
为根结点。左边的树只有根结点。右边的树有14个结点,除了根结点,
其余的13个结点分为3个不相交的子集:T1={B,E,
K
,L}、C,
H
,
M
,
F,T2={G,I,
N
}
和T3={D,J}。其中,T1、T2 和T3 是根结点
A
的子树,并且它们本身也是一棵树。例
如,T2 的根结点是C,其余的5个结点又分为3个不相交的子集:T21={G,
M
}、T22=
{和T23={
N
}。T21 、T22和T23是T2 的子树。
G
是T21的根结点,{是
G
的子树;
H
} I,
M
}
I
是T23的根结点,{
N
}是
I
的子树。
表5-1是树的基本概念。
表5-
1
树的基本概念
概念定义举例
树的结点包含一个数据元素及若干指向子树分支的信息A、B、
C
等都是结点
结点的度一个结点拥有子树的个数结点
C
有3个子树,度为3
叶子结点也称为终端结点,是没有子树的结点,它的度为0
K
、L、F、
M
、
H
、
N
和
J
都是叶子结点
分支结点也称为非终端结点,是度不为0的结点B、C、D、
E
等都是分支结点
孩子结点一个结点的子树的根结点
B
是
A
的孩子结点,
E
是
B
的孩子结
点,
H
是
C
的孩子结点
双亲结点
也称父结点,如果一个结点存在孩子结点,则该
结点就称为孩子结点的双亲结点
A
是
B
的双亲结点,
B
是
E
的双亲结
点,
I
是
N
的双亲结点
139
数据结构(Python
语言描述)
续表
概念定义举例
子孙结点
在一个根结点的子树中的任何一个结点都称为
该根结点的子孙结点
{G,H,I,M,N}是
C
的子树,子树中的结
点G、H、I、
M
和
N
都是
C
的子孙结点
祖先结点
从根结点开始到达一个结点经过的所有分支结
点都称为该结点的祖先结点
N
的祖先结点为A、
C
和
I
兄弟结点
一个双亲结点的所有孩子结点之间互为兄弟
结点
E
和
F
是
B
的孩子结点,因此,
E
和
F
互为兄弟结点
树的度树中所有结点的度的最大值
结点
C
的度为3,结点
A
的度为3,这两
个结点的度是树中度最大的结点,因此
树的度为3
结点的层次
从根结点开始,根结点为第一层,根结点的孩子
结点为第二层,以此类推,如果某一个结点是第
L
层,则其孩子结点位于第L+1 层
在图5-1所示的树中,
A
的层次为1,
B
的层次为2,
G
的层次为3,
M
的层次
为4
树的深度也称为树的高度,树中所有结点的层次最大值图5-1所示的树的深度为4
有序树如果树中各个子树有先后次序,则称之为有序树
无序树如果树中各个子树没有先后次序,则称之为无序树
森林
m
棵互不相交的树构成一个森林。如果把一棵非
空树的根结点删除,则该树就变成了一个森林,森
林中的树由原来的根结点和各个子树构成。如果
给一个森林加上一个根结点,将该森林中的树变
成该根结点的子树,则该森林就转换成一棵树
5.1.2 树的逻辑表示
树的逻辑表示可分为4种:树形表示法、文氏图表示法、广义表表示法和凹入表示法。
(1)树形表示法。图5-1就是树形表示法。树形表示法是最常用的一种逻辑表示,它
能直观、形象地表示出树的逻辑结构,能够清晰地反映出树中结点之间的逻辑关系。树中的
结点使用圆圈表示,结点间的关系使用直线表示,位于直线上方的结点是双亲结点,位于直
线下方的结点是孩子结点。
(2)文氏图表示法。文氏图是利用数学中的集合描述树的逻辑关系的图。图5-1的树
采用文氏图表示如图5-2所示。
(3)广义表表示法。可以采用广义表的形式表示树的逻辑结构,广义表的子表表示结
点的子树。图5-1的树利用广义表表示如下所示:
(A(E(L),C(
M
),I(D(
B(
K
,F),G(
H
,
N
)),J)))
(4)凹入表示法。图5-1的树采用凹入表示法如图5-3所示
。
在这4种树的表示法中,树形表示法最为常用
。
5.1.3 树的抽象数据类型
树的抽象数据类型定义了树中的数据对象、数据关系及基本操作。树的抽象数据类型
描述如表5-2所示。
140
第
5
章 树和二叉树
图5-
2
树的文氏图表示法图5-
3
树的凹入表示法
表5-
2
树的抽象数据类型描述
数据对象
D
是具有相同特性的数据元素的集合
数据关系
若
D
为空集,则称为空树。若
D
仅含一个数据元素,则
R
为空集,否则R={
H
},
H
是如下
二元关系:
(1)在
D
中存在唯一的称为根的数据元素root,它在关系
H
下无前驱结点。
(2)若D-{root}≠.,则存在D-{root}的一个划分D1,D2,…,Dm
(m>0),对任意的j≠
k
(1≤j,k≤m)有Dj
∩Dk
=.,且对任意的i(1≤i≤m),唯一存在数据元素xi
∈Di
,有<
root,xi
>∈
H
。
(3)对应于D-{root}的划分,
H
-{<root,x1>},<root,x2>,…,<root,xn
>}有唯一的
一个划分H1,H2,…,Hm
(m>0),对任意的j≠k(1≤j,k≤m)有Dj
∩Dk
=.,且对任意的
i(1≤i≤m),Hi
是Di
上的二元关系,(Di
,{Hi})是一棵符合本定义的树,称为root的子树
InitTre(&T) 初始条件:树
T
不存在。
操作结果:构造空树
T
DestroyTre(&T) 初始条件:树
T
存在。
操作结果:销毁树
T
CreateTre(&T) 初始条件:树
T
不存在。
操作结果:根据给定条件构造树
T
TreEmpty(T) 初始条件:树
T
存在。
操作结果:若树
T
为空树,则返回True;否则返回False
Root(T) 初始条件:树
T
存在。
操作结果:若树
T
非空,则返回树的根结点;否则返回None
基本操作Parent(T,e) 初始条件:树
T
存在,
e
是
T
中的某个结点。
操作结果:若
e
不是根结点,则返回该结点的双亲;否则返回None
FirstChild(T,e)
初始条件:树
T
存在,
e
是
T
中的某个结点。
操作结果:若
e
是树
T
的非叶子结点,则返回该结点的第一个孩子结
点;否则返回None
NextSibling(T,e)
初始条件:树
T
存在,
e
是
T
中的某个结点。
操作结果:若
e
不是其双亲结点的最后一个孩子结点,则返回它的下
一个兄弟结点;否则返回None
InsertChild(&T,p,i,
Child)
初始条件:树
T
存在,p指向
T
中的某个结点,非空树Child与
T
不
相交。
操作结果:将非空树Child插入到
T
中,使Child成为p指向的结点
的第
i
棵子树
141
数据结构(Python
语言描述)
续表
基本操作
DeleteChild(&T,p,i)
初始条件:树
T
存在,p指向
T
中的某个结点,1≤i≤d,
d
为p所指
向结点的度。
操作结果:将p所指向的结点的第
i
棵子树删除。如果删除成功,返
回True,否则返回False
TraverseTre(T) 初始条件:树
T
存在。
操作结果:按照某种次序对
T
的每个结点访问且仅访问一次
TreDepth(T) 初始条件:树
T
存在。
操作结果:若树
T
非空,返回树的深度;否则返回0
5.二叉树
2
在深入学习树之前,先介绍一种比较简单的树———二叉树。
5.2.1 二叉树的定义
二叉树(binarytre)是另一种树结构,它的特点是每个结点最多只有两棵子树。在二
叉树中,每个结点的度只可能是0、1和2。每个结点的孩子结点有左右之分,位于左边的孩
子结点称为左孩子结点或左孩子,位于右边的孩子结点称为右孩子结点或右孩子。如果
n=0,则称该二叉树为空二叉树。
下面给出二叉树的5种基本形态,如图5-4所示。
图5-4二叉树的5种基本形态
一个由12个结点构成的二叉树如图5-5所示。F是C的左孩子结点,G是C的右孩
子结点,
L
是
G
的右孩子结点,
G
的左孩子结点不存在。
对于深度为
k
的二叉树,若结点数为2k
-1,即除了叶子
结点外,其他结点都有两个孩子结点,这样的二叉树称为满
二叉树。在满二叉树中,每一层的结点都具有最大的结点个
数,每个结点的度或者为2,或者为0(即叶子结点),不存在度
为1的结点。从根结点出发,从上到下,从左到右,依次对每
个结点进行连续编号,一棵深度为4的满二叉树及其结点编
号如图5-6所示。
如果一棵二叉树有
n
个结点,并且这
n
个结点的结构与满二叉树的前
n
个结点的结构
完全相同,则称这样的二叉树为完全二叉树。完全二叉树及其结点编号如图5-7所示。而
图5-5一棵二叉树
142
第
5
章 树和二叉树
图5-8所示就不是一棵完全二叉树。
图5-
6
一棵深度为4的满二叉树及其结点编号
图5-
7
一棵完全二叉树及其结点编号
图5-
8
一棵非完全二叉树
由此可以看出,如果二叉树的层数为k,则满二叉树的叶子结点一定在第
k
层,而完全
二叉树的叶子结点一定在第
k
层或者第k-1层。满二叉树一定是完全二叉树,而完全二叉
树却不一定是满二叉树。
5.2.2 二叉树的性质
二叉树具有以下重要的性质。
性质
1
在二叉树中,第m(m≥1)层上至多有2m-1个结点(规定根结点为第一层)。
证明:利用数学归纳法证明。
当m=1时,即根结点所在的层次,有2m-1=21-1=20=1,命题成立。
假设当m=
k
时命题成立,即第
k
层至多有2k-1个结点。因为在二叉树中每个结点的
度最大为2,则在第k+1 层,结点的个数最多是第
k
层的2倍,即2×2k-1=2k-1+1=2k
。因
此,当m=k+1 时,命题成立。
性质
2
深度为k(的二叉树至多有2k
k≥1) 1个结点。
143
数据结构(Python
语言描述)
证明:第
i
层结点的最多个数2i-1,将深度为
k
的二叉树中每一层结点的最大值相加,
就得到二叉树中结点的最大值,因此深度为
k
的二叉树的结点总数至多为
k
Σ(k) (第
i
层的结点最大个数)=Σ(k) 2i-1=20+21+
…+2k-1=
20(2-1)=2k-1
i=1i=12-1
命题成立。
性质
3
对任何一棵二叉树T,如果叶子结点总数为n0,度为2的结点总数为n2,则有
n0=n2+1 。
证明:假设在二叉树中,结点总数为n,度为1的结点总数为n1。二叉树中结点的总数
n
等于度为0、度为1和度为2的结点总数的和,即n=n0+n1+n2。
假设二叉树的分支数为Y。在二叉树中,除了根结点外,每个结点都存在一个进入的分
支,所以有n=Y+1 。
又因为二叉树的所有分支都是由度为1和度为2的结点发出,所以分支数Y=n1+
2n2。故n=Y+1=n1+2n2+1 。
联合n=n0+n1+n2 和n=n1+2n2+1 两式,得到n0+n1+n2=n1+2n2+1,即n0=
n2+1 。命题成立。
性质
4
如果完全二叉树有
n
个结点,则深度为
+1 。符号
表示不大于
x
的最大整数,而
x
表示不小于
x
的最小整数。
log2n
证明:假设具有
n
个结点的完全二叉树的深度为k。
k
层完全二叉树的结点个数介于
k-k
x
1层满二叉树与
k
层满二叉树的结点个数之间。根据性质2,1层满二叉树的结点总
数为n1=2k-1-
k
层满二叉树的结点总数为n2=
k
-1。因此有n1<n≤n2,即n1+1≤
1,2n<n2+1,又n1=2k-1-1和n2=2k
-1,故得到2k-1-1≤n<2k
-1,同时对不等式两边取
对数,有k-1≤log2n<k。因为
k
是整数,k-1也是整数,所以k-1=
log2n
+1 。命题成立。
log2n
,即k=
性质
5
如果完全二叉树有
n
个结点,按照从上到下、从左到右的顺序对二叉树中的每
个结点从1到
n
进行编号,则对于任意结点
i
有以下性质:
(1)如果i则序号
i
对应的结点就是根结点,该结点没有双亲结点。如果i>1,则=1,
i/2。
序号为
i
的结点的双亲结点的序号为
(2)如果2i>n,则序号为
i
的结点没有左孩子结点。如果2i≤n,则序号为
i
的结点的
左孩子结点的序号为2i。
(3)如果2i+1>n,则序号为
i
的结点没有右孩子结点。如果2i+1≤n,则序号为
i
的
结点的右孩子结点序号为2i+1
。
证明
:
(1)利用性质(2)和(3)证明。当i=1时,该结点一定是根结点,根结点没有双亲结点。
当i>1 时,假设序号为
m
的结点是序号为
i
的结点的双亲结点。如果序号为
i
的结点是序
号为
m
的结点的左孩子结点,则根据性质(2)有2m=i,即
m
=i/2;如果序号为
i
的结点是
m+1=i-=i/2
序号为
m
的结点的右孩子结点,则根据性质(3)有2i,即
m
=(1)/21/2。
综上以上两种情况,当i>1 时,序号为
i
的结点的双亲结点序号为
。结论成立。
i/2
(2)利用数学归纳法证明。当i=1时,有2i=2。如果2>n,则该二叉树中不存在序
号为2的结点,也就不存在序号为
i
的左孩子结点;如果2≤n,则该二叉树中存在两个结
144
第
5
章 树和二叉树
点,序号为2的结点是序号为
i
的结点的左孩子结点。
假设当i=
k
时,如果2k≤n,序号为
k
的结点的左孩子结点存在且序号为2k;如果2k>
序号为
k
的结点的左孩子结点不存在。n,
当i=k+1时,在完全二叉树中,如果序号为k+1的结点的左孩子结点存在(2i≤n),
则其左孩子结点的序号为序号为
k
的结点的右孩子结点的序号加1,即序号为k+1的结点
的左孩子结点的序号为(2=k+1)2当2序号为
i
的结点的
左孩子不存在。结论成立
k
。
+1)+12(=i。因此, i>
n
时,
(3)同理,利用数学归纳法证明。当i=1时,如果2i+1=3>n,则该二叉树中不存在
序号为3的结点,即序号为
i
的结点的右孩子不存在;如果2i+1=3≤n,则该二叉树存在
序号为3的结点,且序号为3的结点是序号为
i
的结点的右孩子结点。
假设当i=
k
时,如果2k+1≤n,序号为
k
的结点的右孩子结点存在且序号为2k+1,
当2k+1>
n
时,序号为
k
的结点的右孩子结点不存在。
当i=k+1时,在完全二叉树中,如果序号为k+1的结点的右孩子结点存在,其序号为
2i+1≤n,则其右孩子结点的序号为序号为
k
的结点的右孩子结点的序号加2,即序号为
k+1的结点的右孩子结点的序号为(2=k+1)+12当2
k+1)+22(=i+1 。因此, i+1>
n
时,序号为
i
的结点的右孩子不存在。结论成立。
5.2.3 二叉树的抽象数据类型
二叉树的抽象数据类型定义了二叉树中的数据对象、数据关系及基本操作。二叉树的
抽象数据类型描述如表5-3所示。
表5-
3
二叉树的抽象数据类型描述
数据对象
D
是具有相同特性的数据元素的集合
数据关系
若D=.,则称之为空二叉树。
若D≠.,则R={
H
},
H
是如下二元关系:
(1)在
D
中存在唯一的称为根的数据元素root,它在关系
H
下无前驱结点。
(2)若D-{root}≠.,则存在D-{root}={Dl,Dr},且Dl∩Dr=.。
(3)若Dl≠.,则Dl中存在唯一的元素xl,<root,xl>∈
H
,且存在Dl 上的关系Hl.
H
;
若Dr≠.,则Dr 中存在唯一的元素xr,<root,xr>∈
H
,且存在Dr上的关系Hr.
H
;
H
=
{<root,xl>,<root,xr>,Hl,Hr}。
(4)(Dl,{Hl})是一棵符合本定义的二叉树,称为根的左子树;(Dr,{Hr})是一棵符合本定
义的二叉树,称为根的右子树
InitBiTre(&T) 初始条件:二叉树
T
不存在。
操作结果:构造空二叉树
T
CreateBiTre(&T) 初始条件:给出了二叉树
T
的定义。
操作结果:创建一棵非空的二叉树
T
基本操作DestroyBiTre(&T) 初始条件:二叉树
T
存在。
操作结果:销毁二叉树
T
InsertLeftChild(p,c)
初始条件:二叉树
c
存在且非空
c
的右子树为空
操作结果:将
c
插入到p所指向的左子树,使p所指结点的左子树
成为
c
的右子树
145
数据结构(Python
语言描述)
续表
基本操作
InsertRightChild(p,c)
初始条件:二叉树
c
存在且非空,
c
的右子树为空。
操作结果:将
c
插入到p所指向的右子树,使p所指结点的右子树
成为
c
的右子树
LeftChild(&T,e)
初始条件:二叉树
T
存在,
e
是
T
中的某个结点。
操作结果:若结点
e
存在左孩子结点,则将
e
的左孩子结点返回;
否则返回空
RightChild(&T,e)
初始条件:二叉树
T
存在,
e
是
T
的某个结点。
操作结果:若结点
e
存在右孩子结点,则将
e
的右孩子结点返回;
否则返回空
DeleteLeftChild(&T,p)
初始条件:二叉树
T
存在,p指向
T
中的某个结点。
操作结果:将p所指向的结点的左子树删除。如果删除成功,返
回True;否则返回False
DeleteRightChild(&T,p)
初始条件:二叉树
T
存在,p指向
T
中的某个结点。
操作结果:将p所指向的结点的右子树删除。如果删除成功,返
回True;否则返回False
PreOrderTraverse(T)
初始条件:二叉树
T
存在。
操作结果:先序遍历二叉树T,即先访问根结点,再访问左子树,
最后访问右子树,对二叉树中的每个结点访问且仅访
问一次
InOrderTraverse(T)
初始条件:二叉树
T
存在。
操作结果:中序遍历二叉树T,即先访问左子树,再访问根结点,
最后访问右子树,对二叉树中的每个结点访问且仅访
问一次
PostOrderTraverse(T)
初始条件:二叉树
T
存在。
操作结果:后序遍历二叉树T,即先访问左子树,再访问右子树,
最后访问根结点,对二叉树中的每个结点访问且仅访
问一次
LevelTraverse(T)
初始条件:二叉树
T
存在。
操作结果:对二叉树
T
进行层次遍历,即按照从上到下、从左到右
的顺序依次对二叉树中的每个结点进行访问
BiTreDepth(T)
初始条件:二叉树
T
存在。
操作结果:若二叉树
T
非空,返回它的深度;若
T
是空二叉树,返
回0
5.2.4 二叉树的存储表示
二叉树的存储表示方式有两种:顺序存储结构和链式存储结构。
1.二叉树的顺序存储结构
我们已经知道,完全二叉树中每个结点的序号可以通过公式计算得到,因此,完全二叉
树可以按照从上到下、从左到右的顺序依次存储在一维数组或列表中。完全二叉树及其顺
序存储结构如图5-9所示。
如果按照从上到下、从左到右的顺序把非完全二叉树的结点依次存放在一维数组或列表
146
第5 章 树和二叉树
1 47
图5-9 完全二叉树及其顺序存储结构
中。为了能够正确反映二叉树中结点之间的逻辑关系,需要在一维数组(列表)中将二叉树中
不存在的结点位置空出,并用∧填充。非完全二叉树及其顺序存储结构如图5-10所示。
图5-10 非完全二叉树及其顺序存储结构
顺序存储结构对于完全二叉树来说是比较适合的,因为采用顺序存储结构能够节省存
储单元,并能够利用公式得到每个结点的存储位置。但是,对于非完全二叉树来说,这种存
储方式会浪费存储空间。在最坏的情况下,如果每个结点只有右孩子结点,而没有左孩子结
点,则需要占用2k -1个存储单元,而实际上该二叉树只有k 个结点。
2.二叉树的链式存储结构
在二叉树中,每个结点有一个双亲结点和两个孩子结点。从一棵二叉树的根结点开始,
图5-11 二叉链表的结点结构
通过结点的左右孩子地址就可以找到二叉树的每一个结点。
因此二叉树的链式存储结构包括三个域:数据域、左孩子指
针域和右孩子指针域。其中,数据域存放结点的值,左孩子
指针域指向左孩子结点,右孩子指针域指向右孩子结点。这
种链式存储结构称为二叉链表,其结点结构如图5-11所示。
二叉树的二叉链表存储表示如图5-12所示。
有时为了方便找到结点的双亲结点,在二叉链表的存储结构中增加一个指向双亲结点
的指针域parent,这种存储结构称为三叉链表,其结点结构如图5-13所示。
通常情况下,二叉树采用二叉链表表示。二叉链表存储结构的类型定义如下:
class BiTreeNode(): #二叉树中的结点
def __init__(self,data,lchild=None,rchild=None):
self.data=data #二叉树的结点值
self.lchild=lchild #左孩子指针
self.rchild=rchild #右孩子指针
定义了二叉树的结点后,为了实现二叉树的插入、删除、遍历和线索化,必须先创建二叉