数据结构章节程内容ppt课件.ppt

数据结构课程的内容
1
第6章树和二叉树( Tree & Binary Tree )
树的基本概念
二叉树
遍历二叉树和线索二叉树
树和森林
赫夫曼树及其应用
特点:非线性结构,一个直接前驱,但可能有多个直接后继(1:n)
2
树的基本概念
1. 树的定义
2. 若干术语
3. 逻辑结构
4. 存储结构
5. 树的运算
3
1. 树的定义
注1:过去许多书籍中都定义树为n≥1,曾经有“空树不是树”的说法,但现在树的定义已修改。
注2:树的定义具有递归性,即树中还有树。
由一个或多个(n≥0)结点组成的有限集合T,有且仅有一个结点称为根(root),当n>1时,其余的结点分为m(m≥0)个互不相交的有限集合T1,T2,…,Tm。每个集合本身又是棵树,被称作这个根的子树。
4
树的表示法有几种:
图形表示法
嵌套集合表示法
广义表表示法
目录表示法
左孩子-右兄弟表示法
这些表示法的示意图参见教材P120
树的抽象数据类型定义参见教材P118-119
5
左孩子-右兄弟表示法
A
B
C
D
E
F
G
H
I
J
K
L
M
数据
左孩子
右兄弟
( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )
8
树的抽象数据类型定义
(见教材P118-119)
ADT Tree{
数据对象D:
数据关系R:
基本操作 P:
}ADT Tree
若D为空集,则称为空树;//允许n=0
若D中仅含一个数据元素,则R为空集;
其他情况下的R存在二元关系:
① root 唯一//关于根的说明
② Dj∩Dk= Φ//关于子树不相交的说明
③……//关于数据元素的说明
D是具有相同特性的数据元素的集合。
//至少有15个
9
2. 若干术语
——即上层的那个结点(直接前驱)
——即下层结点的子树的根(直接后继)
——同一双亲下的同层结点(孩子之间互称兄弟)
——即双亲位于同一层的结点(但并非同一双亲)
——即从根到该结点所经分支的所有结点
——即该结点下层子树中的任一结点
A
B
C
G
E
I
D
H
F
J
M
L
K
根
叶子
森林
有序树
无序树
——即根结点(没有前驱)
——即终端结点(没有后继)
——指m棵不相交的树的集合(例如删除A后的子树个数)
双亲
孩子
兄弟
堂兄弟
祖先
子孙
——结点各子树从左至右有序,不能互换(左为第一)
——结点各子树可互换位置。
10