软件技术基础：树与叉树.doc

2.5树与二叉树
树型结构是一类很重要的非线性数据结构，在这类结构中，元素结点之间存在明显的分支和层次关系。
2.5.1 树的定义及其存储结构
1. 树的定义和术语
树是由n个(n≥0)结点组成的有限集合T，其中有且仅有一个结点称为根结点(root)，其余结点可以分为m(m≥0)个互不相交的有限集合T1，T2，…，Tm,其中每个集合Ti本身又是一棵树，称为根结点root的子树。当n=0时称为空树。矚慫润厲钐瘗睞枥庑赖。
这是一个递归的描述，即在买偶数树时又用到树本身这个术语。图2.33所示为一棵树，A为根结点，期于结点分为三个不相交的子集T1，T2，T3，它们均为根结点A下的三棵树，而这三棵树本身也是树。聞創沟燴鐺險爱氇谴净。

用二元组关系来定义树为
Tree=(T,R)
数据结构树(Tree)由数据元素集合T及各种R组成，其中T 是具有相同类型的数据元素集合T ={x1，x2，…，xn}。若T为空集(T=Ø),则R=Ø，称为空树，否则R是T上某个二元关系H的集合，即R={H}。H的描述如下：残骛楼諍锩瀨濟溆塹籟。
(1)在T中存在唯一的称为根的元素root，它在H关系下无前趋。
(2)若T-{root}≠Ø，则存在m个子集T1，T2，…，Tm(m>0),对任意的j≠k(1≤j,k≤m)，有Tj∩Tk= Ø，则存在唯一的数据元素xi∈Ti(1≤i≤m)，满足<root,xi>∈H。酽锕极額閉镇桧猪訣锥。
(3)对应于 T1，T2，…，Tm，H-{<root，x1>，…，<root，xm>}，满足<root，xi>∈H1，H2，…，Hm(m>0)，对任意的j≠k(1≤j,k≤m)有Hj∩Hk= Ø，Hj满足在Ti上的二元关系。因此(Ti，{Hi})也是一棵符合本定义的树，称为根root的子树。彈贸摄尔霁毙攬砖卤庑。
树结构中常用的术语有
.结点(node):表示树中的元素。
.结点的度(degree)：结点拥有的子树数，如图2.33中结点A的度为3，C的度为1。一棵树中最大的结点度数为这棵树的度，图2.33中树的度为3。謀荞抟箧飆鐸怼类蒋薔。
.叶子(leaf):度为零的结点，又称为端结点。
.孩子(child)：除根结点外，每个结点都是其前趋结点的孩子。
.双亲(parents)：对应上述孩子结点的上层结点称为这些结点的双亲。例如图2.33中，D是A的孩子，A是D，C，B的双亲。厦礴恳蹒骈時盡继價骚。
.兄弟(sibling):同一双亲的孩子。
.结点的层次(level)：从根结点开始算起，根为第一层，根的直接后继结点为第二层，其余个层次依次类推。例如图2.33中共分为4层。茕桢广鳓鯡选块网羈泪。
.深度(depth)：树中结点的最大层次数。图2.33中树的深度为4。
.森林(forest)：是m(m≥0)棵互不相交的树的集合。
.有序树：树中结点在同层中按从左至右有序排列、不能互换的称为有序树，反之称为无序树。
2. 树的存储结构
仅讨论链式存储结构。
异构型：节省存储空间，运算不便。
同构型：运算方便，浪费空间。
假设有一棵具有n个结点的k叉树，则有nk个指针域，其中有用的指针域为n-1个，因此空链域个数为nk-(n-1)=n(k-1)+1个。鹅娅尽損鹌惨歷茏鴛賴。

不同的k值进行比较:

k越大，空链域比例越高，k=2时比例最低，因此着重讨论二叉树结构。
2.5. 2二叉树及其性质
1. 二叉树定义及其存储结构
二叉树是n(n≥0)个结点的有限集合，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。籟丛妈羥为贍偾蛏练淨。
通常用具有两个指针域的链表作为二叉树的存储结构，其中每个结点由数据域(data)、左指针域(L child)和右指针域(R child)组成，即預頌圣鉉儐歲龈讶骅籴。
L child
data
R child

