《數(shù)據(jù)結(jié)構(gòu)-C語言描述》樹

第六章

樹和二叉樹樹的概念與定義二

叉

樹二叉樹的遍歷與線索化樹和森林哈夫曼樹及其應(yīng)用樹的計數(shù)6.1樹的概念與定義樹的定義：樹(tree)是n(n≥0)個結(jié)點的有限集T，當n=0時，稱為空樹；當n>0時，滿足以下條件：有且僅有一個結(jié)點被稱為樹根（root結(jié)點；當n>1時，除根結(jié)點以外的其余n-1個結(jié)點可以劃分成m(m>0)個互不相交的有限集T1,T2,…，Tm，其中每一個集合本身又是一棵樹，稱為根的子樹(subtree)。圖6.1·結(jié)點(node)：表示樹中的元素，包括數(shù)據(jù)項及若干指向其子樹的分支?！そY(jié)點的度(degree)：結(jié)點擁有的子樹的數(shù)目。圖6.1中結(jié)點A的度為3?！と~子(leaf)：度為0的結(jié)點稱為葉子結(jié)點，也稱為終端結(jié)點。圖6.1中，葉子結(jié)點有：K，L，F(xiàn)，G，M，I，J?！し种ЫY(jié)點：度不為0的結(jié)點稱為分支結(jié)點，也稱為非終端結(jié)點。圖6.1中，非終端結(jié)點有：A，B，C，D等?！ず⒆咏Y(jié)點(child)：結(jié)點的子樹的根稱為該結(jié)點的孩子結(jié)點。圖6.1中，結(jié)點A的孩子結(jié)點為B，C，D，結(jié)點B的孩子結(jié)點為E，F(xiàn)?！るp親結(jié)點(parents)：孩子結(jié)點的上層結(jié)點稱為該結(jié)點的雙親結(jié)點。圖6.1中，結(jié)點I的雙親為D，結(jié)點L的雙親為

E?！ば值芙Y(jié)點(sibling)：具有同一雙親結(jié)點的孩子結(jié)點之間互稱為兄弟結(jié)點。圖6.1中，結(jié)點B，C，D互為兄弟，結(jié)點K，L互為兄弟?！涞亩龋簶渲凶畲蟮慕Y(jié)點的度數(shù)即為樹的度。圖6.1中的樹的度為3。·結(jié)點的層次(level)：從根結(jié)點算起，根為第一層，它的孩子為第二層……。若某結(jié)點在第l層，則其孩子結(jié)點就在

第l+1層。圖6.1中，結(jié)點A的層次為1，結(jié)點M的層次為4。·樹的高度(depth)：樹中結(jié)點的最大層次數(shù)。圖6.1中的樹的高度為4?！ど?forest)：m(m≥0)棵互不相交的樹的集合?！び行驑渑c無序樹：樹中結(jié)點的各子樹從左至右是有次序的（不能互換）則稱該樹為有序樹，否則稱該樹為無序樹。6.2

二叉樹二叉樹的定義：二叉樹是由n(n≥0)個結(jié)點的有限集T構(gòu)成，此集合或者為空集，或者由一個根結(jié)點及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。注意：二叉樹的子樹有左右之分，因此二叉樹是一種有序樹。二叉樹的性質(zhì)：性質(zhì)1

在二叉樹的第i層上至多有2i-1個結(jié)點(i≥1)。性質(zhì)2

深度為k的二叉樹至多有2k－1個結(jié)點（k>=1）。性質(zhì)3

對任意一棵二叉樹BT，如果其葉子結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0＝n2＋1。性質(zhì)4

具有n個結(jié)點的完全二叉樹的深度為【log2n】＋1。（符號【x】表示不大于x的最大整數(shù)。）二叉樹的性質(zhì)：性質(zhì)5

對于具有n個結(jié)點的完全二叉樹如果對其結(jié)點按層次編號，則對任一結(jié)點

i(1≤i≤n)，有：(1)如果i=1，則結(jié)點i是二叉樹的根，無親；如果i>1，則其雙親是【i/2】(2)

如果2i>n，則結(jié)點i無左孩子；如果2in，則其左孩子是2i(3)

如果2i+1>n，則結(jié)點i無右孩子；如果

2i+1≤n，則其右孩子是2i+1滿二叉樹：一棵深度為k且有2k-1個結(jié)點的二叉樹稱為滿二叉樹。完全二叉樹：深度為k，有n個結(jié)點的二叉樹當且僅當其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時，稱為完全二叉樹。12345896710

