第六章-樹(shù)與二叉樹(shù)課件

數(shù)據(jù)結(jié)構(gòu)與算法主講人：杜洪波第六章-樹(shù)與二叉樹(shù)第六章樹(shù)和二叉樹(shù)一、教學(xué)內(nèi)容：1、 樹(shù)和森林的概念（樹(shù)的定義、樹(shù)的術(shù)語(yǔ)、性質(zhì)及運(yùn)算）；2、 二叉樹(shù)的定義、性質(zhì)及運(yùn)算；3、 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)（順序、鏈?zhǔn)奖硎荆?、 遍歷二叉樹(shù)5、 樹(shù)的存儲(chǔ)結(jié)構(gòu)；樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換；遍歷樹(shù)；遍歷森林6、 哈夫曼樹(shù)、哈夫曼編碼。二、教學(xué)要求：1、了解樹(shù)和森林的概念。包括樹(shù)的定義、樹(shù)的術(shù)語(yǔ)和性質(zhì)；2、熟練掌握二叉樹(shù)的結(jié)構(gòu)特性，熟悉二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍；3、熟練掌握二叉樹(shù)的遍歷方法及遍歷算法；4、熟悉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換方法5、掌握建立哈夫曼樹(shù)和哈夫曼編碼的方法及帶權(quán)路徑長(zhǎng)度的計(jì)算。第六章-樹(shù)與二叉樹(shù)第六章樹(shù)和二叉樹(shù)樹(shù)是一類(lèi)重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)6.1樹(shù)的定義定義定義：樹(shù)(tree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集T，其中：有且僅有一個(gè)特定的結(jié)點(diǎn)，稱(chēng)為樹(shù)的根(root)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,……Tm，其中每一個(gè)集合本身又是一棵樹(shù)，稱(chēng)為根的子樹(shù)(subtree)特點(diǎn)：樹(shù)中有且只有一個(gè)根結(jié)點(diǎn)樹(shù)中各子樹(shù)是互不相交的集合第六章-樹(shù)與二叉樹(shù)A只有根結(jié)點(diǎn)的樹(shù)ABCDEFGHIJKLM有子樹(shù)的樹(shù)根子樹(shù)第六章-樹(shù)與二叉樹(shù)基本術(shù)語(yǔ)結(jié)點(diǎn)(node)——表示樹(shù)中的元素，包括數(shù)據(jù)項(xiàng)及若干指向其子樹(shù)的分支結(jié)點(diǎn)的度(degree)——結(jié)點(diǎn)擁有的子樹(shù)數(shù)葉子(leaf)——度為0的結(jié)點(diǎn)孩子(child)——結(jié)點(diǎn)子樹(shù)的根稱(chēng)為該結(jié)點(diǎn)的孩子雙親(parents)——孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的~兄弟(sibling)——同一雙親的孩子樹(shù)的度——一棵樹(shù)中最大的結(jié)點(diǎn)度數(shù)結(jié)點(diǎn)的層次(level)——從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層……深度(depth)——樹(shù)中結(jié)點(diǎn)的最大層次數(shù)森林(forest)——m(m

0)棵互不相交的樹(shù)的集合第六章-樹(shù)與二叉樹(shù)ABCDEFGHIJKLM結(jié)點(diǎn)A的度：3結(jié)點(diǎn)B的度：2結(jié)點(diǎn)M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點(diǎn)A的孩子：B，C，D結(jié)點(diǎn)B的孩子：E，F(xiàn)結(jié)點(diǎn)I的雙親：D結(jié)點(diǎn)L的雙親：E結(jié)點(diǎn)B，C，D為兄弟結(jié)點(diǎn)K，L為兄弟樹(shù)的度：3結(jié)點(diǎn)A的層次：1結(jié)點(diǎn)M的層次：4樹(shù)的深度：4結(jié)點(diǎn)F，G為堂兄弟結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的祖先第六章-樹(shù)與二叉樹(shù)樹(shù)的表示

樹(shù)型表示bacghdefij第六章-樹(shù)與二叉樹(shù)圖形表示法：教師學(xué)生其他人員07級(jí)06級(jí)05級(jí)04級(jí)……沈陽(yáng)工業(yè)大學(xué)電氣學(xué)院理學(xué)院信息學(xué)院……葉子根子樹(shù)第六章-樹(shù)與二叉樹(shù)凹入表表示abdeijfcgh第六章-樹(shù)與二叉樹(shù)嵌套集合表示嵌套括號(hào)表示ijdfghabcea(b(d,e(i,j),c(g,h)))第六章-樹(shù)與二叉樹(shù)6.2二叉樹(shù)定義定義：二叉樹(shù)是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?shù)(n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱(chēng)為左子樹(shù)和右子樹(shù)的互不相交的二叉樹(shù)構(gòu)成特點(diǎn)每個(gè)結(jié)點(diǎn)至多有二棵子樹(shù)(即不存在度大于2的結(jié)點(diǎn))二叉樹(shù)的子樹(shù)有左、右之分，且其次序不能任意顛倒基本形態(tài)A只有根結(jié)點(diǎn)的二叉樹(shù)

空二叉樹(shù)AB右子樹(shù)為空AB左子樹(shù)為空ABC左、右子樹(shù)均非空第六章-樹(shù)與二叉樹(shù)二叉樹(shù)性質(zhì)性質(zhì)1：證明：用歸納法證明之

i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，是對(duì)的假設(shè)對(duì)所有j(1j<i)命題成立，即第j層上至多有個(gè)結(jié)點(diǎn)那么，第i-1層至多有個(gè)結(jié)點(diǎn)又二叉樹(shù)每個(gè)結(jié)點(diǎn)的度至多為2第i層上最大結(jié)點(diǎn)數(shù)是第i-1層的2倍，即故命題得證性質(zhì)2：深度為k的二叉樹(shù)至多有個(gè)結(jié)點(diǎn)(k1)證明：由性質(zhì)1，可得深度為k的二叉樹(shù)最大結(jié)點(diǎn)數(shù)是第六章-樹(shù)與二叉樹(shù)性質(zhì)3：對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1證明：n1為二叉樹(shù)T中度為1的結(jié)點(diǎn)數(shù)因?yàn)椋憾鏄?shù)中所有結(jié)點(diǎn)的度均小于或等于2所以：其結(jié)點(diǎn)總數(shù)n=n0+n1+n2

