文档介绍：数据结构 第六章 树和二叉树
本章内容
树的概念与基本术语
二叉树
遍历二叉树
线索二叉树
树与森林
赫夫曼树及其应用
6-2
树的概念与基本术语
树的定义(Tree)
树是有n(n≥0)个结点的有限集合。
如果 n=0,称为空树;
如果 n>0,称为非空树,对于非空树,有且仅有一个特定的称为根(Root)的节点(无直接前驱)
如果 n>1,则除根以外的其它结点划分为 m (m>0)个互不相交的有限集 T1, T2 ,…, Tm,其中每个集合本身又是一棵树,并且称为根的子树(SubTree)。
每个结点都有唯一的直接前驱,但可能有多个后继
树的举例
其中:A是根;其余结点分成三个互不相交的子集,
T1={B,E,F,K,L}; T2={C,G}; T3={D,H,I,J,M},
T1,T2,T3都是根A的子树,且本身也是一棵树
A
C
G
B
D
E
F
K
L
H
M
I
J
有13个结点的树
A
只有根结点的树
6-3
树的概念与基本术语
树的基本术语
结点:包含一个数据元素及若干指向其子树的分支
结点的度:结点拥有的子树数,或者说后继结点数
叶结点:度为0的结点[没有子树的结点]
分支结点:度不为0
的结点[包括根结点],
也称为非终端结点。
内部结点:除根外的结点
孩子:结点的子树的根
双亲:孩子的直接前驱
A
B
C
D
E
F
G
H
I
J
K
L
M
1层
2层
4层
3层
Height= 4
6-4
树的概念与基本术语
兄弟:同一双亲的孩子
子孙:以某结点为根的
树中的所有结点
祖先:从根到该结点
所经分支上的所有结点
层次:根结点为第一层,其孩子为第二层,依此类推
深度:树中结点的最大层次
森林:互不相交的树的集合。对树中每个结点而言,其子树的集合即为森林
A
B
C
D
E
F
G
H
I
J
K
L
M
1层
2层
4层
3层
Height= 4
6-5
二叉树
二叉树(Binary Tree)
每个结点最多有2棵子树
二叉树的子树有左右之分
R
R
L
L
空树只有根只有左子树只有右子树有左右子树
6-6
二叉树
二叉树性质1:在二叉树的第i层上至多有2i-1个结点
证明:
i=1, 只有一个根节点,因此2i-1=20=1
设第i-1层上,以上性质成立,即第i-1层至多有2(i-1)-1结点。
由二叉树的定义可知,任何结点的度小于2,因此,第i层上的结点数最多为第i-1层上的两倍,即2*2i-2=2i-1
证毕
6-7
二叉树
二叉树性质2:深度为k的二叉树至多有2k-1个结点
证明:
由性质1,已知第i层上结点数最多为2i-1
k
∑ 2i-1 = 2k-1
i=1
证毕
6-8
二叉树
二叉树性质3:如果二叉树终端结点数为n0,度为2的结点数为n2,则n0=n2+1
证明:
设n1是度为1的结点,则总结点数n= n0+n1+n2
设B为二叉树的分支数,除根结点外,每个结点有且只有一个分支,因此n=B+1
每个分支皆由度为1或2的结点发出,B=n1+2n2
n=B+1=(n1+2n2)+1 = n0+n1+n2,因此 n0=n2+1
证毕
6-9
二叉树
满二叉树:
一个深度为k且有2k-1个结点的二叉树
每层上的结点数都是最大数
可以自上而下、自左至右连续编号
8
9
10
11
12
13
14
15
4
5
6
7
2
3
1
6-10