文档介绍：第六章树和二叉树
第六章树和二叉树
第六章树和二叉树
树的有关概念
二叉树
二叉树的遍历
遍历的应用
* 线索二叉树(简单介绍)
树和森林
哈夫曼树及应用
第六章树和二叉树
树的有关概念
1. 树的概念
2. 树的应用
3. 树的表示
树的有关术语
5 树的基本操作
树的有关概念

定义:树是n个结点的有限集合。在任一棵非空树中: (1)有且仅有一个称为根的结点;。 (2)其余结点可分为m个互不相交的有限集合,而且这些集合中的每一集合本身又是一棵树,称为根的子树。
树是递归结构,在树的定义中又用到了树的概念
J
I
A
C
B
D
H
G
F
E
树结构(除了一个称为根的结点外)每个元素都有且仅有一个直接前趋,有且仅有零个或多个直接后继。
树的有关概念
从逻辑结构看: 1)树中只有根结点没有前趋;2)除根外,其余结点都有且仅一个前趋;
3)树的结点,可以有零个或多个后继;4)除根外的其他结点,都存在唯一条从根到该结点的路径;
5)树是一种分枝结构
J
I
A
C
B
D
H
G
F
E
树的有关概念
1)树可表示具有分枝结构关系的对象

、系统功能模块图
树的有关概念
2)树是常用的数据组织形式有些应用中数据元素之间并不存在间分支结构关系,但是为了便于管理和使用数据,将它们用树的形式来组织。
例3 计算机的文件系统不论是DOS文件系统还是window文件系统,所有的文件是用树的形式来组织的。
puter
C:
D:
E:
etc
WINDOWS
Program Files
Picture
Music
……
……
……
……
……
……
……
……
树的有关概念
3 、树的基本术语
1)结点的度:结点所拥有的子树的个数。
2)树的度:树中各结点度的最大值。
C
G
B
D
E
F
K
L
H
M
I
J
A
DA=3
DB=2
DC=1
DG=0
DTree=3
树的有关概念
3)叶子结点:度为0的结点,也称为终端结点。
4)分支结点:度不为0的结点,也称为非终端结点。
C
G
B
D
E
F
K
L
H
M
I
J
A
叶子结点:{K,L,F,G,M,I,J}
分支结点:{A,B,C,D,E,H}