文档介绍：第6章树和二叉树
树的定义及其存储结构
二叉树
遍历二叉树和线索化二叉树
树、森林和二叉树的关系
哈夫曼树及其应用
树的定义及其存储结构
数据对象 D:
D是具有相同特性的数据元素的集合。
若D为空集,则称为空树;
否则:
(1) 在D中存在唯一的称为根的数据元素root;
(2) 当n>1时,其余结点可分为m (m>0)个互不相交的有限集T1, T2, …, Tm, 其中每一棵子集本身又是一棵符合本定义的树,称为根root的子树。
数据关系 R:
树的定义及基本术语
A
B
C
D
E
F
G
H
I
J
M
K
L
A( )
T1
T3
T2
树根
例如:
B(E, F(K, L)),
C(G),
D(H, I, J(M))
(1) 有确定的根;
(2) 树根和子树根之间为有向关系。
有向树:
有序树:
子树之间存在确定的次序关系。
无序树:
子树之间不存在确定的次序关系。
基本术语
结点:
结点的度:
树的度:
叶子结点:
分支结点:
数据元素+若干指向子树的分支
分支的个数
树中所有结点的度的最大值
度为零的结点
度大于零的结点
D
H
I
J
M
(从根到结点的)路径:
孩子结点、双亲结点、
兄弟结点、堂兄弟
祖先结点、子孙结点
结点的层次:
树的深度:
由从根到该结点所经分支和结点构成
A
B
C
D
E
F
G
H
I
J
M
K
L
假设根结点的层次为1,第l 层的结点的子树根结点的层次为l+1
树中叶子结点所在的最大层次
任何一棵非空树是一个二元组
Tree = (root,F)
其中:root 被称为根结点,
F 被称为子树森林
森林:
是 m(m≥0)棵互
不相交的树的集合
A
root
B
E
F
K
L
C
G
D
H
I
J
M
F