又二叉樹(shù)中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都只有一個(gè)分支進(jìn)入設(shè)B為分支總數(shù)，則n=B+1

又：分支由度為1和度為2的結(jié)點(diǎn)射出，

B=n1+2n2

于是，n=B+1=n1+2n2+1=n0+n1+n2n0=n2+1第六章-樹(shù)與二叉樹(shù)幾種特殊形式的二叉樹(shù)滿(mǎn)二叉樹(shù)定義：特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)完全二叉樹(shù)定義：深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿(mǎn)二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱(chēng)為~特點(diǎn)葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)對(duì)任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為L(zhǎng)，則其左分支下子孫的最大層次必為L(zhǎng)或L+1第六章-樹(shù)與二叉樹(shù)1231145891213671014151231145891267101234567123456第六章-樹(shù)與二叉樹(shù)性質(zhì)性質(zhì)4：性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層序編號(hào)，則對(duì)任一結(jié)點(diǎn)i(1in)，有：

(1)如果i=1，則結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)雙親；如果i>1，則其雙親是

i/2(2)如果2i>n，則結(jié)點(diǎn)i無(wú)左孩子；如果2in，則其左孩子是2i(3)如果2i+1>n，則結(jié)點(diǎn)i無(wú)右孩子；如果2i+1n，則其右孩子是2i+1第六章-樹(shù)與二叉樹(shù)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)：按滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)層次編號(hào)，依次存放二叉樹(shù)中的數(shù)據(jù)元素特點(diǎn)：結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中浪費(fèi)空間，適于存滿(mǎn)二叉樹(shù)和完全二叉樹(shù)abcdefgabcde0000fg1234567891011第六章-樹(shù)與二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉鏈表typedefstructnode{datatypedata;structnode*lchild,*rchild;}JD;lchilddatarchildABCDEFG在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針域ABCDEFG^^^^^^^^空指針個(gè)數(shù)：2*n0+1*n1+0*n2=2n0+n1=n0+n1+n0=n0+n1+n2+1=n+1第六章-樹(shù)與二叉樹(shù)三叉鏈表typedefstructnode{datatypedata;structnode*lchild,*rchild,*parent;}JD;lchilddataparentrchildABCDEFGABCDEFG^^^^^^^^^第六章-樹(shù)與二叉樹(shù)6.3遍歷二叉樹(shù)和線索二叉樹(shù)二叉樹(shù)的遍歷方法先序遍歷：先訪問(wèn)根結(jié)點(diǎn),然后分別先序遍歷左子樹(shù)、右子樹(shù)中序遍歷：先中序遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后中序遍歷右子樹(shù)后序遍歷：先后序遍歷左、右子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)按層次遍歷：從上到下、從左到右訪問(wèn)各結(jié)點(diǎn)DLRLDR、LRD、DLRRDL、RLD、DRL第六章-樹(shù)與二叉樹(shù)ADBCDLRADLRDLR>B>>D>>CDLR先序遍歷序列：ABDC先序遍歷:第六章-樹(shù)與二叉樹(shù)ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC中序遍歷:第六章-樹(shù)與二叉樹(shù)ADBCLRDLRDLRD>A>>D>>CLRD后序遍歷序列：DBCA后序遍歷:B第六章-樹(shù)與二叉樹(shù)-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：層次遍歷：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef第六章-樹(shù)與二叉樹(shù)算法遞歸算法第六章-樹(shù)與二叉樹(shù)voidpreorder(JD*bt){if(bt!=NULL){printf("%d\t",bt->data);preorder(bt->lchild);preorder(bt->rchild);}}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列：ABDC第六章-樹(shù)與二叉樹(shù)中序遍歷的非遞歸算法ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B訪問(wèn)：C(4)第六章-樹(shù)與二叉樹(shù)pABCDEFGiP->A訪問(wèn)：CB(5)ABCDEFGiP->AP->D訪問(wèn)：CBp(6)ABCDEFGiP->AP->DP->E訪問(wèn)：CBp(7)ABCDEFGiP->AP->D訪問(wèn)：CBEp(8)第六章-樹(shù)與二叉樹(shù)ABCDEFGiP->AP->DP->G訪問(wèn)：CBEP=NULL(9)ABCDEFGiP->A訪問(wèn)：CBEGDp(11)ABCDEFGiP->AP->F訪問(wèn)：CBEGDp(12)ABCDEFGiP->AP->D訪問(wèn)：CBEGp(10)第六章-樹(shù)與二叉樹(shù)ABCDEFGiP->A訪問(wèn)：CBEGDFp=NULL(13)ABCDEFGi訪問(wèn)：CBEGDFAp(14)ABCDEFGi訪問(wèn)：CBEGDFAp=NULL(15)中序遍歷非遞歸算法第六章-樹(shù)與二叉樹(shù)遍歷算法應(yīng)用按先序遍歷序列建立二叉樹(shù)的二叉鏈表，已知先序序列為：