11

12

13

14

1512345896710

11

121234567123456二叉樹的存儲結(jié)構(gòu)·

順序存儲結(jié)構(gòu)

:為了能夠反映出結(jié)點之間的邏輯關(guān)系，必須將它“修補”成完全二叉樹，對應(yīng)該完全二叉樹，可以開辟長度為12的數(shù)組，對12個數(shù)據(jù)元素進行存儲，原二叉樹中空缺的結(jié)點在數(shù)組中的相應(yīng)單元必須置空a

b

c

d

e

φ

φ

φ

φ

f

g二叉樹的存儲結(jié)構(gòu)·

鏈式存儲結(jié)構(gòu)

:表示二叉樹的鏈表中的結(jié)點應(yīng)該包含3個域：數(shù)據(jù)域和指向左、右子樹的指針域，二叉樹的這種存儲結(jié)構(gòu)被稱為二叉鏈表。Lchild

data

rchild在n個結(jié)點的二叉鏈表中，有n+1個空指針域6.3

二叉樹的遍歷與線索化二叉樹的遍歷：是按某條搜索路徑訪問樹中的每一個結(jié)點，使得每一個結(jié)點均被訪問一次，而且僅被訪問一次。先根遍歷二叉樹（1）訪問根結(jié)點；（2）先根遍歷左子樹；（3）先根遍歷右子樹。中根遍歷二叉樹·（1）中根遍歷左子樹；·（2）訪問根結(jié)點；·（3）中根遍歷右子樹。后根遍歷二叉樹·（1）后根遍歷左子樹；·（2）后根遍歷右子樹；·（3）訪問根結(jié)點。先根遍歷:

-+a*b–cd/ef中根遍歷:

a+b*c–d–e/f后根遍歷:

abcd-*+ef/-typedef

struct

Node{datatype

data;struct

Node

*Lchild;struct

Node

*Rchild;}

BTnode,*Btree;·先根遍歷算法void

preorder(Btree

root){if(root!=NULL){Visit(root->data);preorder(root->Lchild);preorder(root->Rchild);}}·中根遍歷算法void InOrder(Btree

root){if(root!=NULL){InOrder(root->Lchild);Visit(root->data);InOrder(root->Rchild);}}·后根遍歷算法void PostOrder(Btree

root){if(root!=NULL){PostOrder(root->Lchild);PostOrder(root->Rchild);Visit(root

->data);}}線索二叉樹：利用二插鏈表剩余的n+1個空指針域來存放遍歷過程中結(jié)點的前驅(qū)和后繼的指針，這種附加的指針稱為“線索”，加上了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹稱為線索二叉樹。為了區(qū)分結(jié)點的指針域是指向其孩子的指針，還是指向其前驅(qū)或后繼的線索，可在二叉鏈表的結(jié)點中,再增設(shè)2個標志域。Lchild

Ltag

Data

Rtag

RchildLchild域指示結(jié)點的左孩子Ltag=Lchild域指示結(jié)點的遍歷前驅(qū)Rchild域指示結(jié)點的右孩子Rtag=Rchild域指示結(jié)點的遍歷后繼中序線索二叉樹·

基于遍歷的應(yīng)用與線索二叉樹的應(yīng)用二叉樹的遍歷是對二叉樹進行各種運算的一個重要基礎(chǔ)，對訪問（程序中的visit函數(shù)）結(jié)點可理解為各種對二叉樹中結(jié)點進行操作。因此，只要將二叉樹三種遍歷算法中的visit函數(shù)具體化，就產(chǎn)生了基于二叉樹的不同應(yīng)用?！?/p>

輸出二叉樹中的結(jié)點Void

paintnode

(Btree

root){if

(root!=NULL){printf

(root

->data);paintnode

(root

->Lchild);paintnode

(root

->Rchild);}}·

輸出二叉樹中的葉子結(jié)點Void

paintleaf

(Btree

root){if

(root!=NULL){if

(root

->Lchild==NULL

&&

root

->Rchild==NULL)printf

(root

->data);paintleaf

(root

->Lchild);paintleaf

(root

->Rchild);}}·

統(tǒng)計葉子結(jié)點數(shù)目Void

leafcount(Btree

root){if(root!=NULL){leafcount(root->Lchild);leafcount(root->Rchild);if

(root

->Lchild==NULL

&&

root

->Rchild==NULL)count++;}}提示：count為全局變量，在主函數(shù)中定義?！?/p>