二叉树的链表结构如图2.35(b)所示。

2. 二叉树的基本性质
(1) 二叉树的第I层上至多有2i-1(i≥1)个结点。
1，21-1． 2，22-1…………..
(2) 深度为h的二叉树中至多含有2h-1个结点。
1， 21-1．2，22-1…
20+21+22+23+………2h-1 =1+20+21+22+23+………2h-1-1
=2h-1

(3) 在任意二叉树中，若有n0个叶子结点，n2个度为2 的结点，则必有：n0=n2+1。
每增加一个度为2的结点，叶子结点就增加一个。
3. 几种特殊形式的二叉树
(1) 满二叉树:
深度为h含有2h-1个结点的二叉树为满二叉树。图2.36所示为一棵深度为4的满二叉树。

(2) 完全二叉树
如果一棵n个结点的二叉树，按与满二叉树相同的编号方式对结点进行编号，若树中n个结点和满二叉树1～n编号完全一致，则称该树 为完全二叉树，如图2.37(a)所示；而图2.37(b)就不是完全二叉树。渗釤呛俨匀谔鱉调硯錦。

(3) 平衡二叉树
平衡二叉树或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树 ，且左子树和右子树的深度之差的绝对值不超过1。图2.38(a)为平衡二叉树，(b)为不平衡二叉树。铙誅卧泻噦圣骋贶頂廡。

4. 一般树转换为二叉树
(1) 在兄弟结点之间加一连线；
(2) 对每个结点，除了与它的第一个孩子保持联系外，去除与其它孩子的联系；
(3) 以树根为轴心，将整棵树顺时针旋转45°。

2.5.3二叉树的遍历
遍历是指遵循某条搜索路线，依次访问某数据结构中的全部结点，而且每个结点只被访问一次。
1. 遍历二叉树的定义
DLR，LDR，LRD，DRL，RDL，RLD六种遍历形式。
若规定先左后右，则归并成下述三种形式：
DLR：先序遍历
LDR：中序遍历
LRD：后序遍历
以图2.40中的二叉树为例，三种遍历结果为：
先序：ABCDEFG
中序：CBDAEGF
后序：CDBGFEA

