數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)明教程（第3版）課件 第6章樹和二叉樹(下)

第6章樹和二叉樹6.1樹6.2二叉樹6.3遞歸算法設(shè)計(jì)方法6.4二叉樹的基本運(yùn)算算法6.5二叉樹的遍歷6.6二叉樹的構(gòu)造6.7二叉樹與樹之間的轉(zhuǎn)換6.8線索二叉樹6.9哈夫曼樹第6章樹和二叉樹1/506.6二叉樹的構(gòu)造6.6.1什么是二叉樹的構(gòu)造一棵所有結(jié)點(diǎn)值不同的二叉樹，其先序、中序、后序和層次遍歷都是唯一的。二叉樹的構(gòu)造就是給定某些遍歷序列，反過來唯一地確定該二叉樹。6.6二叉樹的構(gòu)造2/50

【例6.15】一棵二叉樹的先序遍歷序列和中序遍歷序列相同，說明該二叉樹的形態(tài)。

二叉樹的先序遍歷序列為NLR，中序遍歷序列為L(zhǎng)NR:NLR=LNR則L應(yīng)為空（因?yàn)镹為空后其L、R沒有意義）。所以這樣的二叉樹為右單支樹（除葉子結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)只有一個(gè)右孩子）。高度為4的滿足題目要求的二叉樹6.6二叉樹的構(gòu)造3/506.6.2二叉樹的構(gòu)造方法二叉樹遍歷序列圖(a)的二叉樹圖(b)的二叉樹圖(c)的二叉樹圖(d)的二叉樹圖(e)的二叉樹先序遍歷序列ABCABCABCABCABC中序遍歷序列BACBCAACBCBAABC后序遍歷序列BCACBACBACBACBAABCABCABCABCABC(a)(b)(c)(d)(e)6.6二叉樹的構(gòu)造4/50從中看到，對(duì)于不同形態(tài)的二叉樹：先序遍歷序列可能相同（圖中5棵二叉樹的先序遍歷序列均相同）。中序遍歷序列可能相同。后序遍歷序列可能相同（圖(b)～(e)的后序遍歷序列均相同）先序遍歷序列和后序遍歷序列可能都相同（圖(d)和(e)的先序遍歷序列和后序遍歷序列均相同）。ABCABCABCABCABC(a)(b)(c)(d)(e)6.6二叉樹的構(gòu)造5/50實(shí)際上，對(duì)于含2個(gè)或者以上結(jié)點(diǎn)的二叉樹，在先序、中序和后序遍歷序列中：由先序遍歷序列和中序遍歷序列能夠唯一確定一棵二叉樹。由后序遍歷序列和中序遍歷序列能夠唯一確定一棵二叉樹。由先序遍歷序列和后序遍歷序列不能唯一確定一棵二叉樹。6.6二叉樹的構(gòu)造6/50任何n（n≥0）個(gè)不同結(jié)點(diǎn)的二又樹，都可由它的中序序列b和先序序列a唯一地確定。1.由先序遍歷序列和中序遍歷序列構(gòu)造一棵二叉樹6.6二叉樹的構(gòu)造7/50左子樹先序序列，有k個(gè)結(jié)點(diǎn)右子樹先序序列，有n-k-1個(gè)結(jié)點(diǎn)先序序列：a0

a1

…

ak

ak+1

…

an-1左子樹中序序列，有k個(gè)結(jié)點(diǎn)右子樹中序序列，有n-k-1個(gè)結(jié)點(diǎn)中序序列：b0

b1

…

bk

bk+1

…

bn-1通過根結(jié)點(diǎn)a0在中序序列中找到bk由a0（根結(jié)點(diǎn)）找到bk。若bk前面有k個(gè)結(jié)點(diǎn)，則左子樹有k個(gè)結(jié)點(diǎn)，右子樹有n-k-1個(gè)結(jié)點(diǎn)。可以求出左右子樹的中序序列和先序序列。這樣根結(jié)點(diǎn)是確定的，左右子樹也是確定的，則該二叉樹是確定的。6.6二叉樹的構(gòu)造8/50

【例6.16】已知先序序列為ABDECFG，中序序列為DBEACGF，給出構(gòu)造該二叉樹的過程。根：D左先序：空