建立二叉樹圖中二叉樹的先根遍歷序列為：

ABDGCEHF，而考慮空子樹后的先根遍歷序列應(yīng)為：ABD．G．CE．HF，其中“．”代表空子樹。如果已知二叉樹的考慮了空子樹后的遍歷序列，那么建立這棵二叉樹的算法如下(假定datatype類型為char)Void

CreateBtree(Btree

*bt){char

ch;ch=getchar();if(ch==".")*bt=NULL;else{*bt=(Btree)malloc(sizeof(BTnode));(*bt)->data=ch;CreateBiTree(&((*bt)->Lchild));CreateBiTree(&((*bt)->Rchild));}}·

求二叉樹的高度采用遞歸的方法定義二叉樹的高度：若二叉樹為空，則高度為0；若二叉樹非空，其高度應(yīng)為其左右子樹高度的最大值加1。int

TreeDepth(Btree

bt){int

hl,hr,max;if(bt!=NULL){hl=TreeDepth(bt->Lchild);hr=TreeDepth(bt->Rchild);max=(hl，hr);return(max+1);}else

return(0);}·

在中根遍歷的線索樹中查找前驅(qū)結(jié)點對于二叉樹中任意結(jié)點p，要找其前驅(qū)結(jié)點,當p->Ltag=1時，p->Lchild即為p的前驅(qū)結(jié)點；當p->Ltag=0時，說明

p有左子樹，此時p的中根遍歷下的前驅(qū)結(jié)點即為其左子右鏈下的最后一個結(jié)點。Void

Previous(ThreadTnode

*

p,

ThreadTnode

*pre){

ThreadTnode

*q;if(p->Ltag==1)

pre=

p->Lchild;else{for(q=

p->Lchild;q->Rtag==0;q=q->Rchild);pre=q;}}·

在中根遍歷的線索樹中查找后繼結(jié)點二叉樹中任意結(jié)點p，若要找其后繼結(jié)點，當p->Rtag=1時，p->Rchild即為p的后繼結(jié)點；當p->Rtag=0時，說明

p有右子樹，此時p的中根遍歷下的后繼結(jié)點即為其右子左鏈下的最后一個結(jié)點。Void

Succedent(ThreadTnode

*p,

ThreadTnode

*succ){

ThreadTnode

*q;if

(p->Rtag==1)succ=

p->

RChild;else{for(q=

p->RChild;

q->Ltag==0

;q=q->LChild

);succ=q;}}6.4

樹和森林·樹的存儲結(jié)構(gòu)雙親（鏈表）表示法用一組連續(xù)的存儲空間（數(shù)組）來存儲樹中的結(jié)點，每個組元素中不但包含結(jié)點本身的信息，還保存該結(jié)點雙親結(jié)點在數(shù)組中的下標號。數(shù)組中每個結(jié)點含兩個域：數(shù)據(jù)域：存放結(jié)點本身信息雙親域：指示本結(jié)點的雙親結(jié)點在數(shù)組中位置在雙親表示法下，樹的數(shù)據(jù)類型定義如下：

#define

Maxsize

50typedef

struct

Node{DataType

data;int

parent;}Tnode;Tnode

Ptree[Maxsize];abcdefhgidataparent0a－11b12c13d24e25f36g57h58i5如何找孩子結(jié)點·孩子鏈表表示法把每個結(jié)點的孩子結(jié)點排列起來，構(gòu)成一個單鏈表，該鏈表就是本結(jié)點的孩子鏈表。具有n個結(jié)點的樹就形成了個孩子鏈表·孩子結(jié)點·#define

Maxsize

50typedef

struct

ChildNode{int

Child;struct

ChildNode

*

next;}ChildNode;·表頭結(jié)點typedef

struct{DataType

data;ChildNode

*

ChildHead

;}DataNode;·孩子鏈表·DataNode

Ctree[Maxsize];·

孩子兄弟鏈表表示法又稱為二叉鏈表表示法，即以二叉鏈表作為樹的存儲結(jié)構(gòu)。鏈表中每個結(jié)點設(shè)有兩個鏈域，與二叉樹的二叉鏈表表示法所不同是，這兩個鏈域分別指向該結(jié)點的第一個孩子結(jié)點和下一個兄弟（右兄弟）。dataNextsiblingFirstChildtypedef

struct

CSNode{DataType

data;Struct

CSNode

*FirstChild,

*Nextsibling;}