ABCDEGF求二叉樹(shù)深度算法ABCDEFGA^B^C^D^E^F^^G^統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)算法二叉樹(shù)的建立演示第六章-樹(shù)與二叉樹(shù)用隊(duì)列實(shí)現(xiàn)層次遍歷

下面的C語(yǔ)言函數(shù)是實(shí)現(xiàn)對(duì)給定的二叉樹(shù)T的層次遍歷。函數(shù)使用一個(gè)順序存儲(chǔ)的隊(duì)列q[100],存放還沒(méi)有處理的子樹(shù)的根結(jié)點(diǎn)的地址。注意,隊(duì)首和隊(duì)尾指針?lè)謩e指向隊(duì)首結(jié)點(diǎn)和下次進(jìn)隊(duì)結(jié)點(diǎn)的存放位置。

voidlev_traverse(T)NODE*T;{NODE*q[100],p;inthead,tail,i;q[0]=T;head=0;tail=1;while(head<tail){p=q[head++];printf(“%c”,p->data);if(p->lchild!=NULL)q[tail++]=p->lchild;if(p->rchild!=NULL)q[tail++]=p->rchild;}}第六章-樹(shù)與二叉樹(shù)線索二叉樹(shù)定義：前驅(qū)與后繼：在二叉樹(shù)的先序、中序或后序遍歷序列中兩個(gè)相鄰的結(jié)點(diǎn)互稱(chēng)為~線索：指向前驅(qū)或后繼結(jié)點(diǎn)的指針?lè)Q為~線索二叉樹(shù)：加上線索的二叉鏈表表示的二叉樹(shù)叫~線索化：對(duì)二叉樹(shù)按某種遍歷次序使其變?yōu)榫€索二叉樹(shù)的過(guò)程叫~實(shí)現(xiàn)在有n個(gè)結(jié)點(diǎn)的二叉鏈表中必定有n+1個(gè)空鏈域在線索二叉樹(shù)的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域ltag:若ltag=0,lchild域指向左孩子；若ltar=1,lchild域指向其前驅(qū)rtag:若rtag=0,rchild域指向右孩子；若rtag=1,rchild域指向其后繼第六章-樹(shù)與二叉樹(shù)ABCDEABDCET先序序列：ABCDE先序線索二叉樹(shù)00001111^11typedefstructnode{intdata;intltag,rtag;structnode*lchild,*rchild;}JD;lchildltagdatartagrchild第六章-樹(shù)與二叉樹(shù)ABCDEABDCET中序序列：BCAED中序線索二叉樹(shù)00001111^11^第六章-樹(shù)與二叉樹(shù)ABCDEABDCET后序序列：CBEDA后序線索二叉樹(shù)0000111111^第六章-樹(shù)與二叉樹(shù)ABCDE0A01B00D11C11E1T中序序列：BCAED帶頭結(jié)點(diǎn)的中序線索二叉樹(shù)

