树和二叉树.ppt

文档介绍：1
树的定义与基本术语
第 6 章树和二叉树
二叉树
二叉树的遍历与线索化
树、森林与二叉树的关系
哈夫曼树及其应用
总结与提高
2
树的定义与基本术语
第 6 章树和二叉树
树:是n(n≥0)个结点的有限集合T。
当n=0时称为空树;
当n>0时,该集合满足如下条件:
其中必有一个称为根(root)的特定结点,它没有直接前驱,但有零个或多个直接后继。
(2) 其余n-1个结点可以划分成m(m≥0)个互不相交的有限集T1,T2,T3,…,Tm,其中Ti又是一棵树,称为根root的子树。每棵子树的根结点有且仅有一个直接前驱,但有零个或多个直接后继。
3
树的定义与基本术语
例如:
第 6 章树和二叉树
A
B
C
D
E
F
G
H
I
J
M
K
L
A( B(E, F(K, L)), C(G), D(H, I, J(M)) )
T1
T3
T2
根
4
树的定义与基本术语
表示方法:
第 6 章树和二叉树
①树型表示
b
a
c
g
h
d
e
f
i
j
5
树的定义与基本术语
表示方法:
第 6 章树和二叉树
②文氏图表示
i
j
d
f
g
h
a
b
c
e
6
树的定义与基本术语
表示方法:
第 6 章树和二叉树
③凹入表示
a
b
d
e
i
j
f
c
g
h
7
树的定义与基本术语
表示方法:
第 6 章树和二叉树
④嵌套括号表示
a ( b ( d, e ( i, j ), c ( g, h ) ) )
8
树的定义与基本术语
第 6 章树和二叉树
基本术语
①结点:
数据元素+若干指向子树的分支
②结点的度:
分支的个数
③树的度:
树中所有结点的度的最大值
④叶子结点:
度为零的结点
⑤分支结点:
度大于零的结点
⑥(从根到结点的)路径:
由从根到该结点所经分支和结点构成。
A
B
C
D
E
F
G
H
I
J
M
K
L
9
树的定义与基本术语
第 6 章树和二叉树
基本术语
⑦孩子结点:
一个结点的直接后继
⑧双亲结点:
一个结点的直接前驱
⑨兄弟结点:
同一双亲结点的孩子结点之间互称~。
⑩堂兄弟、祖先结点、子孙结点
结点的层次:
根结点的层次为1,第i层的结点的
子树的根结点的层次为i+1
树的深度:
树中结点的层次的最大值
A
B
C
D
E
F
G
H
I
J
M
K
L
森林:
是m(m≥0)棵互不相交的树的集合
10
树的定义与基本术语
第 6 章树和二叉树
基本操作
①InitTree(Tree);
②DestoryTree(Tree);
③CreatTree(Tree);
④TreeEmpty(Tree);
⑤Root(Tree);
⑥Parent(Tree,x);
⑦FirstChild(Tree,x);
⑧NextSibling(Tree,x);
⑨InsertChild(Tree,p,Child);
⑩DeleteChild(Tree,p,Child);
返回