右先序：空右中序：空

右中序：空根：E左先序：空

右先序：空右中序：空

右中序：空根：F左先序：G右先序：空右中序：G右中序：空根：G左先序：空

右先序：空右中序：空

右中序：空根：B左先序：D右先序：E右中序：D右中序：E根：C左先序：空

右先序：FG右中序：空

右中序：GF6.6二叉樹的構(gòu)造構(gòu)造該二叉樹的過程如下所示。根：A左先序：BDE右先序：CFG右中序：DBE右中序：CGF9/50

任何n（n≥0）個(gè)不同結(jié)點(diǎn)的二又樹，都可由它的中序序列和后序序列唯一地確定。2.由中序遍歷序列和后序遍歷序列構(gòu)造一棵二叉樹6.6二叉樹的構(gòu)造10/50左子樹后序序列，有k個(gè)結(jié)點(diǎn)右子樹后序序列，有n-k-1個(gè)結(jié)點(diǎn)后序序列：a0

a1…ak-1

ak…an-2

an-1左子樹中序序列，有k個(gè)結(jié)點(diǎn)右子樹中序序列，有n-k-1個(gè)結(jié)點(diǎn)中序序列：b0

b1

…

bk

bk+1

…

bn-1通過根結(jié)點(diǎn)an-1在中序序列中找到bk由an-1（根結(jié)點(diǎn)）找到bk。若bk前面有k個(gè)結(jié)點(diǎn)，則左子樹有k個(gè)結(jié)點(diǎn)，右子樹有n-k-1個(gè)結(jié)點(diǎn)。可以求出左右子樹的中序序列和后序序列。這樣根結(jié)點(diǎn)是確定的，左右子樹也是確定的，則該二叉樹是確定的。6.6二叉樹的構(gòu)造11/50

【例6.17】已知一棵二叉樹的后序遍歷序列為DEBGFCA，中序遍歷序列為DBEACGF，給出構(gòu)造該二叉樹的過程。根：D左后序：空

右后序：空右中序：空

右中序：空根：E左后序：空

右后序：空右中序：空

右中序：空根：F左后序：G右后序：空右中序：G右中序：空根：G左后序：空

右后序：空右中序：空

右中序：空根：B左后序：D右后序：E右中序：D右中序：E根：C左后序：空

右后序：GF右中序：空