0

1頭結(jié)點(diǎn)：ltag=0,lchild指向根結(jié)點(diǎn)rtag=1,rchild指向遍歷序列中最后一個(gè)結(jié)點(diǎn)遍歷序列中第一個(gè)結(jié)點(diǎn)的lchild域和最后一個(gè)結(jié)點(diǎn)的rchild域都指向頭結(jié)點(diǎn)ABDCET中序序列：BCAED中序線索二叉樹(shù)00001111^11^第六章-樹(shù)與二叉樹(shù)線索二叉樹(shù)的生成算法（算法6.6,見(jiàn)教材P134）目的：在依某種順序遍歷二叉樹(shù)時(shí)修改空指針，添加前驅(qū)或后繼。注解：為方便添加結(jié)點(diǎn)的前驅(qū)或后繼，需要設(shè)置兩個(gè)指針：

p指針→當(dāng)前結(jié)點(diǎn)之指針；pre指針→前驅(qū)結(jié)點(diǎn)之指針。技巧：當(dāng)結(jié)點(diǎn)p的左/右域?yàn)榭諘r(shí)，只改寫(xiě)它的左域（裝入前驅(qū)pre），而其右域（后繼）留給下一結(jié)點(diǎn)來(lái)填寫(xiě)。或者說(shuō)，當(dāng)前結(jié)點(diǎn)的指針p應(yīng)當(dāng)送到前驅(qū)結(jié)點(diǎn)的空右域中。若p->lchild＝NULL,則{p->Ltag=1;p->lchild＝pre;}//p的前驅(qū)結(jié)點(diǎn)指針pre存入左空域若pre->rchild＝NULL,則{pre->Rtag＝1;pre->rchild=p;}//p存入其前驅(qū)結(jié)點(diǎn)pre的右空域第六章-樹(shù)與二叉樹(shù)算法遍歷中序線索二叉樹(shù)在中序線索二叉樹(shù)中找結(jié)點(diǎn)后繼的方法：（1）若rtag=1,則rchild域直接指向其后繼（2）若rtag=0,則結(jié)點(diǎn)的后繼應(yīng)是其右子樹(shù)的左鏈尾（ltag=1)的結(jié)點(diǎn)在中序線索二叉樹(shù)中找結(jié)點(diǎn)前驅(qū)的方法：（1）若ltag=1,則lchild域直接指向其前驅(qū)（2）若ltag=0,則結(jié)點(diǎn)的前驅(qū)應(yīng)是其左子樹(shù)的右鏈尾（rtag=1)的結(jié)點(diǎn)ABCDE0A01B00D11C11E1T中序序列：BCAED帶頭結(jié)點(diǎn)的中序線索二叉樹(shù)

0

