文档介绍：第6章树和二叉树
树的定义和基本术语
二叉树
遍历二叉树和线索二叉树
树和森林
赫夫曼树及其应用
树的定义和基本术语
是由n(n ≥ 0)个结点组成的有限集合T。
在任意一个非空树中:
有且仅有一个特定的称为根的结点;
n > 1时,其余结点可以分为m(m > 0)个互不相交的有限集T1,T2,T3 ,…,Tm,其中每一个集合本身又是一棵树,且称为根的子树。
树的结构定义是一个递归的定义,即在树的定义中又用到树的概念,它说明了树的特性。
如在右图中,
是只有一个根结点的树
是有13个结点的树
其中A是根,其余结点
分成三个互不相交的子集:T1={B,E,F,K,L}, T2={C,G}, T3={D,H,I,J,M};
T1,T2,T3 都是A的子树,且本身也是一棵树。则同理按此分析方式分析 T1 ,T2,T3。
A
A
B
C
D
E
F
G
H
I
J
K
L
M
嵌套集合:是一些集合的集体,对于其中任何两个集合,或不相交,或一个包含另一个的形式表示。
广义表表示:根作为由子树森林组成的表的名字写在表的左边。
凹入表示:类似书的编目。
G
C
A
B
D
H
I
J
E
K
F
L
A*****************
B****************
E***************
F***************
K**************
L**************
C****************
G***************
D****************
H***************
I***************
J***************
(A(B(E, F(K,L)), C(G), D(H, I, J)))
A
B
C
D
E
F
G
H
I
J
K
L
结点:数据元素+若干指向其子树的分支;
结点的度:结点拥有的子树数;
树的度:树中所有结点的度的最大值;
叶子结点:度为零的结点,或称为终端结点;
分支结点:度大于零的结点,或称为非终端结点;
结点的层次:假设根结点的层次为1, 若某结点在第i层,则其子树的根在第i+1层;
A
B
D
E
F
H
I
J
K
M
树的深度:树中叶子结点所在的最大层次;
孩子结点:结点的子树的根;相应地该结点称为孩子的双亲结点;
兄弟结点:同一个双亲的孩子之间称为兄弟结点;
祖先:从根到该结点所经分支上的所有结点;
子孙:子树中任一结点;
A
B
D
E
F
H
I
J
K
M
有序树、无序树
子树之间是否存在次序关系?
将树中结点的各子树看成从左至右是有次序的(即不能互换) 称有序树,否则称无序树;
森林:是m(m≥0)棵互不相交的树的集合。
任何一棵非空树是一个二元组
Tree = (root,F)
其中:root被称为根结点,F被称为子树森林;
A
B
D
E
F
H
I
J
K
M
第一个数据元素(无前驱)   
最后一个数据元素(无后继)
其它元素(一个前驱、一个后继)
根结点(无前驱)
多个叶子结点(无后继)
其它结点(一个前驱、多个后继)
线性结构
树结构
ADT List {
数据对象D:是具有相同特性的数据元素的集合
数据关系R:数据关系R:若D为空集,则称为空树;若D仅含一个数据元素,则R为空集,否则 R={H},H是如下二元关系:
(1) 在D中存在唯一的称为根的数据元素root,它在关系H下无前驱;
(2) 若D-{root}!=Φ,则存在 D-{root}的一个划分D1,D2,…,Dm (m>0),对任意j≠k(1≤j,k≤m)有Dj∩Dk=Φ,且对任意的 i(1≤i≤m),唯一存在数据元素xi∈Di,有<root,xi>∈H;
ADT List {
数据关系R:
(3) 对应于 D-{root}的划分,H-{<root,x1>,…,<root,xm>} 有唯一的一个划分 H1,H2,…,Hm(m>0),对任意j≠k(1≤j,k≤m)有 Hj∩Hk=Φ,对任意 i(1≤i≤m),Hi是Di上的二元关系,(Di,{Hi})是一棵符合本定义的子树,称为根root的子树。
基本操作:
} ADT List