文档介绍：该【数据结构第六章数和二叉树 】是由【mxh2875】上传分享，文档一共【87】页，该文档可以免费在线阅读，需要了解更多关于【数据结构第六章数和二叉树 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。1
202X
CIICK HERE TO ADD A TITLE
单击添加副标题
数据结构课程的内容
2
第6章 树和二叉树（ Tree & Binary Tree ）
特点：非线性结构，一个直接前驱，但可能有多个直接后继（1：n）
树的基本概念
二叉树
遍历二叉树和线索二叉树
树和森林
赫夫曼树及其应用
3
树的基本概念
树的定义
若干术语
逻辑结构
存储结构
树的运算
4
注1：过去许多书籍中都定义树为n≥1，曾经有“空树不是树”的说法，但现在树的定义已修改。
注2：树的定义具有递归性，即树中还有树。
由一个或多个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树 。
5
1
WORKREVIEW
图形表示法
CONTENTS
树的表示法有几种：
2
嵌套集合表示法
UNDERWORK
3
广义表表示法
WORKHARVEST
4
目录表示法
FUTUREOUTLOOK
5
左孩子－右兄弟表示法
这些表示法的示意图参见教材P120
树的抽象数据类型定义参见教材P118-119
UNDERWORK
6
教师
学生
其他人员
2003级
2004级
2005级
2006级
……
河南大学
物理系
计算机系
化学系
……
叶子
根
子树
图形表示法：
7
嵌套集合表示法
( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) )
根作为由子树森林组成的表的名字写在表的左边
8
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 ) ) )
左孩子－右兄弟表示法
9
ADT Tree{
数据对象D:
数据关系R:
基本操作 P：
}ADT Tree
若D为空集，则称为空树；//允许n=0
若D中仅含一个数据元素，则R为空集；
其他情况下的R存在二元关系：
① root 唯一 //关于根的说明
② Dj∩Dk= Φ //关于子树不相交的说明
③ Hj ∩Hk= Φ 且Hi仍然是一棵树
//关于数据元素的说明
D是具有相同特性的数据元素的集合。
//至少有15个
A
B
C
G
E
I
D
H
F
J
M
L
K
树的抽象数据类型定义
10
——即上层的那个结点(直接前驱)
——即下层结点的子树的根(直接后继)
——同一双亲下的同层结点（孩子之间互称兄弟）
——即双亲位于同一层的结点（但并非同一双亲）
——即从根到该结点所经分支的所有结点
——即该结点下层子树中的任一结点
A
B
C
G
E
I
D
H
F
J
M
L
K
根
叶子
森林
有序树
无序树
——即根结点(没有前驱)
——即终端结点(没有后继)
——指m棵不相交的树的集合(例如删除A后的子树个数)
双亲
孩子
兄弟
堂兄弟
祖先
子孙
——结点各子树从左至右有序，不能互换（左为第一）
——结点各子树可互换位置。
2. 若干术语