右中序：GF6.6二叉樹的構(gòu)造構(gòu)造該二叉樹的過程如下所示。根：A左后序：DEB右后序：GFC右中序：DBE右中序：CGF12/506.7二叉樹與樹之間的轉(zhuǎn)換6.7.1森林/樹轉(zhuǎn)換成二叉樹樹中所有相鄰兄弟之間加一條連線；對(duì)樹中的每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪除它與其他孩子結(jié)點(diǎn)之間的連線；以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針轉(zhuǎn)動(dòng)45度，使之結(jié)構(gòu)層次分明。6.7二叉樹與樹之間的轉(zhuǎn)換將一棵樹轉(zhuǎn)換成二叉樹的過程如下：13/50【例6.18】將圖6.27(a)所示的樹轉(zhuǎn)換成二叉樹。ABEFCDG一棵樹相鄰兄弟之間加連線(虛線)刪除與雙親結(jié)點(diǎn)的連線轉(zhuǎn)換后的二叉樹ABEFCDGABEFCDGABEFCDG6.7二叉樹與樹之間的轉(zhuǎn)換14/50當(dāng)要轉(zhuǎn)換為二叉樹的森林由兩棵或以上樹構(gòu)成時(shí)，將這樣的森林轉(zhuǎn)換為二叉樹的過程如下：將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。第一棵二叉樹不動(dòng)，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子結(jié)點(diǎn)，當(dāng)所有二叉樹連在一起后，此時(shí)所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。6.7二叉樹與樹之間的轉(zhuǎn)換15/50【例6.19】將下圖所示的森林轉(zhuǎn)換成二叉樹。ABCDEFGHIJKABCDEFGHIJKABCDEFGHIJK6.7二叉樹與樹之間的轉(zhuǎn)換16/506.7.2二叉樹還原為樹/森林當(dāng)一棵二叉樹是由一棵樹轉(zhuǎn)換而來的，則該二叉樹還原為樹的過程如下：若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子、…、都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用連線連起來。刪除原二叉樹中所有雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)之間的連線。整理由①、②兩步所得到的樹，使之結(jié)構(gòu)層次分明。6.7二叉樹與樹之間的轉(zhuǎn)換17/50【例6.21】將下圖的一棵二叉樹還原為森林。ABECFDG一棵二叉樹ABECFDG加連線ABECFDG刪除與右孩子的連線ABECFDG6.7二叉樹與樹之間的轉(zhuǎn)換18/50當(dāng)一棵二叉樹是由m棵樹構(gòu)成的森林轉(zhuǎn)換而來的，該二叉樹的根結(jié)點(diǎn)一定有m-1個(gè)右下孩子，則該二叉樹還原為森林的過程如下：抹掉二叉樹根結(jié)點(diǎn)右鏈上所有結(jié)點(diǎn)之間的“雙親－右孩子”關(guān)系，將其分成若干個(gè)以右鏈上的結(jié)點(diǎn)為根結(jié)點(diǎn)的二叉樹，設(shè)這些二叉樹為bt1、bt2、…、btm。分別將bt1、bt2、…、btm二叉樹各自還原成一棵樹。6.7二叉樹與樹之間的轉(zhuǎn)換19/50【例6.22】將如下圖的二叉樹還原為森林。ABCDEGFHI一棵二叉樹ABCDEFGHI6.7二叉樹與樹之間的轉(zhuǎn)換20/50ABCDEFGHIABCDEFGHI6.7二叉樹與樹之間的轉(zhuǎn)換21/50ABCDEFGHI6.7二叉樹與樹之間的轉(zhuǎn)換ABCDEGFHI一棵二叉樹森林還原22/506.8線索二叉樹6.8.1什么是線索對(duì)于n個(gè)結(jié)點(diǎn)的二叉樹，在二叉鏈存儲(chǔ)結(jié)構(gòu)中有n+1個(gè)空鏈域。利用這些空鏈域存放在某種遍歷次序下該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針，這些指針稱為線索，加上線索的二叉樹稱為線索二叉樹。線索二叉樹分為先序、中序和后序線索二叉樹。6.8線索二叉樹23/50圖中虛線為線索。ABDCEF二叉樹ABDCEF先序序列：ABDCEF先序線索二叉樹6.8線索二叉樹24/506.8.2線索二叉樹的存儲(chǔ)結(jié)構(gòu)在原二叉鏈中增加了ltag和rtag兩個(gè)標(biāo)志域。ltag=0表示lchild指向結(jié)點(diǎn)的左孩子1表示lchild指向結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)即為線索rtag=0表示rchild指向結(jié)點(diǎn)的左孩子1表示rchild指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)即為線索6.8線索二叉樹25/50線索二叉樹的類型定義如下：typedefstructbthnode{ElemTypedata;structbthnode*lchild,*rchild;intltag,rtag;}BthNode;6.8線索二叉樹26/50下面以中序線索二叉樹為例，討論線索二叉樹的建立和相關(guān)算法。為了方便算法實(shí)現(xiàn)，為線索二叉樹增加一個(gè)頭結(jié)點(diǎn)。01頭結(jié)點(diǎn)head0A1根結(jié)點(diǎn)1B00C11D10E10F1中序序列：DBAECF6.8線索二叉樹27/506.8.3建立線索二叉樹及其銷毀建立線索化二叉樹稱之為二叉樹線索化。以中序線索化一棵二叉樹為例，實(shí)質(zhì)上就是中序遍歷一棵二叉樹，在遍歷過程中，檢查當(dāng)前結(jié)點(diǎn)的左、右指針域是否為空；如果為空，將它們改為指向前驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn)的線索。6.8線索二叉樹28/50先創(chuàng)建一個(gè)頭結(jié)點(diǎn)head，在進(jìn)行中序遍歷過程中需保留當(dāng)前結(jié)點(diǎn)p的前驅(qū)結(jié)點(diǎn)的指針，設(shè)為pre（全局變量，初值時(shí)指向頭結(jié)點(diǎn)）。在p不空的情況下：遍歷左子樹（即左子樹線索化）。對(duì)空指針線索化。若p->lchild為空，則置p->ltag=1，且p->lchild=pre；6.8線索二叉樹算法思想prep∧29/50先創(chuàng)建一個(gè)頭結(jié)點(diǎn)head，在進(jìn)行中序遍歷過程中需保留當(dāng)前結(jié)點(diǎn)p的前驅(qū)結(jié)點(diǎn)的指針，設(shè)為pre（全局變量，初值時(shí)指向頭結(jié)點(diǎn)）。在p不空的情況下：遍歷左子樹（即左子樹線索化）。對(duì)空指針線索化。若p->lchild為空，則置p->ltag=1，且p->lchild=pre；若p->rchild為空，則置pre->rtag=l，且pre->rchild=ppre=p；遍歷右子樹（即右子樹線索化）。6.8線索二叉樹算法思想∧prep30/50中序線索二叉樹過程：01頭結(jié)點(diǎn)head0A1根結(jié)點(diǎn)1B00C11D10E10F1中序序列：BDAECF6.8線索二叉樹31/50BthNode*CreaThread(BthNode*bt)//對(duì)以bt為根結(jié)點(diǎn)的二叉樹中序線索化,并增加一個(gè)頭結(jié)點(diǎn)head{BthNode*head;

