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

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

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

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

a1

…

ak

ak+1

…

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

b1

…

bk

bk+1

…

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

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

右先序：空右中序：空

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

右先序：空右中序：空

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

右先序：空右中序：空

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

右先序：FG右中序：空

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

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

a1…ak-1

ak…an-2

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

b1

…

bk

bk+1

…

bn-1通過(guò)根結(jié)點(diǎn)an-1在中序序列中找到bk由an-1（根結(jié)點(diǎn)）找到bk。若bk前面有k個(gè)結(jié)點(diǎn)，則左子樹(shù)有k個(gè)結(jié)點(diǎn)，右子樹(shù)有n-k-1個(gè)結(jié)點(diǎn)?？梢郧蟪鲎笥易訕?shù)的中序序列和后序序列。這樣根結(jié)點(diǎn)是確定的，左右子樹(shù)也是確定的，則該二叉樹(shù)是確定的。6.6二叉樹(shù)的構(gòu)造11/50

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

右后序：空右中序：空

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

右后序：空右中序：空

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

右后序：空右中序：空

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

右后序：GF右中序：空

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

head->lchild=head;

else

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

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

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

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

}

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

{

Thread(p->lchild); //左子樹(shù)線索化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); //右子樹(shù)線索化

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

DestroyBTree1(b->lchild);

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

DestroyBTree1(b->rchild);

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

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

return(tb->rchild);}6.8線索二叉樹(shù)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)//在中序線索二叉樹(shù)上,查找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線索二叉樹(shù)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)//在中序線索二叉樹(shù)上,查找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線索二叉樹(shù)38/50（5）輸出中序遍歷序列先訪問(wèn)第一個(gè)結(jié)點(diǎn)，繼續(xù)訪問(wèn)其后繼結(jié)點(diǎn)，直到遍歷完所有結(jié)點(diǎn)為止。voidThInOrder(BthNode*tb)//中序遍歷線索二叉樹(shù),輸出中序遍歷序列{BthNode*p;

p=FirstNode(tb);

while(p!=tb)

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

}

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

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

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

它們的帶權(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)所示的二叉樹(shù)就是一棵哈夫曼樹(shù)。43/506.9.2構(gòu)造哈夫曼樹(shù)根據(jù)哈夫曼樹(shù)的定義，一棵二叉樹(shù)要使其WPL值最小，必須使權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)。而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。6.9哈夫曼樹(shù)44/50構(gòu)造一棵哈夫曼樹(shù)的過(guò)程