第六章（树与二叉树）.ppt

第六章树和二叉树
树的定义和基本概念
二叉树
遍历二叉树
树和森林
赫夫曼树及其应用
树型结构是一类重要的非线性结构。树结构在客观世界里是大量存在的,树在计算机领域中也有着广泛的应用,例如在编译程序中,用树来表示源程序的语法结构;在数据库系统中,可用树来组织信息;在分析算法的行为时,可用树来描述其执行过程等等。
树的定义和基本术语
1、定义树是n(n>=0)个结点的有限集T,T为空时称为空树,否则它满足如下两个条件:
(1)有且仅有一个特定的称为根的结点;
(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,T3…Tm,其中每个子集又是一棵树,并称其为根的子树。
A
只有根结点的树
A
B
C
D
E
F
G
H
I
J
K
L
M
有子树的树
根
子树
1、定义
结点——表示树中的元素,包括数据项及若干指向其子树的分支
2、基本术语
结点的度(degree)——结点拥有的子树数
叶子(leaf)——度为0的结点
孩子(child)——结点子树的根称为该结点的孩子
双亲(parents)——孩子结点的上层结点叫该结点的~
兄弟(sibling)——同一双亲的孩子
树的度——一棵树中最大的结点度数
结点的层次(level)——从根结点算起,根为第一层,它的孩子为第二层……
深度(depth)——树中结点的最大层次数
森林(forest)——m(m0)棵互不相交的树的集合
A
B
C
D
E
F
G
H
I
J
K
L
M
结点A的度:3
结点B的度:2
结点M的度:0
叶子:K,L,F,G,M,I,J
结点A的孩子:B,C,D
结点B的孩子:E,F
结点I的双亲:D
结点L的双亲:E
结点B,C,D为兄弟
结点K,L为兄弟
树的度:3
结点A的层次:1
结点M的层次:4
树的深度:4
结点F,G为堂兄弟
结点A是结点F,G的祖先
2、基本术语
二叉树
二叉树在树结构的应用中起着非常重要的作用,因为对二叉树的许多操作算法简单,而任何树都可以与二叉树相互转换,这样就解决了树的存储结构及其运算中存在的复杂性。
定义:二叉树是由n(n>=0)个结点的有限集合构成,此集合或者为空集,或者由一个根结点及两棵互不相交的左右子树组成,并且左右子树都是二叉树。
这也是一个递归定义。二叉树可以是空集合,根可以有空的左子树或空的右子树。二叉树不是树的特殊情况,它们是两个概念。
(a)
空二叉树
A
A
B
A
B
A
C
B
(b)
根和空的左右子树
(c)
根和左子树
(d)
根和右子树
(e)
根和左右子树

二叉树结点的子树要区分左子树和右子树,即使只有一棵子树也要进行区分,说明它是左子树,还是右子树。这是二叉树与树的最主要的差别。,(C) (d)是不同的两棵二叉树。
二叉树
二叉树的性质
二叉树具有下列重要性质:
性质1: 在二叉树的第i层上至多有2i-1个结点(i>=1)。
采用归纳法证明此性质。
当i=1时,只有一个根结点,2i-1=20 =1,命题成立。
现在假定对所有的j,1<=j<i,命题成立,即第j层上至多有2j-1个结点,那么可以证明j=i时命题也成立。由归纳假设可知,第i-1层上至多有2i-2个结点。
由于二叉树每个结点的度最大为2,故在第i层上最大结点数为第i-1层上最大结点数的二倍,
即2×2i-2=2i-1。命题得到证明。
性质2:深度为k的二叉树至多有2k-1个结点(k>=1).
性质3: 对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。
深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点数之和,由性质1得到每层上的最大结点数,
设二叉树中度为1的结点数为n1,二叉树中总结点数为N,因为二叉树中所有结点均小于或等于2,所以有:
N=n0+n1+n2 (6-1)
再看二叉树中的分支数,除根结点外,其余结点都有一个进入分支,设B为二叉树中的分支总数,
则有: N=B+1。
由于这些分支都是由度为1和2的结点射出的,所以有:
B=n1+2*n2
N=B+1=n1+2×n2+1 (6-2)
由式(6-1)和(6-2)得到:
N=n0+n1+n2 (6-1)
性质3: 对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。
n0+n1+n2=n1+2*n2+1
n0=n2+1