head=(BthNode*)malloc(sizeof(BthNode));

head->ltag=0;head->rtag=1;//創(chuàng)建頭結(jié)點(diǎn)head

head->rchild=bt;

if(bt==NULL)

//bt為空樹時(shí)

head->lchild=head;

else

{ head->lchild=bt; pre=head; //pre是p的前驅(qū)結(jié)點(diǎn),供加線索用

Thread(bt); //中序遍歷線索化二叉樹

pre->rchild=head; //最后處理,加入指向根結(jié)點(diǎn)的線索

pre->rtag=1; head->rchild=pre; //根結(jié)點(diǎn)右線索化

}

returnhead;}6.8線索二叉樹32/50BthNode*pre; //定義pre為全局變量voidThread(BthNode*&p)//對(duì)以p為根結(jié)點(diǎn)的二叉樹進(jìn)行中序線索化{if(p!=NULL)

{

Thread(p->lchild); //左子樹線索化if(p->lchild==NULL) //前驅(qū)線索

{p->lchild=pre; //給結(jié)點(diǎn)p添加前驅(qū)線索

p->ltag=1;

}

elsep->ltag=0;

if(pre->rchild==NULL)

{pre->rchild=p; //給結(jié)點(diǎn)pre添加后繼線索

pre->rtag=1;

}

elsepre->rtag=0;

pre=p;

Thread(p->rchild); //右子樹線索化

}}6.8線索二叉樹33/50當(dāng)建立好一棵中序線索二叉樹tb后，銷毀tb的過程是先銷毀原來的二叉鏈，最后釋放頭結(jié)點(diǎn)。voidDestroyBTree1(BthNode*&b){if(b->ltag==0) //b有左孩子,釋放左子樹

DestroyBTree1(b->lchild);

if(b->rtag==0) //b有右孩子,釋放右子樹

DestroyBTree1(b->rchild);

free(b);}voidDestroyBTree(BthNode*&tb){DestroyBTree1(tb->lchild); //釋放以tb->lchild為根結(jié)點(diǎn)的樹

free(tb); //釋放頭結(jié)點(diǎn)}6.8線索二叉樹34/506.8.4線索二叉樹的基本運(yùn)算算法（1）查找中序序列的第一個(gè)結(jié)點(diǎn)從中序線索二叉樹的根結(jié)點(diǎn)出發(fā)沿左指針向下到達(dá)最左下結(jié)點(diǎn)，它是中序序列的第一個(gè)結(jié)點(diǎn)。而中序線索二叉樹的根結(jié)點(diǎn)由頭結(jié)點(diǎn)的lchild所指向。BthNode*FirstNode(BthNode*tb)//在中序線索樹中查找中序序列的第1個(gè)結(jié)點(diǎn){BthNode*p=tb->lchild; //p指向根結(jié)點(diǎn)

while(p->ltag==0) //找根結(jié)點(diǎn)的最左下結(jié)點(diǎn)p=p->lchild;

return(p);}6.8線索二叉樹35/50（2）查找中序序列的最后一個(gè)結(jié)點(diǎn)在中序線索二叉樹中，由頭結(jié)點(diǎn)的rchild域指向中序序列的最后一個(gè)結(jié)點(diǎn)。BthNode*LastNode(BthNode*tb) //在中序線索樹中查找中序序列的最后1個(gè)結(jié)點(diǎn){

