文档介绍：基本术语
二元树
树
森林与二元树间的转换
树的应用
第四章树(Tree)
线性表——元素之间的线性关系
树——元素之间的层次关系
基本术语
[定义]
一
1、一个结点x组成的集{x}是一株树,这个结点x也是这
株树的根。
2、假设x是一个结点,T1,T2,…,Tk是k株互不相交的
树,我们可以构造一株新树:令x为根,并有k条边由
x指向树T1,T2,…,Tk。这些边也叫做分支,T1,T2,
…,Tk称作根x的树之子树(SubTree)。
树是n(≥0)个结点的有限集。在任意一棵非空树中:
1、有且仅有特定的称为根(Root)的结点;
2、当n>1时,其余结点可分为m(>0)个互不相交的有限
集T1,T2,…,Tm,其中每一个集合本身又是一棵树,
并且称为根的子树( SubTree )。
[定义]
二
基本术语
[定义三]
T = ( D,R )
D:具有相同类型的数据元素的集合。
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),唯一存在数据元素 x i∈ Di,
有< root , xi > ∈ H;
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的子树。
基本术语
A
B
C
D
E
F
G
H
I
J
K
L
M
图一
第1层
第2层
第3层
第4层
第5层
A
B
C
D
E
F
G
H
I
J
K
L
M
图二
树高为5
常用术语:
结点
度
叶(终端结点)
非终端结点
分支路长
父亲双亲
儿子兄弟
子孙祖先
层结点的高
树的高(深度)
有序树& 无序树
基本术语
A
B
C
A
C
B
≠
森林forest:
是 n ≥ 0 株互不相交的树的集合。
二元树( binary tree )
[定义一] 二元树是有限个结点的集合,这个集合或者是空集,
或者是由一个根结点和两株互不相交的二元树组成,其中一
株叫根的做左子树,另一棵叫做根的右子树。
二元树的定义和基本性质
二元树的定义和基本性质
[定义二] Binary Tree = ( D , R )
D:指数据对象,是由相同类型的数据元素组成的集合。
R:为数据元素间的关系:
若D=¢,则R= ¢,称Binary tree 为空树;
若D≠￠;则R={H},H是如下二元关系:
⑴在D中存在唯一的称为根的数据元素 root,它在关系H下
无前驱;
⑵若D-{ root } ≠￠,则存在D-{root}={Dl,Dr},且Dl∩Dr=¢;
⑶若Dl ≠￠,则Dl中存在唯一的元素xl,< root , xl >∈H,且存
在Dl上的关系Hl∈H;若Dr ≠￠,则Dr中存在唯一的元素
xr,< root , xr >∈H,且存在Dr上的关系Hr∈H;
H={< root , x l>, <root,xr>,Hl,Hr};
⑷(Dl,{Hl})是符合本定义的二元树,称为根的左子树;
(Dr,{Hr})是符合本定义的二元树,称为根的右子树;
二元树的定义和基本性质
二元树的性质:
性质1:在二元树中第 i 层的结点数最多为2i-1(i ≥ 1)。
性质2:高度为k的二元树其结点总数最多为2k-1( k ≥ 1)
性质3:对任意的非空二元树 T ,如果叶结点的个数为 n0,而
其度为 2 的结点数为 n2,则:
n0 = n2 + 1
[定义] 深度为k且有2k -1个结点的二元树称为满二元树。
层序编号:对满二元树的结点进行连续编号。从根结点开始,
从上而下,自左至右。
[定义] 深度为 k 的,由n个结点的二元树,当且仅当其每个结点
都与深度为 k 的满二元树中编号从 1 至 n 的结点一一对
应,称之为完