文档介绍：第6章树和二叉树
树的概念与定义
二叉树
二叉树的遍历与线索化
树、森林和二叉树的关系
哈夫曼树及其应用
树的计数
树的概念与定义
树是n(n≥0)个结点的有限集合T。当n=0时,称为空树;当n>0时,该集合满足如下条件:
(1) 其中必有一个称为根(root)的特定结点,它没有直接前驱,但有零个或多个直接后继。
(2) 其余n-1个结点可以划分成m(m≥0)个互不相交的有限集T1,T2,T3,…,Tm,其中Ti又是一棵树,称为根root的子树。每棵子树的根结点有且仅有一个直接前驱,但有零个或多个直接后继。
例如:
A
C
G
B
D
E
F
K
L
H
M
I
J
A
只有根结点的树
有13个结点的树
其中:A是根;其余结点分成三个互不相交的子集,
T1={B,E,F,K,L}; T2={C,G}; T3={D,H,I,J,M},
T1,T2,T3都是根A的子树,且本身也是一棵树
1. 树型表示法
2. 嵌套集合表示法
A
B
C
D
A
B
C
D
3. 广义表表示法
(A(B(D),C))
3. 凹入表示法
树的表示法
A
B
D
C
树的基本术语
1层
2层
4层
3层
height
= 4
A
C
G
B
D
E
F
K
L
H
M
I
J
结点
结点的度
叶结点
分支结点
子女
双亲
兄弟
祖先
子孙
结点层次
树的深度
树的度
森林
有关树的一些术语:
结点:包含一个数据元素及若干指向其它结点的分支信息。
结点的度:一个结点的子树个数称为此结点的度。
叶结点:度为0的结点,即无后继的结点,也称为终端结点。
分支结点:度不为0的结点,也称为非终端结点。
孩子结点:一个结点的直接后继称为该结点的孩子结点。如上图的B、C、D是A的孩子。
双亲结点:一个结点的直接前驱称为该结点的双亲结点。上图中A是B、C、D的双亲。
兄弟结点:同一双亲结点的孩子结点之间互称兄弟结点。上图中的结点H、I、J互为兄弟结点。
祖先结点:一个结点的祖先结点是指从根结点到该结点的路径上的所有结点。如结点K的祖先结点是A、B、E。
子孙结点:一个结点的直接后继和间接后继称为该结点的子孙结点。如结点D的子孙是H、I、J、M。
树的度:树中所有结点的度的最大值。
堂兄弟结点:其双亲在同一层的结点。如结点G与结点E、F、H、I、J互为堂兄弟。
结点的层次:从根结点开始定义,根结点的层次为1,根的直接后继的层次为2,依此类推。
树的高度(深度):树中所有结点的层次的最大值。
有序树:在树T中,如果各子树Ti之间是有先后次序的,则称为有序树。
森林:m(m≥0)棵互不相交的树的集合。将一棵非空树的根结点删去,树就变成一个森林;反之,给森林增加一个统一的根结点,森林就变成一棵树。
树的抽象数据类型定义:
数据对象D:一个集合,该集合中的所有元素具有相同的特性。
数据关系R:若D为空集,则为空树。若D中仅含有一个数据元素,则R为空集,否则R={H},H是如下的二元关系:
(1) 在D中存在唯一的称为根的数据元素root,它在关系H下没有前驱。
(2) 除root以外,D中每个结点在关系H下都有且仅有一个前驱。
基本操作:
InitTree(Tree): 将Tree初始化为一棵空树。
(2) DestoryTree(Tree): 销毁树Tree。
(3) CreateTree(Tree): 创建树Tree。
(4) TreeEmpty(Tree): 若Tree为空,则返回TRUE,否则返回FALSE。
(5) Root(Tree): 返回树Tree的根。
(6) Parent(Tree,x): 树Tree存在,x是Tree中的某个结点。若x为非根结点,则返回它的双亲,否则返回“空”。