return(tb->rchild);}6.8線索二叉樹36/50（3）查找p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)若p->ltag=1（線索），則p->lchild指向前驅(qū)結(jié)點(diǎn)；否則，查找p結(jié)點(diǎn)的左孩子的最右下結(jié)點(diǎn)，該結(jié)點(diǎn)作為p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。BthNode*PreNode(BthNode*p)//在中序線索二叉樹上,查找p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn){BthNode*pre;

pre=p->lchild;

if(p->ltag!=1){while(pre->rtag==0)

pre=pre->rchild;}

return(pre);}6.8線索二叉樹37/50（4）查找p結(jié)點(diǎn)的后繼結(jié)點(diǎn)若p->rtag=1，則p->rchild指向后繼結(jié)點(diǎn)；否則，查找p結(jié)點(diǎn)的右孩子的最左下結(jié)點(diǎn)，該結(jié)點(diǎn)作為p結(jié)點(diǎn)的后繼結(jié)點(diǎn)。BthNode*PostNode(BthNode*p)//在中序線索二叉樹上,查找p結(jié)點(diǎn)的后繼結(jié)點(diǎn){BthNode*post;

post=p->rchild;

if(p->rtag!=1){ while(post->ltag==0)

post=post->lchild;

}return(post);}6.8線索二叉樹38/50（5）輸出中序遍歷序列先訪問第一個(gè)結(jié)點(diǎn)，繼續(xù)訪問其后繼結(jié)點(diǎn)，直到遍歷完所有結(jié)點(diǎn)為止。voidThInOrder(BthNode*tb)//中序遍歷線索二叉樹,輸出中序遍歷序列{BthNode*p;

p=FirstNode(tb);

while(p!=tb)

{ printf("%c",p->data); p=PostNode(p);

}

printf("\n");}6.8線索二叉樹39/506.9哈夫曼樹6.9.1哈夫曼樹的定義設(shè)二叉樹具有n個(gè)帶權(quán)值的葉子結(jié)點(diǎn)，從根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)都有一個(gè)路徑長(zhǎng)度。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)結(jié)點(diǎn)權(quán)值的乘積的和稱為該二叉樹的帶權(quán)路徑長(zhǎng)度，記作：其中，wi為第i個(gè)葉子結(jié)點(diǎn)的權(quán)值，li為第i個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。6.9哈夫曼樹40/50以下二叉樹的帶權(quán)路徑長(zhǎng)度值：WPL=1×3+3×3+2×2+4×1=20。42136.9哈夫曼樹41/50給定一組具有確定權(quán)值的葉子結(jié)點(diǎn)，可以構(gòu)造出許多形狀的二叉樹。它們的帶權(quán)路徑長(zhǎng)度可能不相同。把其中具有最小帶權(quán)路徑長(zhǎng)度的二叉樹稱為哈夫曼樹。6.9哈夫曼樹42/50

【例6.19】如下圖的4棵二叉樹具有相同的葉子結(jié)點(diǎn)，計(jì)算出它們的帶權(quán)路徑長(zhǎng)度。

1357(a)1735(b)1375(c)7513(d)6.9哈夫曼樹

它們的帶權(quán)路徑長(zhǎng)度分別為：（a）WPL=1×2+3×2+5×2+7×2=32（b）WPL=1×2+3×3+5×3+7×1=33（c）WPL=7×3+5×3+3×2+1×1=43（d）WPL=1×3+3×3+5×2+7×1=29其中圖(d)所示的二叉樹就是一棵哈夫曼樹。43/506.9.2構(gòu)造哈夫曼樹根據(jù)哈夫曼樹的定義，一棵二叉樹要使其WPL值最小，必須使權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)。而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。6.9哈夫曼樹44/50構(gòu)造一棵哈夫曼樹的過程