《數(shù)據(jù)結(jié)構(gòu)-C語言描述》樹_第1頁
《數(shù)據(jù)結(jié)構(gòu)-C語言描述》樹_第2頁
《數(shù)據(jù)結(jié)構(gòu)-C語言描述》樹_第3頁
《數(shù)據(jù)結(jié)構(gòu)-C語言描述》樹_第4頁
《數(shù)據(jù)結(jié)構(gòu)-C語言描述》樹_第5頁
已閱讀5頁,還剩62頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

第六章

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

樹二叉樹的遍歷與線索化樹和森林哈夫曼樹及其應(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;

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論