*CSTree;對應(yīng)結(jié)論：樹的孩子兄弟鏈表表示法與對應(yīng)二叉樹的二插鏈表表示法相同。因此，上圖中的樹與二叉樹之間存在相互轉(zhuǎn)換的關(guān)系。BEFGDA

AC

D

B

CH

I

E

F

GHIABCDEFGHIABCDEABCDEFGHIF

G

H

I樹轉(zhuǎn)換成的二叉樹其右子樹一定為空·樹轉(zhuǎn)換為二叉樹加線：在樹中所有相鄰的兄弟之間加一連線；抹線：對樹中每個結(jié)點，除了其左孩子外抹去該結(jié)點與其孩子之間的連線。整理：以樹的根結(jié)點為軸心，將整樹順時針轉(zhuǎn)45°?！ど洲D(zhuǎn)換成二叉樹·將各棵樹分別轉(zhuǎn)換成二叉樹將每棵樹的根結(jié)點用線相連以第一棵樹根結(jié)點為二叉樹的根，再以根結(jié)點為軸心，順時針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu)ABCDFE

GHIJBCDEFA

GHIJABCDEFGHIJABCDEFGHIJ·二叉樹轉(zhuǎn)換成樹·加線：若p結(jié)點是雙親結(jié)點的左孩子，則將p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都與p的雙親用線連起來·抹線：抹掉原二叉樹中雙親與右孩子之間的連線·調(diào)整：將結(jié)點按層次排列，形成樹結(jié)構(gòu)EGHIA

ACDB

BC

EF

D

FGHIEGHIA

ACDB

BC

EF

D

FGHIABCDEFGHI·二叉樹轉(zhuǎn)換成森林·

抹線：將二叉樹中根結(jié)點與其右孩子連線，及沿右分支·搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二樹·還原：將孤立的二叉樹還原成樹ABCDEFGHIJABCDEFGHIJBCDEFA

GHIJABCDEFGHIJ·樹和森林的遍歷樹的遍歷先根遍歷若樹非空，則遍歷方法為：a.訪問根結(jié)點。b.從左到右，依次先根遍歷根結(jié)點的每一棵子樹。后根遍歷若樹非空，則遍歷方法為：a.從左到右，依次后根遍歷根結(jié)點的每一棵子樹。b.訪問根結(jié)點。按層次遍歷若樹非空，則遍歷方法為：先訪問第一層上的結(jié)點，然后依次遍歷第二層，……第n層的結(jié)點。ABCDEFGHIJ

K

L

MNO先根遍歷：A

B

E

F

I

G

C

D

H

J

K

L

N

O

M后根遍歷：E

IF

G

B

C

JK

N

O

L

M

H

D

A層次遍歷：A

B

C

D

E

F

G

H

I

J

K

L

M

N

O·森林的遍歷·先根遍歷·若森林非空，則遍歷方法為：a.訪問森林中第一棵樹的根結(jié)點。b.先根遍歷第一棵樹的根結(jié)點的子樹森林。c.先根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林?！ぶ懈闅v若森林非空，則遍歷方法為：·a.中根遍歷森林中第一棵樹的根結(jié)點的子樹森林。·b.訪問第一棵樹的根結(jié)點。c.中根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林?！ず蟾闅v·若森林非空，則遍歷方法為：a.后根遍歷森林中第一棵樹的根結(jié)點的子樹森林。b.后根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。c.訪問第一棵樹的根結(jié)點。先根遍歷：ABCDEFGHIJ中根遍歷：BCDAFEHJIG后根遍歷：DCBFJIHGEA6.5

哈夫曼樹及其應(yīng)用與哈夫曼樹相關(guān)的基本概念路徑和路徑長度路徑：從一個結(jié)點到另一個結(jié)點之間的分支序列。路徑長度：是指從一個結(jié)點到另一個結(jié)點所經(jīng)過的分支數(shù)目。結(jié)點的權(quán)和帶權(quán)路徑長度結(jié)點的權(quán)：在實際的應(yīng)用中，人們常常給樹的每個結(jié)點賦予一個具有某種實際意義的數(shù)值，我們稱該數(shù)值為這個結(jié)點的權(quán)。結(jié)點的帶權(quán)路徑長度：從樹根到某一結(jié)點的路徑長度與該結(jié)點的權(quán)的乘積，叫做該結(jié)點的帶權(quán)路徑長度。樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度是指樹中所有葉子結(jié)點的帶權(quán)路徑長之和?！涞膸?quán)路徑長度樹的帶權(quán)路徑長度是指樹中所有葉子結(jié)點的帶權(quán)路徑長度之和?！す蚵鼧涔蚵鼧洌菏怯蒼個帶權(quán)葉子結(jié)點構(gòu)成的所有二叉樹中帶權(quán)路徑長度WPL最小的二叉樹。哈夫曼樹又叫最佳判定樹。例：有4個結(jié)點，權(quán)值分別為7，5，2，4，構(gòu)造有4個葉子結(jié)點的二叉樹ab

