第6章 树和二叉树.ppt

第6章二叉树
线性结构:每个元素都只有一个前驱和后继结点。
现实许多事物的关系没有这么简单,如社会机构组成、城市交通通讯等,事物的联系是非线性的:数据元素具有两个以上的前驱或后继结点。
树型结构是一类重要的非线性数据结构,其中以树和二叉树最为常用。
本章讨论二叉树的存储结构及其各种操作,并研究树和森林与二叉树的转换关系,最后介绍几个应用例子。下一章进展到具有一般意义的树结构。
第6章二叉树
二叉树的定义与性质
二叉树的基本操作与存储
二叉树的遍历
线索二叉树
二叉树的应用
基本概念
二叉树(Binary Tree)是有限个元素的集合:
或者为空
或者是由一个根结点加上两棵互不相交的二叉树组成(分别称为左子树和右子树)
二叉树的定义与性质
二叉树的基本概念
二叉树是有序的。
二叉树的子树有左右之分。
有5种基本形态。
二叉树的定义与性质
二叉树的五种不同形态
L
L
R
R
1层
2层
4层
3层
height
= 4
A
B
C
D
E
H
I
F
J
G
结点
结点的度
树的度
分支结点
叶结点
子女(左右)
双亲
兄弟
祖先
子孙
结点层次
树的高(深)度
满二叉树
完全二叉树
两种特殊的二叉树
满二叉树:所有的分支结点都有左右子树,所有的叶子结点都在同一层上。
A
B
C
D
E
H
I
J
K
F
G
L
M
N
O
A
B
C
D
E
H
I
J
K
F
G
L
M
满二叉树
非满二叉树
A
B
C
D
E
H
I
J
K
F
G
L
N
O
非满二叉树
非满二叉树
A
B
C
D
H
I
F
G
L
M
N
O
两种特殊的二叉树
完全二叉树:叶子结点只出现在最下层和次下层,并且最下层的叶子结点集中在树的左边。
满二叉树必定是完全二叉树,完全二叉树不一定是满二叉树。
A
B
C
D
E
H
I
J
K
F
G
L
完全二叉树
A
B
C
D
E
H
I
K
F
G
L
非完全二叉树
ADT BinaryTree {
数据对象D:具有相同特性的数据元素的集合。
数据关系R:
若D= Φ,则R=Φ,称BinaryTree为空二叉树;
若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上的关系H1为H的子集;Dr同样;
H={<root,xl>,<root,xr>,Hl,Hr};
(4)(Dl,{Hl})是一棵符合本定义的二叉树,称为根的左子树,(Dr,{Hr})是一棵符合本定义的二叉树,称为根的右子树。
二叉树的抽象数据类型
2. 二叉树的性质
性质1 二叉树的第i层上至多有2i-1个结点(i≥1)。
利用归纳法容易证得此性质。
(1)i=1时,只有一个根结点。显然,2i-1=20=1。
(2)假定对所有的j,1≤j<i,命题成立,即第j层上至多有2j-1个结点。那么,现在来证明j=i时命题也成立。
(3)由归纳假设:第i-1层上至多有2i-2个结点。由于二叉树的每个结点的度至多为 2,故在第i层上的最大结点数为第i-1层上的最大结点数的2倍,即2*2i-2=2i-1。