数据结构铜陵学院.ppt

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