1第六章-樹(shù)與二叉樹(shù)程序注解(非遞歸，且不用棧）：P=T->lchild;//從頭結(jié)點(diǎn)進(jìn)入到根結(jié)點(diǎn)；while(p!=T){while(p->LTag==link)p=p->lchild;//先找到中序遍歷起點(diǎn)

if(!visit(p->data))returnERROR;//若起點(diǎn)值為空則出錯(cuò)告警

while(p->RTag==Thread……){p=p->rchild;Visit(p->data);}//若有后繼標(biāo)志，則直接提取p->rchild中線索并訪問(wèn)后繼結(jié)點(diǎn)；p=p->rchild;//當(dāng)前結(jié)點(diǎn)右域不空或已經(jīng)找好了后繼，則一律從結(jié)點(diǎn)的右子樹(shù)開(kāi)始重復(fù){}的全部過(guò)程。}ReturnOK;線索二叉樹(shù)的中序遍歷算法（算法6.5,參見(jiàn)教材P134）LTag=0RTag=1第六章-樹(shù)與二叉樹(shù)中序線索化演示中序線索化后續(xù)演示中序線索化前序演示第六章-樹(shù)與二叉樹(shù)6.4樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu)雙親表示法實(shí)現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹(shù)的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)含兩個(gè)域：數(shù)據(jù)域：存放結(jié)點(diǎn)本身信息雙親域：指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中位置特點(diǎn)：找雙親容易，找孩子難typedefstructnode{datatypedata;intparent;}JD;JDt[M];第六章-樹(shù)與二叉樹(shù)abcdefhgiacdefghib012235551096012345789dataparent0號(hào)單元不用或存結(jié)點(diǎn)個(gè)數(shù)如何找孩子結(jié)點(diǎn)第六章-樹(shù)與二叉樹(shù)孩子表示法多重鏈表：每個(gè)結(jié)點(diǎn)有多個(gè)指針域，分別指向其子樹(shù)的根結(jié)點(diǎn)同構(gòu)：結(jié)點(diǎn)的指針個(gè)數(shù)相等，為樹(shù)的度D結(jié)點(diǎn)不同構(gòu)：結(jié)點(diǎn)指針個(gè)數(shù)不等，為該結(jié)點(diǎn)的度ddatachild1child2……….childDdatadegreechild1child2……….childd孩子鏈表：每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)用單鏈表存儲(chǔ)，再用含n個(gè)元素的結(jié)構(gòu)數(shù)組指向每個(gè)孩子鏈表第六章-樹(shù)與二叉樹(shù)孩子結(jié)點(diǎn)：typedefstructnode{intchild;//該結(jié)點(diǎn)在表頭數(shù)組中下標(biāo)

structnode*next;//指向下一孩子結(jié)點(diǎn)}JD;表頭結(jié)點(diǎn)：typedefstructtnode{datatypedata;//數(shù)據(jù)域

structnode*fc;//指向第一個(gè)孩子結(jié)點(diǎn)}TD;TDt[M];//t[0]不用第六章-樹(shù)與二叉樹(shù)abcdefhgi6012345789acdefghibdatafc23^45^^978^6^^^^^如何找雙親結(jié)點(diǎn)第六章-樹(shù)與二叉樹(shù)帶雙親的孩子鏈表612345789acdefghibdatafc23459786^^^^^^^^^012235551parentabcdefhgi第六章-樹(shù)與二叉樹(shù)孩子兄弟表示法（二叉樹(shù)表示法）實(shí)現(xiàn)：用二叉鏈表作樹(shù)的存儲(chǔ)結(jié)構(gòu)，鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)特點(diǎn)操作容易破壞了樹(shù)的層次typedefstructnode{datatypedata;structnode*fch,*nsib;}JD;abcdefhgiabcdefghi^^^^^^^^^^第六章-樹(shù)與二叉樹(shù)樹(shù)與二叉樹(shù)轉(zhuǎn)換ACBED樹(shù)ABCDE二叉樹(shù)A^^BC^D^^E^A^^BC^D^^E^A^^BC^D^^E^對(duì)應(yīng)存儲(chǔ)存儲(chǔ)解釋解釋第六章-樹(shù)與二叉樹(shù)將樹(shù)轉(zhuǎn)換成二叉樹(shù)加線：在兄弟之間加一連線抹線：對(duì)每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除其與其余孩子之間的關(guān)系旋轉(zhuǎn)：以樹(shù)的根結(jié)點(diǎn)為軸心，將整樹(shù)順時(shí)針轉(zhuǎn)45°ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI樹(shù)轉(zhuǎn)換成的二叉樹(shù)其右子樹(shù)一定為空第六章-樹(shù)與二叉樹(shù)將二叉樹(shù)轉(zhuǎn)換成樹(shù)加線：若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都與p的雙親用線連起來(lái)抹線：抹掉原二叉樹(shù)中雙親與右孩子之間的連線調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹(shù)結(jié)構(gòu)ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI第六章-樹(shù)與二叉樹(shù)森林轉(zhuǎn)換成二叉樹(shù)將各棵樹(shù)分別轉(zhuǎn)換成二叉樹(shù)將每棵樹(shù)的根結(jié)點(diǎn)用線相連以第一棵樹(shù)根結(jié)點(diǎn)為二叉樹(shù)的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，構(gòu)成二叉樹(shù)型結(jié)構(gòu)ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ第六章-樹(shù)與二叉樹(shù)二叉樹(shù)轉(zhuǎn)換成森林抹線：將二叉樹(shù)中根結(jié)點(diǎn)與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹(shù)還原：將孤立的二叉樹(shù)還原成樹(shù)ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ第六章-樹(shù)與二叉樹(shù)樹(shù)和森林的遍歷樹(shù)的遍歷遍歷——按一定規(guī)律走遍樹(shù)的各個(gè)頂點(diǎn)，且使每一頂點(diǎn)僅被訪問(wèn)一次，即找一個(gè)完整而有規(guī)律的走法，以得到樹(shù)中所有結(jié)點(diǎn)的一個(gè)線性排列常用方法先根（序）遍歷：先訪問(wèn)樹(shù)的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹(shù)后根（序）遍歷：先依次后根遍歷每棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)按層次遍歷：先訪問(wèn)第一層上的結(jié)點(diǎn)，然后依次遍歷第二層，……第n層的結(jié)點(diǎn)第六章-樹(shù)與二叉樹(shù)ABCDEFGHIJKLMNO先序遍歷：后序遍歷：層次遍歷：ABEFIGCDHJKLNOMEIFGBCJKNOLMHDAABCDEFGHIJKLMNO第六章-樹(shù)與二叉樹(shù)討論：若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否一樣？abdec先序遍歷：后序遍歷：中序遍歷：decbaabdecabcdebdcea1.

樹(shù)的先序遍歷二法相同；2.樹(shù)的后序遍歷相當(dāng)于對(duì)應(yīng)二叉樹(shù)的中序遍歷；3.樹(shù)沒(méi)有中序遍歷，因?yàn)樽訕?shù)無(wú)左右之分。結(jié)論：第六章-樹(shù)與二叉樹(shù)先序遍歷若森林為空，返回；訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；先序遍歷第一棵樹(shù)中根結(jié)點(diǎn)的子樹(shù)森林；先序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。中序遍歷若森林為空，返回；中序遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林；訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)；中序遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。森林的遍歷ABCDEFGHJI第六章-樹(shù)與二叉樹(shù)討論：若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否相同？例如：ABCDEFGHJI先序序列：中序序列：ABCDEFGHIJBCDAFEHJIGABCDEFGHJI先序序列：中序序列：ABCDEFGHIJBCDAFEHJIG結(jié)論：森林的先序和中序遍歷在兩種方式下的結(jié)果相同。第六章-樹(shù)與二叉樹(shù)結(jié)論：當(dāng)以二叉鏈表做樹(shù)的存儲(chǔ)結(jié)構(gòu)時(shí)，樹(shù)的先根序列和后根序列可借用二叉樹(shù)的先序遍歷和后序遍歷的算法實(shí)現(xiàn)之；對(duì)于森林也一樣。第六章-樹(shù)與二叉樹(shù)一、基本術(shù)語(yǔ)1．路徑和路徑長(zhǎng)度在一棵樹(shù)中，從一個(gè)結(jié)點(diǎn)往下可以達(dá)到的孩子或子孫結(jié)點(diǎn)之間的通路，稱(chēng)為路徑。通路中分支的數(shù)目稱(chēng)為路徑長(zhǎng)度。若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則從根結(jié)點(diǎn)到第L層結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)-1。2．結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長(zhǎng)度若將樹(shù)中結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值，則這個(gè)數(shù)值稱(chēng)為該結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為：從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積。7.7哈夫曼樹(shù)第六章-樹(shù)與二叉樹(shù)3．樹(shù)的帶權(quán)路徑長(zhǎng)度樹(shù)的帶權(quán)路徑長(zhǎng)度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，記為wpl=，其中n為葉子結(jié)點(diǎn)數(shù)目，wi為第i個(gè)葉子結(jié)點(diǎn)的權(quán)值，li

