版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領
文檔簡介
1數(shù)據(jù)結構及應用算法教程(修訂版)配套課件2第6章二叉樹和樹
前面的章節(jié)主要討論的是線性結構,二叉樹和樹屬于非線性的結構。遍歷非線性結構比線性結構要麻煩。二叉樹及樹的遍歷技術是本章各種算法的核心,而且大多是以遞歸的形式表現(xiàn)的,閱讀和編寫遞歸算法是學習本章的難點。講授本章課程大約需8課時。3
樹結構的特點及基本術語
6.1二叉樹
6.2二叉樹的遍歷
6.3樹和森林
6.4樹的應用4樹結構的特點及基本術語
5線性結構樹型結構第一個數(shù)據(jù)元素
(無前驅(qū))
根結點
(無前驅(qū))最后一個數(shù)據(jù)元素
(無后繼)多個葉子結點
(無后繼)其它數(shù)據(jù)元素(一個前驅(qū)、一個后繼)其它數(shù)據(jù)元素(一個前驅(qū)、多個后繼)對比樹型結構和線性結構的結構特點6結點:數(shù)據(jù)元素+若干指向子樹的分支結點的度:分支的個數(shù)樹的度:樹中所有結點的度的最大值葉子結點:度為零的結點分支結點:度大于零的結點DHIJM基本術語7(從根到結點的)路徑:孩子結點、雙親結點兄弟結點、堂兄弟祖先結點、子孫結點
由從根到該結點所經(jīng)分支和結點構成ABCDEFGHIJMKL結點的層次:假設根結點的層次為1,第l
層的結點的子樹根結點的層次為l+1樹的深度:樹中葉子結點所在的最大層次層次-深度-高度,86.1二叉樹一、二叉樹的定義和基本術語二、二叉樹的幾個基本性質(zhì)三、二叉樹的存儲結構9一、二叉樹的定義和基本術語
10
二叉樹的定義
二叉樹是n(n≥0)個元素的有限集,它或為空樹,或是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。根結點左子樹右子樹ABCDEFGHKLB11二叉樹可以表現(xiàn)出五種基本形態(tài):空樹N只含根結點右子樹為空樹NL左子樹為空樹NR左右子樹均不為空樹NLR12
二叉樹的基本操作:
查找類的操作
插入類的操作
刪除類的操作13Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T);InOrderTraverse(T);PostOrderTraverse(T);LevelOrderTraverse(T);查找類的操作:14InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);插入類的操作:15ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);刪除類的操作:16二、二叉樹的幾個基本性質(zhì)17
性質(zhì)1:
在二叉樹的第i
層上至多有2i-1個結點(i≥1)。用歸納法證明:
歸納基:
歸納假設:
歸納證明:i=1
層時,只有一個根結點:
2i-1=20=1;假設對所有的j,1≤j
i,命題成立;二叉樹上每個結點至多有兩棵子樹,則第i層的結點數(shù)=2i-22=2i-1
。18
性質(zhì)2:
深度為k
的二叉樹上至多含
2k-1
個結點(k≥1)。證明:
基于上一條性質(zhì),深度為k的二叉樹上的結點數(shù)至多為
20+21+
+2k-1=2k-1
。19
性質(zhì)3:
對任何一棵二叉樹,若它含有n0個葉子結點、n2
個度為
2
的結點,則必存在關系式:n0=n2+1。證明:設二叉樹上結點總數(shù)n=n0+n1+n2又二叉樹上分支總數(shù)b=n1+2n2
而b=n-1=n0+n1+n2-1由此,n0=n2+1。20兩類特殊的二叉樹:滿二叉樹:指的是深度為k且含有2k-1個結點的二叉樹。完全二叉樹:樹中所含的n個結點和滿二叉樹中編號為1至n的結點一一對應。abcdefghij12345678910111213141521
性質(zhì)4:
具有n
個結點的完全二叉樹的深度為
log2n+1。證明:設完全二叉樹的深度為k則根據(jù)第二條性質(zhì)得2k-1≤n<2k
即k-1≤log2n<k
因為k只能是整數(shù),因此,k=log2n
+1。22
性質(zhì)5
:
若對含n個結點的完全二叉樹從上到下且從左至右進行1
至n
的編號,則對完全二叉樹中任意一個編號為i
的結點:
(1)若i=1,則該結點是二叉樹的根,無雙親,否則,編號為
i/2的結點為其雙親結點;
(2)若2i>n,則該結點無左孩子,
否則,編號為
2i的結點為其左孩子結點;
(3)若2i+1>n,則該結點無右孩子結點,
否則,編號為2i+1的結點為其右孩子結點。23三、二叉樹的存儲結構
二叉樹順序存儲表示二叉樹鏈式存儲表示24#defineMAX_TREE_SIZE100//二叉樹的最大結點數(shù)typedef
TElemTypeSqBiTree[MAX_TREE_SIZE];//0號單元存儲根結點SqBiTreebt;
二叉樹順序存儲表示25例如:
ABDCEF012345678910111213ABCDEF140132626
二叉樹鏈式存儲表示1.二叉鏈表2.三叉鏈表3.線索鏈表27ADEBCFroot結點結構:1.二叉鏈表lchilddatarchild28typedefstruct
BiTNode
{//結點結構
TElemTypedata;
structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;lchilddatarchild結點結構:C語言的類型描述如下:29rootADEBCF2.三叉鏈表parent
lchilddatarchild結點結構:30
typedefstruct
TriTNode
{
//結點結構
TElemTypedata;
structTriTNode*lchild,*rchild;//左右孩子指針
struct
TriTNode
*parent;//雙親指針
}TriTNode,*TriTree;parentlchilddatarchild結點結構:C語言的類型描述如下:31(請見后面的線索二叉樹)3.線索鏈表326.2二叉樹遍歷一、問題的提出二、遍歷算法描述三、遍歷算法應用舉例四、線索二叉樹33
順著某一條搜索路徑巡訪二叉樹中的結點,使得每個結點均被訪問一次,而且僅被訪問一次。一、問題的提出“訪問”的含義可以很廣,如:輸出結點的數(shù)據(jù)、判斷結構信息等。34
“遍歷”是任何類型均有的操作,對線性結構而言,只有一條搜索路徑(因為每個結點均只有一個后繼),故不需要另加討論。而二叉樹是非線性結構,
每個結點有兩個后繼,則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。35
對“二叉樹”而言,可以有三條搜索路徑:
1.先上后下的按層次遍歷;
2.先左(子樹)后右(子樹)的遍歷;
3.先右(子樹)后左(子樹)的遍歷。36先左后右的遍歷算法先(根)序的遍歷算法中(根)序的遍歷算法后(根)序的遍歷算法37若二叉樹為空樹,則空操作;否則,(1)訪問根結點;(2)先序遍歷左子樹;(3)先序遍歷右子樹。先(根)序的遍歷算法:ABCDFGEH38若二叉樹為空樹,則空操作;否則,(1)中序遍歷左子樹;(2)訪問根結點;(3)中序遍歷右子樹。中(根)序的遍歷算法:ABCDFGEH39若二叉樹為空樹,則空操作;否則,(1)后序遍歷左子樹;(2)后序遍歷右子樹;(3)訪問根結點。后(根)序的遍歷算法:ABCDFGEH40ABCDEFGHA前序遍歷:ABCDEFGHBDCEGHFB中序遍歷:DAGEHCFD后序遍歷:BGHEFCA二叉樹遍歷的輸出順序示例演示41NULLNULLNULLNULLNULLNULLNULLNULLNULLABCDEFGH先序遍歷:中序遍歷:后序遍歷:ABDBDCEGHFDAGEHCFBGHEFCA二叉樹遍歷過程的示例演示42二、遍歷算法描述
先序(前序)遍歷二叉樹的遞歸算法
中序遍歷二叉樹的遞歸算法
后序遍歷二叉樹的遞歸算法43先序遍歷二叉樹的遞歸算法voidpreorder(BiTreeT){
//
先序遍歷二叉樹
if(T==NULL)exit;
{
visit(T->data);//訪問結點
preorder(T->lchild);//遍歷左子樹
preorder(T->rchild);//遍歷右子樹
}}44void
inorder(BiTreeT){
//
中序遍歷二叉樹
if(T==NULL)exit;{
inorder(T->lchild);
//遍歷左子樹
visit(T->data);//訪問結點
inorder(T->rchild);//遍歷右子樹
}}中序遍歷二叉樹的遞歸算法45void
postorder(BiTreeT)
{
//
后序遍歷二叉樹
if(T==NULL)
{
postorder(T->lchild);//遍歷左子樹
postorder(T->rchild);//遍歷右子樹
visit(T->data);//訪問結點
}}后序遍歷二叉樹的遞歸算法46三、遍歷算法應用舉例1、統(tǒng)計二叉樹中葉子結點的個數(shù)
(先序遍歷)2、求二叉樹的深度(后序遍歷)3、復制二叉樹(后序遍歷)4、建立二叉樹的存儲結構471、統(tǒng)計二叉樹中葉子結點的個數(shù)算法基本思想:
先序(或中序或后序)遍歷二叉樹,在遍歷過程中查找葉子結點,并計數(shù)。由此,需在遍歷算法中增添一個“計數(shù)”的參數(shù),并將算法中“訪問結點”的操作改為:若是葉子,則計數(shù)器增1。48voidCountLeaf(BiTreeT,int&count){
if(T){
if
((!T->lchild)&&(!T->rchild))count++;
//對葉子結點計數(shù)
CountLeaf(T->lchild,count);CountLeaf(T->rchild,count);
}
//if}
//CountLeaf492.求二叉樹的深度(后序遍歷)算法基本思想:
從二叉樹深度的定義可知,二叉樹的深度應為其左、右子樹深度的最大值加1。由此,需先分別求得左、右子樹的深度,算法中“訪問結點”的操作為:求得左、右子樹深度的最大值,然后加1。
首先分析二叉樹的深度和它的左、右子樹深度之間的關系。50int
Depth(BiTreeT
){//返回二叉樹的深度
if
(!T)depthval=0;else{
depthLeft=Depth(T->lchild);
depthRight=Depth(T->rchild);
depthval=1+(depthLeft>depthRight?depthLeft:depthRight);
}
return
depthval;}513、復制二叉樹(后序遍歷)核心操作:生成一個根結點,并鏈接左右子樹根元素T根元素NEWT遞歸操作:完成左右子樹的復制52BiTNode*CopyTree(BiTNode*T)
{
if
(!T)returnNULL;
if(T->lchild)
newlptr=CopyTree(T->lchild);//復制左子樹
elsenewlptr=NULL;
if
(T->rchild)
newrptr=CopyTree(T->rchild);//復制右子樹
elsenewrptr=NULL;
newT=GetTreeNode(T->data,newlptr,
newrptr);
return
newT;}
//CopyTree53BiTNode*GetTreeNode(TElemTypeitem,BiTNode*lptr,BiTNode*rptr){
if
(!(T=newBiTNode))
exit(1);T->data=item;T->lchild=lptr;T->rchild=rptr;
returnT;}
生成一個二叉樹的結點的操作算法:(其數(shù)據(jù)域為item,左指針域為lptr,右指針域為rptr)54ABCDEFGHK^D^C^^H^^K^G^F^E^A例如:下列二叉樹的復制過程如下:^BnewTT554、建立二叉樹的存儲結構
不同的定義方法相應有不同的存儲結構的建立算法。以下建立以二叉鏈表表示的存儲結構。從輸入的字符串建立二叉樹由前序和中序的序列建立二叉樹56
以字符串的形式
根
左子樹
右子樹定義一棵二叉樹例如:ABCD以空白字符“”表示A(B(,C(,)),D(,))空樹只含一個根結點的二叉樹A以字符串“A”表示以下列字符串表示57voidCreateBiTree(BiTree&T){cin>>ch;
if(ch=='')T=NULL;
else{
if
(!(T=newBiTNode))exit(OVERFLOW);T->data=ch;//生成根結點
CreateBiTree(T->lchild);//構造左子樹
CreateBiTree(T->rchild);//構造右子樹
}}//CreateBiTree58AB
C
D
ABCD上頁算法執(zhí)行過程舉例如下:ATBCD^^^^^59
僅知二叉樹的先序序列“abcdefg”
不能唯一確定一棵二叉樹,由二叉樹的先序和中序序列建樹
如果同時已知二叉樹的中序序列“cbdaegf”,則會如何?
二叉樹的先序序列二叉樹的中序序列左子樹左子樹右子樹右子樹根根60abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列61preinopsps+n-1isis+n-1pre[ps]kps+1k-isps+1+(k-is)k+1n-(k-is)-1子樹序列下標位置的確定62void
CrtBT(BiTree&T,charpre[],charino[],
intps,intis,intn){
//已知pre[ps..ps+n-1]為二叉樹的先序序列,//ins[is..is+n-1]為二叉樹的中序序列,//本算法由此兩個序列構造二叉鏈表
if
(n==0)T=NULL;
else{k=Search(ino,pre[ps]);//在中序序列中查詢
if(k==-1)T=NULL;
else{}//遞歸程序段
}}//CrtBT……
63T=newBiTNode;T->data=pre[ps];if(k==is)T->Lchild=NULL;else
CrtBT(T->Lchild,
pre[],ino[],
ps+1,is,k-is
);if(k==is+n-1)T->Rchild=NULL;else
CrtBT(T->Rchild,
pre[],ino[],
ps+1+(k-is),k+1,n-(k-is)-1);遞歸語句程序段:64四、線索二叉樹一、何謂線索二叉樹?二、線索鏈表的遍歷算法三、如何建立線索鏈表?65一、何謂線索二叉樹?
遍歷二叉樹的結果是,求得結點的一個線性序列,例如:先序序列:
ABDEGHCFIJ中序序列:
DBGEHACIJF后序序列:
DGHEBJIFCA66
遍歷引起的思考:
遍歷二叉樹把非線性結構以序列的形式加以“線性化”了,那么所得序列信息可否長期利用?信息保持可否盡量少占用額外的存儲空間?是否能否形成一般化的方法?
處理辦法:
在遍歷時,串聯(lián)起前驅(qū)、后繼的關系鏈,以備后期的再利用。67
指向該線性序列中的“前驅(qū)”和“后繼”的指針,稱作“線索”DBG
E
H
A
CIJF
以中序為例,看結點H的前驅(qū)線索和后繼線索ABCFDGEHIJ的前驅(qū)線索H的后繼線索H68
與其相應的二叉樹,稱作“線索二叉樹”
包含“線索”的存儲結構,稱作“線索鏈表”
按“序”來講,可分成:“先序線索二叉樹”、“中序線索二叉樹”和“后序線索二叉樹”69typedefstruct
BiThrNode
{
TElemTypedata;
struct
BiThrNode*lchild,rchild;
struct
BiThrNode*pred,succ;
//前驅(qū)、后繼線索}
BiThrNode,*BiThrTree;線索二叉樹的類型定義:70HABCDEGHFIJT中序線索化二叉樹示例71DBGEHACIJF線索關系表現(xiàn)為雙向循環(huán)鏈表查找前驅(qū)和后繼變得異常容易72
遍歷帶有線索的二叉樹,既無需重新遞歸遍歷,也無需棧的協(xié)助,只進行相當“線性結構”的尋訪即可,而且可正反雙向進行。二、線索鏈表的遍歷算法:73void
InOrder(BiThrTreeH,void(*visit)(BiTree))
{
//H為指向中序線索鏈表中頭結點的指針
p=H->succ;
while(p!=H)
{
visit(p);p=p->succ;
}}74三、如何建立線索鏈表?
建立中序線索化的過程,是在中序遍歷的過程中串聯(lián)起前驅(qū)和后繼的線索指針鏈。(線索化過程參照教科書)756.3樹和森林一、樹和森林的定義二、樹和森林的存儲結構三、樹和森林的遍歷76一、樹和森林的定義
77
樹的定義:樹是n(n≥0)個元素的有限集D,若D為空集,則為空樹。否則:
(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root;
(2)當n>1時,其余結點可分為m(m>0)個互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定義的樹,稱為根root的子樹。78樹的基本操作:
查找類的操作
插入類的操作
刪除類的操作79Root(T)//求樹的根結點查找類的操作:Value(T,cur_e)//求當前結點的元素值
Parent(T,cur_e)//求當前結點的雙親結點LeftChild(T,cur_e)//求當前結點的最左孩子RightSibling(T,cur_e)//求當前結點的右兄弟TreeEmpty(T)//判定樹是否為空樹TreeDepth(T)//求樹的深度TraverseTree(T)//遍歷80InitTree(&T)//初始化置空樹
插入類的操作:CreateTree(&T,definition)
//按定義構造樹Assign(T,cur_e,value)
//給當前結點賦值InsertChild(&T,&p,i,c)
//將以c為根的樹插入為結點p的第i棵子樹81
ClearTree(&T)//將樹清空
刪除類的操作:DestroyTree(&T)//銷毀樹的結構DeleteChild(&T,&p,i)
//刪除結點p的第i棵子樹82ABCDEFGHIJMKLA(B(E,F(K,L)),
C(G),
D(H,I,J(M))
)T1T3T2樹根例如:83(1)有確定的根;(2)樹根和子樹根之間為有向關系。有向樹:有序樹:子樹之間存在確定的次序關系。無序樹:子樹之間不存在確定的次序關系。84任何一棵非空樹是一個二元組
Tree=(root,F(xiàn))其中:root被稱為根結點
F
被稱為子樹森林森林:是m(m≥0)棵互不相交的樹的集合ArootCGDHIJMFBEFKL85二、樹和森林的存儲結構1.雙親表示法2.孩子鏈表表示法3.樹的二叉鏈表(孩子-兄弟)存儲表示法86ABCDEFG0
A
-11
B
02
C
03
D
04
E
25
F
26
G
5r=0n=6dataparent1.雙親表示法:87
typedefstructPTNode{Elemdata;
intparent;//雙親位置域
}PTNode;
dataparent#defineMAX_TREE_SIZE100結點結構:C語言的類型描述:88typedefstruct{PTNodenodes[MAX_TREE_SIZE];
intr,n;//根結點的位置和結點個數(shù)}PTree;樹結構:89r=0n=6data,firstchild0
A
-11
B
02
C
03
D
04
E
25
F
26
G
56451232.孩子鏈表表示法:ABCDEFG90typedefstruct
CTNode{
intchild;
struct
CTNode*next;}*ChildPtr;孩子結點結構:
childnextC語言的類型描述:91
typedefstruct{Elemdata;ChildPtrfirstchild;//孩子鏈的頭指針
}CTBox;雙親結點結構
datafirstchild92typedefstruct{CTBoxnodes[MAX_TREE_SIZE];
int
n,r;//結點數(shù)和根結點的位置}CTree;樹結構:93ABCEDFG
3.樹的二叉鏈表(孩子-兄弟)存儲表示法ABCDEFGrootABCDEFG94typedefstructCSNode{Elemdata;
structCSNode
*firstchild,*nextsibling;}CSNode,*CSTree;C語言的類型描述:結點結構:
firstchilddatanextsibling
樹—二叉樹
將一棵樹轉(zhuǎn)換為二叉樹的方法是:
(1)樹中所有相鄰兄弟之間加一條連線。
(2)對樹中的每個結點,只保留其與第一個孩子結點之間的連線,刪去其與其它孩子結點之間的連線。(刪線)
(3)以樹的根結點為軸心,將整棵樹順時針旋轉(zhuǎn)一定的角度,使之結構層次分明。樹做這樣的轉(zhuǎn)換所構成的二叉樹是唯一的。圖
樹到二叉樹的轉(zhuǎn)換圖
樹與二叉樹的對應2.森林轉(zhuǎn)換為二叉樹森林是若干棵樹的集合。樹可以轉(zhuǎn)換為二叉樹,森林同樣也可以轉(zhuǎn)換為二叉樹。因此,森林也可以方便地用孩子兄弟鏈表表示。森林轉(zhuǎn)換為二叉樹的方法如下:(1)將森林中的每棵樹轉(zhuǎn)換成相應的二叉樹。(2)第一棵二叉樹不動,從第二棵二叉樹開始,依次把后一棵二叉樹的根結點作為前一棵二叉樹根結點的右孩子,當所有二叉樹連在一起后,所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。圖
森林轉(zhuǎn)換為二叉樹的過程100
森林和二叉樹的對應關系設森林
F=(T1,T2,…,Tn);T1=(root,t11,t12,…,t1m);二叉樹
B=(LBT,Node(root),RBT);101由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為:若
F=Φ,則
B=Φ;否則,
由
ROOT(T1)
對應得到
Node(root);
由
(t11,t12,…,t1m)
對應得到
LBT;
由
(T2,T3,…,Tn)
對應得到
RBT。102由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為:若B=Φ,則F=Φ;否則,由Node(root)
對應得到ROOT(T1
);由LBT
對應得到(t11,t12,…,t1m);由RBT
對應得到(T2,T3,…,Tn)。103
由此,樹的各種操作均可對應二叉樹的操作來完成。
應當注意的是,和樹對應的二叉樹,其左、右子樹的概念已改變?yōu)椋?/p>
左是孩子,右是兄弟。104
三、樹和森林的遍歷
1.樹的遍歷2.森林的遍歷3.樹的遍歷的應用1051.樹的遍歷(可有三條搜索路徑):按層次遍歷:先根(次序)遍歷:后根(次序)遍歷:
若樹不空,則先訪問根結點,然后依次先根遍歷各棵子樹。
若樹不空,則先依次后根遍歷各棵子樹,然后訪問根結點。
若樹不空,則自上而下自左至右訪問樹中每個結點。106ABCDEFGHIJK
先根遍歷時頂點的訪問次序:ABEFCDGHIJK
后根遍歷時頂點的訪問次序:EFBCIJKHGDA
層次遍歷時頂點的訪問次序:ABCDEFGHIJK1072.森林中第一棵樹的子樹森林;1.森林中第一棵樹的根結點;
BCDEFGHIJK3.森林中其它樹構成的森林。森林由三部分構成:2.森林的遍歷108
先序遍歷
即:依次從左至右對森林中的每一棵樹進行先根遍歷。
若森林不空,則訪問森林中第一棵樹的根結點;先序遍歷森林中第一棵樹的子樹森林;先序遍歷森林中(除第一棵樹之外)其余樹構成的森林。109中序遍歷
若森林不空,則中序遍歷森林中第一棵樹的子樹森林;訪問森林中第一棵樹的根結點;中序遍歷森林中(除第一棵樹之外)其
余樹構成的森林。
即:依次從左至右對森林中的每一棵樹進行后根遍歷。110
樹的遍歷和二叉樹遍歷的對應關系?先根遍歷后根遍歷樹二叉樹森林先序遍歷先序遍歷中序遍歷中序遍歷111(設樹的存儲結構為孩子兄弟鏈表)typedefstructCSNode{Elemdata;
structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;
求樹的深度
輸出樹中所有從根到葉子的路徑
建樹的存儲結構3.樹的遍歷的應用112intTreeDepth(CSTreeT){
if(!T)return0;
else{h1=TreeDepth(T->firstchild);h2=TreeDepth(T->nextsibling);
}}//TreeDepthreturn(max(h1+1,h2));
求樹的深度的算法:113ABCDABCD求樹深算法的理解(max(h1+1,h2))的圖解
114
輸出樹中所有從根到葉子的路徑的算法:例如:對左圖所示的樹,其輸出結果應為:ABEABFACADGHIADGHJADGHK
ABCDEFGHIJK115void
AllPath(BitreeT,Stack&S)
{
if
(T)
{
Push(S,T->data);if(!T->Lchild&&!T->Rchild)PrintStack(S);else{
AllPath(T->Lchild,S);AllPath(T->Rchild,S);
}
Pop(S);
}//
if(T)}
//AllPath//輸出二叉樹上從根到所有葉子結點的路徑116ABCDEFGHABA-B-D-FDFGA-B-D-GCEHA-C-E-H輸出二叉樹上從根到所有葉子結點的路徑演示117ABCDEFGHIJKABEABFACADGHIADGHJADGHK輸出樹中所有從根到葉子的路徑??????如何判定葉子?118void
OutPath(BitreeT,Stack&S){
while(!T){
Push(S,T->data);
if(!T->firstchild)Printstack(s);
else
OutPath(T->firstchild,s);
Pop(S);
T=T->nextsibling;
}
//while}
//OutPath//輸出森林中所有從根到葉的路徑119
建樹的存儲結構的算法:
和二叉樹類似,不同的定義相應有不同的算法。
假設以二元組(F,C)的形式自上而下、自左而右依次輸入樹的各邊,建立樹的孩子-兄弟鏈表。120ABCDEFG例如:對下列所示樹的輸入序列應為:(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)(‘C’,‘F’)(‘E’,‘G’)ABCD(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)
算法中需要一個隊列保存已建好的結點的指針。121voidCreatTree(CSTree&T){T=NULL;
for(scanf(&fa,&ch);ch!=#;
scanf(&fa,&ch);)
{ p=GetTreeNode(ch);//創(chuàng)建結點
EnQueue(Q,p);//指針入隊列
if(fa==
#)T=p;//所建為根結點
else{ }
//非根結點的情況
}
//for}
//CreateTree
……
122GetHead(Q,s);//取隊列頭元素(指針值)while(s->data!=fa){
//查詢雙親結點
DeQueue(Q,s);GetHead(Q,s);}
if(!(s->firstchild))
{s->firstchild=p;r=p;}
//鏈接第一個孩子結點else
{r->nextsibling=p;r=p;
}
//鏈接其它孩子結點
非根結點的情況的代碼段:123
6.4樹的應用
一、堆排序的實現(xiàn)二、二叉排序樹三、赫夫曼樹及其應用124一、堆排序的實現(xiàn)125堆是滿足下列性質(zhì)的數(shù)列{r1,r2,…,rn}:或堆的定義:{12,36,27,65,40,34,98,81,73,55,49}例如:是小頂堆{12,36,27,65,40,14,98,81,73,55,49}不是堆(小頂堆)(大頂堆)復習第4章排序126rir2ir2i+1
若將該數(shù)列視作完全二叉樹,則r2i
是ri
的左孩子;r2i+1
是
ri
的右孩子。1236276549817355403498例如:是堆14不127如何“建堆”?兩個問題:如何“篩選”?定義堆類型為:typedef
SqListHeapType;//堆采用順序表表示之HeapAdjust(.,.,.);12812998814973556412362740例如:是大頂堆12但在98
和12
進行互換之后,它就不是堆了因此,需要對它進行“篩選”98128173641298比較比較130void
HeapAdjust(RcdType&R[],int
s,int
m){//已知R[s..m]中記錄的關鍵字除R[s]之外均
//滿足堆的特征,本函數(shù)自上而下調(diào)整R[s]的
//關鍵字,使R[s..m]也成為一個大頂堆}//HeapAdjustrc=R[s];//暫存R[s]for
(j=2*s;j<=m;j*=2
){//j初值指向左孩子
自上而下的篩選過程;}R[s]=rc;
//將調(diào)整前的堆頂記錄插入到s位置131if(rc.key>=R[j].key)break;//再作“根”和“子樹根”之間的比較,
//若“>=”成立,則說明已找到rc的插
//入位置s,不需要繼續(xù)往下調(diào)整R[s]=R[j];s=j;
//否則記錄上移,尚需繼續(xù)往下調(diào)整if(j<m
&&R[j].key<R[j+1].key)++j;//左/右“子樹根”之間先進行相互比較
//令j指示關鍵字較大記錄的位置自上而下的篩選過程的代碼段:132
建堆是一個從下往上進行“篩選”的反復過程40554973816436122798例如:排序之前的關鍵字序列為123681734998817355
現(xiàn)在,左/右子樹都已經(jīng)調(diào)整為堆,最后只要調(diào)整根結點,使整個二叉樹是個“堆”即可。98494064361227133voidHeapSort(HeapType&H){
//對順序表H進行堆排序。}
//HeapSortfor
(i=H.length/2;i>0;--i)
//建大頂堆
HeapAdjust(H.r,i,H.length);
for(i=H.length;i>1;--i)
{//調(diào)整堆來實現(xiàn)排序
H.r[1]←→H.r[i];
//將堆頂記錄和當前未經(jīng)排序子序列
//H.r[1..i]中最后一個記錄相互交換
HeapAdjust(H.r,1,i-1);
//對H.r[1]進行篩選
}13412345678910405549731227988164363612738181559849557340984049
堆排序的邏輯結構是一棵完全二叉樹,而實現(xiàn)的空間則是順序表。以數(shù)據(jù)模型演示數(shù)據(jù)在順序空間的動態(tài)變化。初始堆的建立過程:初始堆的建立過程有比較大的消耗,可達4n135堆排序第一趟:1234567891098814973362740556412129881127312641281堆排序第二趟:123456789108173496436274055121298128112731264125573堆排序第三趟:1234567891073644955362740128112988173121264125564可以看出,每趟的調(diào)整只牽涉少量的數(shù)據(jù)……
有序段136堆排序的時間復雜度分析(建堆+
n-1
次調(diào)整):
以后的每次調(diào)整,耗費將顯著減少。因為這樣調(diào)整所耗用的比較操作次數(shù)都不超過堆的樹深,是一種消耗很少的局部調(diào)整。
初始堆的建立過程:O(n)
建成深度為
h=(log2n+1)的堆,需要調(diào)整n-1次,總共進行的關鍵字比較的次數(shù)不超過
2*(log2(n-1)+log2(n-2)+
…+log22)<2n(log2n)
因此,堆排序的時間復雜度為O(nlogn)137二、二叉排序樹
138(1)若它的左子樹不空,則左子樹上所有結點的值均小于根結點的值;1.二叉排序的定義:
二叉排序樹或者是一棵空樹;或者是具有如下特性的二叉樹:(3)它的左、右子樹也都分別是二叉排序樹。(2)若它的右子樹不空,則右子樹上所有結點的值均大于根結點的值;139503080209010854035252388例如:是二叉排序樹。66不140(49,38,65,76,49,13,27,52)4938657649132752構造二叉排序樹
構建二叉排序樹的過程,是一個從空樹起不斷插入結點的過程。每插入一個結點都應保證遵從二叉排序樹的定義。141(,,,,,,,)1327384949526576(49,38,65,76,49,13,27,52)原始序列數(shù)據(jù)4938657649132752構造的二叉排序樹中序遍歷二叉排序樹
如果中序遍歷二叉排序樹,所得序列將是有序的,即實現(xiàn)了對原始數(shù)據(jù)的排序,二叉排序樹即由此得名。142
有關二叉排序樹更詳細的討論及算法,請見第8章查找表的二叉查找樹一節(jié)143三、赫夫曼樹及其應用
(哈夫曼樹)最優(yōu)樹的定義如何構造最優(yōu)樹前綴編碼壓縮的本質(zhì)就是--赫夫曼樹abaabaabadbcaabcabadababa計算機內(nèi)部:ASCII碼,定長編碼;8bit-一個字節(jié),共256個字符;(漢字-雙字節(jié)表示一個漢字,共6萬字符,康熙字典多于這個;)25*8=200bit,144哈夫曼編碼:非定長編碼原則:根據(jù)如字符出現(xiàn)頻率高,則其編碼越短。在軍事情報中,根據(jù)截留的代碼,分析每串字符出現(xiàn)的頻率,分析可能是代表什么文字?慢慢湊成一句話,就能找出每個字的代碼是什么。因為說話的頻率難以更改:比如我,的之類的。145
abaabaabadbcaabcabadababa等長編碼:總共才四個字符,等長編碼:都用兩個bit表示,2*25=50bit用哈夫曼樹可以更省空間跟時間計數(shù):統(tǒng)計每個字符出現(xiàn)的次數(shù)a:13次---0;b:8次---10;c:2次----110,d:2次----111;13*1+8*2+2*3+2*3=45bit在軍事上,就可能取得時間上的勝利。146如何獲得不等長的編碼-建立哈夫曼樹來進行編碼---二叉樹的應用哈夫曼編碼的實質(zhì)就是為了壓縮,那如何譯碼呢?147問題:如何獲得哈夫曼編碼-----如何解出實際內(nèi)容(字符):譯碼哈夫曼法--哈夫曼樹-輸入一串字符,計算每個字符出現(xiàn)頻率--哈夫曼樹(最優(yōu)二叉樹)-哈夫曼編碼-實現(xiàn)壓縮(輸出編碼序列)編碼過程-哈夫曼樹(解壓縮)輸出字符序列:譯碼過程什么是哈夫曼樹----最優(yōu)二叉樹?148149
最優(yōu)樹的定義樹的路徑長度定義為:
樹中每個結點的路徑長度之和。
結點的路徑長度定義為:
從根結點到該結點的路徑上
分支的數(shù)目。150
樹的帶權路徑長度定義為:樹中所有葉子結點的帶權路徑長度之和
WPL(T)=wklk(對所有葉子結點)。
含n個葉子結點、每個葉子結點帶權為w,必存在一棵其帶權路徑長度取最小值的二叉樹,稱為“最優(yōu)二叉樹”或者哈夫曼樹PL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=8954152
根據(jù)給定的n個權值{w1,w2,…,wn},構造n棵二叉樹的集合
F={T1,T2,…,Tn},其中每棵二叉樹中均只含一個帶權值為wi的根結點,其左、右子樹為空樹;如何構造最優(yōu)樹(1)(赫夫曼算法)以二叉樹為例:153
在F中選取其根結點的權值為最小的兩棵二叉樹,分別作為左、右子樹構造一棵新的二叉樹,并置這棵新的二叉樹根結點的權值為其左、右子樹根結點的權值之和;(2)154
從F中刪去這兩棵樹,同時加入剛生成的新樹;
重復(2)
和(3)
兩步,直至F中只含一棵樹為止。(3)(4)1559例如:已知權值W={
5,6,2,9,7
}5627527697671395271566713952795271667132900001111000110110111157
指的是,任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴。前綴編碼
利用赫夫曼樹可以構造一種不等長的二進制編碼,并且構造所得的赫夫曼編碼是一種最優(yōu)前綴編碼,即使所傳電文的總長度最短。158出現(xiàn)頻度:5,6,2,9,7編碼:
101,00,100,11,01字母集:
s,t,a,e,i電文:eat編碼:eat111000025701100101911160167130100012901tiase譯電文:eat
符合前綴編碼規(guī)則才能按唯一性進行譯碼問題:如何獲得哈夫曼編碼-----如何解出實際內(nèi)容(字符):譯碼哈夫曼法--哈夫曼樹-輸入一串字符,計算每個字符出現(xiàn)頻率--哈夫曼樹(最優(yōu)二叉樹)-哈夫曼編碼-實現(xiàn)壓縮(輸出編碼序列)編碼過程-哈夫曼樹(解壓縮)輸出字符序列:譯碼過程什么是哈夫曼樹----最優(yōu)二叉樹?159哈夫曼算法:就是找到最優(yōu)二叉樹,就是構造最優(yōu)二叉樹的過程,WPL總和最小。哈夫曼算法:輸入:n個帶權值的字符---將其看成H[]數(shù)組輸出:最優(yōu)二叉樹就是哈夫曼樹。160算法流程(步驟):1、從H[]中選擇兩個權值最小的字符x,y;2、利用x,y構建一棵二叉樹Z,權值為xw+yw;3、將新產(chǎn)生的二叉樹Z,加入到集合中,同時將x,y刪除;4、不斷重復1、2、3,直到H[]中只剩下一個元素為止。161哈夫曼樹----哈夫曼編碼?規(guī)則:1、沿著哈樹分支,左邊為0,右邊為1;2、每個葉子結點的路徑:從根—該葉子結點所形成的01代碼串---就為該葉子結點對應字符編碼。162壓縮---編碼字符----01串解壓縮—譯碼01串—字符1、從哈樹的根開始,遇0走左分支,遇1走右分支,直至葉子結點----輸出相應字符;2、不斷重復1,直到01串結束。163難點:哈夫曼樹的構造
采用技巧:用數(shù)組表示二叉樹。Typedefstructleafnode{intweight;權值intleft;intright;intparent;}HNODEHNODEH[];
}164Parent,left,right表示該結點父結點,孩子結點的下標Parent,left,right=-1,表示無父結點,無左右孩子準備:建立H[]數(shù)組表示葉子結點,其父結點、左右孩子均為-1;weight,data值求哈夫曼樹函數(shù)Huffman(HNODEH[],intn)(n為葉子結點數(shù))165Huffman(HNODEH[],intn)Count=n;While(count>1){If(H[].parent=-1)Selecttwomin(H,n,&index1,&index2);//找當前數(shù)組中權值最小的兩個數(shù),其下標用Index1,index2表示Index=creatBiTree(H,n,index1,index2)//兩結點建立二叉樹,新生成的結點為indexDelecttwomin(H,n,index1,index2;)Count--;}166Index=creatBiTree(H,n,index1,index2){H[n]為新結點,H[0—n-1]為放原葉子結點值H[n].left=index1;H[n].right=index2;H[n].parent=-1;H[n].weight=H[index1].weight+H[index2].weightH[index1].parent=n;H[index2].parent=n;}技巧:當parent==-1,表示已經(jīng)用過該結點。167作業(yè):編碼:輸入:一串英文txt(都為小寫,不考慮空格)輸出:該txt的01壓縮串(編碼)譯碼:輸入:01串輸出:該01串表示的字符串(解壓縮譯碼)168輸入:一串英文txt(都為小寫,不考慮空格)---1、計數(shù)(求權值weight)2、建立哈樹(數(shù)組H[])3、哈編碼:txt的編碼(01串)4、譯碼169輸入:一串英文txt(都為小寫,不考慮空格)1、計數(shù)—求權值:每個字母出現(xiàn)的頻率.intA[26];//放每個字符出現(xiàn)的次數(shù)chardoc[];//英文txtinti=1;
while(i<n){A[doc[i]-’a’]++;i++;}//后兩條語句可用A[doc[i++]-’a’]++;A[doc[i]-’a’]++;//-’a’得到該字符在A[]中的下標位置,對其++運算,等于累計該字符在txt中出現(xiàn)的次數(shù),也就是它的weight。1702、建立哈樹(H[]):哈夫曼算法計數(shù)后,得到每個字母的權值weight,就可以求得哈夫曼樹---將此樹用H[]數(shù)組表示。(程序見前面)1713、哈編碼:txt的編碼(01串)輸出每個葉子結點(每個字母)的編碼。算法思路:1、從哈樹根開始,沿著哈樹分支,左分支為0,右分支為1;2、每個葉子結點的編碼:從根—>該葉子結點所形成的01代碼串---就為該葉子結點對應字符編碼。172Outputcode(H,n){
for(i=1;i<n;i++){1、Index=found(H,n)//找到每個葉子結點H[i].left=H[i].right=-12、沿著H[index].parent不斷往上尋找,判斷該index是其父親的左孩子還是右孩子,如為左則將0,右則將1壓入棧中。3、,重復2,直到找到根,然后將代碼出棧,就得到該葉子結點代表的字符的編碼。}1734、譯碼輸入一串01串----輸出字符串算法思想:1、從根開始走,看到1就走右分支,看0就走左分支,直到走到葉子結點為止(left=right=-1),輸出該葉子結點對應的字符。2、重復1,直到01串結束174遷移:1、可實現(xiàn)壓縮圖像圖像RGB表示,分別用8位(一個字節(jié))表示,如R用256個字符表示。判斷每個256個字符出現(xiàn)的概率---哈夫曼樹(數(shù)組)---每個字符的編碼---壓縮2、中文txt3、視頻壓縮175176本章學習要點177
1.熟練掌握二叉樹的結構特性,了解相應性質(zhì)的證明方法。
2.熟悉二叉樹的各種存儲結構的特點及適用范圍。
3.遍歷二叉樹是二叉樹各種操作的基礎。實現(xiàn)二叉樹遍歷的具體算法與所采用的存儲結構有關。掌握各種遍歷策略的遞歸算法,靈活運用遍歷算法實現(xiàn)二叉樹的其它操作。層次遍歷是按另一種搜索策略進行的遍歷。178
4.理解二叉樹線索化的實質(zhì)是建立結點與其在相應序列中的前驅(qū)或后繼之間的直接聯(lián)系,熟悉二叉樹的線索化過程以及在中序線索化樹上找給定結點的前驅(qū)和后繼的方法。二叉樹的線索化過程是基于對二叉樹進行遍歷,而線索二叉樹上的線索又為相應的遍歷提供了方便。179
5.熟悉樹的各種存儲結構及其特點,掌握樹和森林與二叉樹的轉(zhuǎn)換方法。建立存儲結構是進行其它操作的前提,因此讀者應掌握1至2種建立二叉樹和樹的存儲結構的方法。
6.學會編寫實現(xiàn)樹的各種操作的算法。
7.
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年哈爾濱2024年客運從業(yè)資格證
- 怎么把視頻改成課件
- 2024年銀川客運服務考試題
- 2024年河北客運資格證都考什么
- 2024年昆明客運資格證考幾科
- 2024年毫州客運資格證仿真試題
- 2024年贛州客運從業(yè)資格證考試題庫
- 2024年山東客運資格證需要考幾科
- 2025屆安徽省定遠縣民族私立中學高三數(shù)學第一學期期末學業(yè)質(zhì)量監(jiān)測試題含解析
- 2025屆河南省濟源四中生物高一第一學期期末學業(yè)水平測試模擬試題含解析
- SMW工法樁施工流程及工藝
- 創(chuàng)意C4D低碳環(huán)保綠色出行PPT模板
- 部編版六年級上冊小學語文期中期末復習課件(按單元復習)PPT
- 消防工程施工組織設計(標準版)58154
- 液壓技術課程設計拉床的液壓動力滑臺的液壓系統(tǒng)設計
- 社會組織公益項目評估指標表
- 滅火器檢查記錄表
- 不良貸款催收管理辦法
- 中醫(yī)門診病歷書寫模板
- 湯有綸-20121027-淺談電子特氣發(fā)展趨勢totzbg20121026
- 基于西門子plc停車場車位控制系統(tǒng)設計
評論
0/150
提交評論