cd7

5

2

4WPL=7*2+5*2+2*2+4*2=36dcb2a745WPL=7*3+5*3+2*1+4*2=46abc

d752

4WPL=7*1+5*2+2*3+4*3=35·構(gòu)造Huffman樹的方法——Huffman算法·

構(gòu)造Huffman樹步驟根據(jù)給定的n個權(quán)值{w1,w2,……wn}，構(gòu)造n棵只有根結(jié)點的二叉樹，令起權(quán)值為wj在森林中選取兩棵根結(jié)點權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點權(quán)值為其左右子樹根結(jié)點權(quán)值之和在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中重復上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹例7

5

2

4a

b

c

d7a5b2

4c

d67a5b2

4c

d6117a5b2

4c

d61118例w={5,29,7,8,14,23,3,11}5

2929

733

118157

829

145

378142381423115231181181929

14

23

157

8115

3829

23

1914157

85

32929147

829115

381915

234211819234214157

829

2958115

381923422914157

829585

3100·

哈夫曼樹的應(yīng)用·

最佳判定樹·

學生成績的分布呈正態(tài)分布即：中等成績的學生較多，而較好或較差學生均比較少。設(shè)其分布規(guī)律如下表：等級不及格及格中等良好優(yōu)秀分數(shù)段0~5960~6970~7980~8990~100比例5％15％40％30％10％（a）（b）若采用圖（a）來進行判斷，則80%以上的數(shù)據(jù)要進行三次或三次以上的比較才能得到結(jié)果。而如果我們以各分數(shù)段人數(shù)的占總?cè)藬?shù)的比例5、15、40、30、10為權(quán)值構(gòu)造哈夫曼樹，可得到（b）所示的判定樹來進行判斷可以使大部分數(shù)據(jù)經(jīng)過較少次數(shù)的比較得到結(jié)果?！?/p>

哈夫曼編碼哈夫曼樹還被廣泛的應(yīng)用在編碼技術(shù)中。利用哈夫曼樹，我們可以得到平均長度最短的編碼。設(shè)有一臺模型機，共有7種不同的指令，其使用頻率如下：為了充分地利用編碼信息和減少程序的總位數(shù)，我們考慮采用變長編碼。如果對每一條指令指定一條編碼，使得這些編碼互不相同且最短。若要設(shè)計變長的編碼，這種編碼必須滿足這樣一個條件：任意一個編碼不能成為其它任意編碼的前綴。我們把滿足這個條件的編碼叫做前綴編碼。利用哈夫曼算法，可以設(shè)計出最優(yōu)的前綴編碼。以每條指令的使用頻率為權(quán)值構(gòu)造哈夫曼樹，構(gòu)造結(jié)果如圖所示：·哈夫曼編碼算法的實現(xiàn)數(shù)據(jù)類型的定義如下：typedef

struct

Node{int

weight

;int

parent,

LChild,RChild

;}

HTNode,

*

HTree;typedef

char

*

*HuffmanCode

;創(chuàng)建哈夫曼樹并求哈夫曼編碼的算法如下：viod

CreatHTree(HTree

*ht

,

HuffmanCode

*hc,int

*

w,int

n){/*w存放n個權(quán)值,構(gòu)造哈夫曼樹ht,并求出哈夫曼編碼hc

*/int

start;m=2*n-1;*ht=(HTree)malloc((m+1)*sizeof(HTNode));for(i=1;i<=n;i++)(*ht)[i]

={

w[i],0,0,0};for(i=n+1;i<=m;i++)(*

ht)[i]={0,0,0,0};/*初始化*/for(i=n+1;i<=m;i++){select(ht,i-1,&s1,&s2);/*在(*ht)[1]~(*ht)[i-1]的范圍內(nèi)選擇兩個parent為0且weight最小的結(jié)點，其序號分別賦值給s1、s2返回，select函數(shù)要求在上機調(diào)試使補充定義*/(*ht)[s1].parent=i;(*ht)[s2].parent=i;