為第i個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。二、構(gòu)造哈夫曼樹(shù)1．哈夫曼樹(shù)的定義在一棵二叉樹(shù)中，若帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱(chēng)這樣的二叉樹(shù)為最優(yōu)二叉樹(shù)，也稱(chēng)為哈夫曼樹(shù)(Huffmantree)。第六章-樹(shù)與二叉樹(shù)例有4個(gè)結(jié)點(diǎn)，權(quán)值分別為7，5，2，4，構(gòu)造有4個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35第六章-樹(shù)與二叉樹(shù)2．哈夫曼樹(shù)的構(gòu)造假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹(shù)有n個(gè)葉子結(jié)點(diǎn)。n個(gè)權(quán)值分別設(shè)為w1,w2,…,wn,則哈夫曼樹(shù)的構(gòu)造規(guī)則為：(1)將w1,w2,…,wn看成是有n棵樹(shù)的森林(每棵樹(shù)僅有一個(gè)結(jié)點(diǎn))；(2)在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹(shù)合并，作為一棵新樹(shù)的左、右子樹(shù)，且新樹(shù)的根結(jié)點(diǎn)權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和；(3)從森林中刪除選取的兩棵樹(shù)，并將新樹(shù)加入森林；(4)重復(fù)(2)、(3)步，直到森林中只剩一棵樹(shù)為止，該樹(shù)即為我們所求得的哈夫曼樹(shù)。第六章-樹(shù)與二叉樹(shù)下面給出哈夫曼樹(shù)的構(gòu)造過(guò)程，假設(shè)給定的葉子結(jié)點(diǎn)的權(quán)分別為1,5,7,3，則構(gòu)造哈夫曼樹(shù)過(guò)程如圖7-24所示。第六章-樹(shù)與二叉樹(shù)從圖7-24可知，n個(gè)權(quán)值構(gòu)造哈夫曼樹(shù)需n-1次合并，每次合并，森林中的樹(shù)數(shù)目減1，最后森林中只剩下一棵樹(shù)，即為我們求得的哈夫曼樹(shù)。構(gòu)造哈夫曼樹(shù)的模擬演示第六章-樹(shù)與二叉樹(shù)3、哈夫曼樹(shù)構(gòu)造程序一棵有n個(gè)葉子結(jié)點(diǎn)的Huffman樹(shù)有2n-1個(gè)結(jié)點(diǎn)采用順序存儲(chǔ)結(jié)構(gòu)——一維結(jié)構(gòu)數(shù)組存儲(chǔ)結(jié)點(diǎn)信息結(jié)點(diǎn)類(lèi)型定義為：typedefstruct{intweight;intparent,lchild,rchild;}JD;#defineMAX100voidhuffman(intn,intw[],JDt[]){inti,j,k,x1,x2,m1,m2;for(i=1;i<(2*n);i++){t[i].parent=t[i].lchild=t[i].rchild=-1;if(i<=n)t[i].weight=w[i];elset[i].weight=0;}

第六章-樹(shù)與二叉樹(shù)

for(i=1;i<n;i++){m1=m2=MAX;x1=x2=0;for(j=1;j<(n+i);j++){if((t[j].weight<m1)&&(t[j].parent==0)){m2=m1;x2=x1;m1=t[j].weight;x1=j;}elseif((t[j].weight<m2)&&(t[j].parent==0)){m2=t[j].weight;x2=j;}}k=n+i;t[x1].parent=t[x2].parent=k;t[k].weight=m1+m2;t[k].lchild=x1;t[k].rchild=x2;}}第六章-樹(shù)與二叉樹(shù)哈夫曼樹(shù)的算法模擬演示第六章-樹(shù)與二叉樹(shù)

在遠(yuǎn)程通訊中，要將待傳字符轉(zhuǎn)換成由二進(jìn)制組成的字符串：設(shè)要傳送的字符為：ABACCDA若編碼為：A—00B—01