2. 遍历算法
PROORDER(p)//先序遍历//
1.if (p<>nil) then
2.{write(data(p)); //访问根结点//
3.PROORDER (L child(p));//遍历左子树//
4.PROORDER (R child(p));//遍历右子树//
5.return

FR

FR1

BR

BR1

ER

ER1
ER1
ER1
ER1
ER1

AR
AR
AR
AR
AR

AR1
AR1
AR1
AR1
AR1
AR1
AR1
AR1
AR1

A B C D E F G擁締凤袜备訊顎轮烂蔷。

G

G1

C

C1

D

D1

F
F
F
F
F

F1

B
B
B
B
B
B1
B1
B1
B1

E

E1
E1
E1
E1
E1
E1
E1
E1
E1

A
A
A
A
A
A
A
A
A
A
A

A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1

A
B
C

D

E

F
G

先

C

B

D

A

E

G

F

中

C

D
B

G

F
E
A
后
INORDER(p)//中序遍历//
1.if (p<>nil) then
2.{INORDER(L,child(p)); //遍历左子树//
3. write (data(p)); //访问根结点//
4. INORDER(R,child(p)); //遍历右子树//
5．Return

FR

FR1

BR

BR1

ER

ER1
ER1
ER1
ER1
ER1

AR
AR
AR
AR
AR

AR1
AR1
AR1
AR1
AR1
AR1
AR1
AR1
AR1

C B D A E G F
POSTORDER(p)//后序遍历//
1.if (p<>nil) then
2.{POSTORDER(L,child(p)); //遍历左子树//
3. POSTORDER(R,child(p)); //遍历右子树//
4. write (data(p)); //访问根结点//
5．Return

FR

FR1

BR

BR1

ER

ER1
ER1
ER1
ER1
ER1

AR
AR
AR
AR
AR

AR1
AR1
AR1
AR1
AR1
AR1
AR1
AR1
AR1

C D B G F E A贓熱俣阃歲匱阊邺镓騷。
统计二叉树中的叶子结点数
//p指向根结点,count为计数器，初值为0
1.if (p<>nil) then
2.{if (L child(p)=nil) and (R child=nil)
3. then count←count +1
4. COUNTLEFT(L,child(p));
5. COUNTLEFT(R,child(p))};
6.return(count)
2.5. 4二叉树的应用
1. 二叉排序树
(1)定义
二叉排序树或是空树，或是具有下述性质的二叉树：其左子树上所有结点的数据均小于根结点的数据值；右子树上所有结点的数据值均大于或等于根结点的数据值。左子树和右子树又各是一棵二叉排序树。图2.41所示就是一棵二叉排序树。坛摶乡囂忏蒌鍥铃氈淚。

在二叉排序树中，若按中序遍历就可以得到由小到大的有序序列，如图2.41中的二叉排序树，中序遍历可得到有序序列{2,3,4,8,9,9,10,13,15,18,21}。蜡變黲癟報伥铉锚鈰赘。
(2)二叉排序树的生成
二叉排序树是一种动态表结构，即二叉排序树的生成过程是不断地向二叉排序树中插入新的结点。
对任意的一组数据元素序列{R1，R2，…，Rn}，要生成一棵二叉排序树的过程为：
<1>令R1为二叉排序树的根结点。
<2>若R2<R1，令R2为R1的左子树的根结点；否则R2为R1的右子树的根结点。
<3>R3，…，Rn结点的插入方法同上。
二叉排序树插入算法如下：
INSERBET(t,b) // 将数值b插入根结点指针为t的二叉排序树中,此函数返回值为指向根结点t的指针//買鲷鴯譖昙膚遙闫撷凄。
1.if (t=nil) then //生成一个新结点,其数值域为b//
2. {GETNODE(t); data(t)←b;L child(t)←nil;R child(t)←nil}綾镝鯛駕櫬鹕踪韦辚糴。
3.else if (b<data(t) then
4. {L child(t)←INSERTBET(L child(t),b)}//插入左子树//
5. else
6. {R child(t)←INSERTBET(R child(t),b)} //插入右子树//
7.return(t)
图2.42所示为序列{10，18，3，8，12，2，7，3} 构成一棵二叉排序树的过程。

(3)删除二叉排序树上的结点
删除二叉排序树上的一个结点，也就是要在已排好序的序列中删除一个元素，因此要求删除一个结点后二叉树仍然是一棵二叉排序树。驅踬髏彦浃绥譎饴憂锦。
删除二叉排序树上结点过程较插入过程复杂，按照被删除结点在二叉排序树中的位置，可以有以下几种情况：
<1>被删除结点是叶子结点，则删除后不会影响整个二叉排序树的结构，因此只需修改它双亲结点的指针即可。
<2>被删除结点P只有左子树PL或右子树PR，此时只要将左子树或右子树直接成为其双亲结点F的左或右子树即可，见图2.43(a)所示。猫虿驢绘燈鮒诛髅貺庑。
<3>若被删除结点P的左右子树均为非空。这是要循着P的左子树的根结点C，向右一直找到结点S，要求S的右子树为空。然后将S 的左子树改为结点Q的右子树，将S结点的数据域值取代P结点的数据域值，删除前后如图2.43(b)(c)所示。锹籁饗迳琐筆襖鸥娅薔。
<4>若被删除的结点为二叉排序树的根结点，则删除后应修改根结点指针。

算法如下：
DELNODE(t,p,f)//t为根结点指针,p指向被删除结点,f指向其双亲,当p=t时 f=nil//構氽頑黉碩饨荠龈话骛。
1.fag←0//fag=0需要修改F结点指针,fag=1不需修改//
2.if (L child(p)=nil) then s←R child(p)//p为叶子或左子树为空// s为所要替代p的子树輒峄陽檉簖疖網儂號泶。
3.else if (R child(p)=nil) then s←L child(p)
//p的右子树为空//
4.else {q←p;s←L child(p) //p的左右子树均非空//
5. while (R child(s)<>nil) do
6. { q←s;s←R child(s)}//寻找s结点//
7. if (q=p) then L child(q)←L child(s)
8． else R child(q)←L child(s)
9. data(p)←data(s) //s值代替p值//
10. RET(s); fag←1 //释放s结点//}
11.if (fag=0) then //修改F结点指针//
12 {if (f=nil) then t←s
//被删除结点为根结点//
13.else if (L child(f)=p)
then L child(f)←s
14. else R child(f)←s
15. RET(p) //释放结点p//
16.return
2. 哈夫曼树
哈夫曼树又称最优树，是一类带权路径最短的树。
(1)树的路径长度
从树中一个结点到另一个结点之间的分支数目称为这对结点之间的路径长度。树的路径长度是从树根到每个结点的路径长度之和。路径长度用PL表示，图2.44中(a)(b)两棵树 的路径长度分别为：尧侧閆繭絳闕绚勵蜆贅。
(a) PL=0+1+2+2+3+4+5=17；
(b) PL=0+1+1+2×4+3=13。

在任何二叉树中，都存在如下情况：
路径为0的结点至多只有1个；
路径为1的结点至多只有2个；
……
路径为k的结点至多只有2k个。
因此，n个结点的二叉树路径长度满足

log21+log22+log23+log24+log25+log26+log27+log28+…………识饒鎂錕缢灩筧嚌俨淒。
=0+1+1+2+2+2+2+3+…………
从上述关系可知，具有最小路径长度的二叉树为完全二叉树。
(2)树的带权路径长度
结点带权路径长度为 该结点到树根之间的路径长度与结点上权值的乘积。
树的带权路径长度为树中叶子结点的带权路径长度之和，记作

其中wk为树中每个叶子结点的权值，lk为每个叶子结点到根结点的路径长度。WPL最小的二叉树称作最优二叉树或哈夫曼树。凍鈹鋨劳臘锴痫婦胫籴。
例如图2.45中的三棵二叉树，都有4个叶子结点a，b，c，d，分别具有权值7，5，2，4，它们带权路径长度分别为：恥諤銪灭萦欢煬鞏鹜錦。
(a) WPL=7*2+5*2+2*2+4*2=36
(b) WPL=7*3+5*3+2*1+4*2=46
(c) WPL=7*1+5*2+2*3+4*3=35
其中以(c)为最小，可以验证(c)为哈夫曼树。

(3)哈夫曼树的构造
原则：权值越大的叶子离根结点的距离越近。
<1>由给定的n个权值{w1，w2，…，wn}构成n棵二叉树的集合F={T1，T2，…，Tn}，其中每棵二叉树只有一个权值为wi的根结点，如图2.46(a)所示。鯊腎鑰诎褳鉀沩懼統庫。
<2>在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和，如图2.46(b)所示。硕癘鄴颃诌攆檸攜驤蔹。
<3>将新的二叉树假如F中，去除原两棵根结点权值最小的树。
<4>重复<2>,<3>两步骤，直到F中只含一棵树为止。这棵树 就是哈夫曼树，如图2.46(d)所示。阌擻輳嬪諫迁择楨秘騖。

在计算机上实现上述算法，首先要确定存储结构，由于哈夫曼树中没有度为1的结点，因此一棵有n个叶子结点的哈夫曼树共有2n-1个结点。结点采用数组型链表结构每个结点由4个数据域组成，即氬嚕躑竄贸恳彈瀘颔澩。
date:存放结点权值
L child:左指针
R child:右指针
Prnt:双亲指针
算法如下：
HUFFMAN(n,L child,R child,data,Prnt,w)
//w[1:n]存放n个权值,
L child[1:m],R child[1:m],data[1:m],
Prnt[1:m],m=2n-1//
1.for i=1 to n
2. data[i]←w[i];L child(i)←0;
R child(i)←0 //初始化//
3.end(i)
4.for i=1 to (2*n-1) Prnt[i]←0//初始化//
5.end(i)
6．for k=n+1 to (2*n-1)
7. SELECT(k-1,i,j)//从data[1:k-1]中选出双亲为零的两个权值最小的下标i,j// 釷鹆資贏車贖孙滅獅赘。
8. data[k]←data[i]+date[j]
9. L child[k]←i; R child[k]←j;
10. Prnt[i]←k; Prnt[j]←k;
11.end(k)
12.return
对应图2.46中哈夫曼树的存储空间的初始状态为图2.47(a)，最终状态为图2.47(b)。

data
Prnt
L chil
R chil
1

2

3

4

5

6

7

(4)哈夫曼树的应用
最佳判定算法
分数段
0～59
60～69
70～79
80～89
90～100
比例
0.05
0.15
0.40
0.30
0.10

COUNTLEFT(A,count)
//p指向根结点,count为计数器，初值为0
1.if (p<>nil) then
2.{if (L child(p))=nil} and (R child=nil)
3. then count←count +1
4. *COUNTLEFT(L,child(p));
COUNTLEFT(B,count)
//p指向根结点,count为计数器，初值为0
1.if (p<>nil) then
2.{if (L child(p))=nil} and (R child=nil)
3. then count←count +1
4. *COUNTLEFT(L,child(p));
COUNTLEFT(C,count)
//p指向根结点,count为计数器，初值为0
1.if (p<>nil) then
2.{if (L child(p))=nil} and (R child=nil)
3. then count←count +1
4. *COUNTLEFT(L,child(p));
COUNTLEFT(NIL,count)
//p指向根结点,count为计数器，初值为0
1.if (p<>nil) then
2.{if (L child(p))=nil} and (R child=nil)
3. then count←count +1
4. *COUNTLEFT(L,child(p));
5. COUNTLEFT(R,child(p));
6.return

5. COUNTLEFT(R,child(p));
COUNTLEFT(NIL,count)
//p指向根结点,count为计数器，初值为0
1.if (p<>nil) then
2.{if (L child(p))=nil} and (R child=nil)
3. then count←count +1
4. *COUNTLEFT(L,child(p));
5. COUNTLEFT(R,child(p));
6.return
6.return
5. COUNTLEFT(R,child(p));
COUNTLEFT(D,count)
//p指向根结点,count为计数器，初值为0
1.if (p<>nil) then
2.{if (L child(p))=nil} and (R child=nil)
3. then count←count +1
4. *COUNTLEFT(L,child(p));
COUNTLEFT(NIL,count)
//p指向根结点,count为计数器，初值为0
1.if (p<>nil) then
2.{if (L child(p))=nil} and (R child=nil)
3. then count←count +1
4. *COUNTLEFT(L,child(p));
5. COUNTLEFT(R,child(p));
6.return
5. COUNTLEFT(R,child(p));
COUNTLEFT(NIL,count)
//p指向根结点,count为计数器，初值为0
1.if (p<>nil) then
2.{if (L child(p))=nil} and (R child=nil)
3. then count←count +1
4. *COUNTLEFT(L,child(p));
5. COUNTLEFT(R,child(p));
6.return

6.return
6.return
5. COUNTLEFT(R,child(p));
COUNTLEFT(E,count)
//p指向根结点,count为计数器，初值为0
1.if (p<>nil) then
2.{if (L child(p))=nil} and (R child=nil)
3. then count←count +1
4. *COUNTLEFT(L,child(p));
COUNTLEFT(NIL,count)
//p指向根结点,count为计数器，初值为0
1.if (p<>nil) then
2.{if (L child(p))=nil} and (R child=nil)
3. then count←count +1
4. *COUNTLEFT(L,child(p));
5. COUNTLEFT(R,child(p));
6.return
5. COUNTLEFT(R,child(p));
COUNTLEFT(F, count)
//p指向根结点,count为计数器，初值为0
1.if (p<>nil) then
2.{if (L child(p))=nil} and (R child=nil)
3. then count←count +1
4. *COUNTLEFT(L,child(p));
COUNTLEFT(G, count)
//p指向根结点,count为计数器，初值为0
1.if (p<>nil) then
2.{if (L child(p))=nil} and (R child=nil)
3. then count←count +1
4. *COUNTLEFT(L,child(p));
5. COUNTLEFT(R,child(p));
6.return
5. COUNTLEFT(R,child(p));
COUNTLEFT(NIL,count)
//p指向根结点,count为计数器，初值为0
1.if (p<>nil) then
2.{if (L child(p))=nil} and (R child=nil)
3. then count←count +1
4. *COUNTLEFT(L,child(p));
5. COUNTLEFT(R,child(p));
6.return
6.return

6.return

6.return