文档介绍:数据结构
----树和二叉树
第六章树和二叉树
树的定义
1.
二叉树
2.
遍历二叉树
3.
树和森林
4.
赫夫曼树及其应用
5.
树的定义
树:n(n≥0)个结点的有限集合。当n=0时,称为空树;任意一棵非空树满足以下条件:
⑴有且仅有一个特定的称为根的结点;
⑵当n>1时,除根结点之外的其余结点被分成m(m>0)个互不相交的有限集合T1,T2,…,Tm,其中每个集合又是一棵树,并称为这个根结点的子树。
树的定义是采用递归方法
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))
(a) 一棵树结构(b)一个非树结构(c)一个非树结构
树的定义
A
C
B
G
F
E
D
H
I
A
C
B
G
F
D
A
C
B
G
F
D
E
树的应用举例——文件结构
puter
C:
D:
E:
etc
WINDOWS
Program Files
Picture
Music
……
……
……
……
……
……
……
……
基本术语
结点:
结点的度:
树的度:
叶子结点:
分支结点:
数据元素+若干指向子树的分支
分支的个数
树中所有结点的度的最大值
度为零的结点
度大于零的结点
D
H
I
J
M
(从根到结点的)路径:
孩子结点、双亲结点、
兄弟结点、堂兄弟
祖先结点、子孙结点
结点的层次:
树的深度:
由从根到该结点所经分支和结点构成
A
B
C
D
E
F
G
H
I
J
M
K
L
假设根结点的层次为1,第l 层的结点的子树根结点的层次为l+1
树中叶子结点所在的最大层次