數(shù)據(jù)結(jié)構(gòu)樹(shù)教程課件

上傳人：4*** IP屬地：貴州上傳時(shí)間：2022-12-23 格式：PPT 頁(yè)數(shù)：154 大?。?.12MB 積分：25 舉報(bào) 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)樹(shù)教程課件_第2頁(yè)

數(shù)據(jù)結(jié)構(gòu)樹(shù)教程課件_第3頁(yè)

數(shù)據(jù)結(jié)構(gòu)樹(shù)教程課件_第4頁(yè)

數(shù)據(jù)結(jié)構(gòu)樹(shù)教程課件_第5頁(yè)

已閱讀5頁(yè)，還剩149頁(yè)未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說(shuō)明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

第五章樹(shù)樹(shù)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)5.1樹(shù)的定義定義定義：樹(shù)(tree)是n(n>0)個(gè)結(jié)點(diǎn)的有限集T，其中：有且僅有一個(gè)特定的結(jié)點(diǎn)，稱為樹(shù)的根(root)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,……Tm，其中每一個(gè)集合本身又是一棵樹(shù)，稱為根的子樹(shù)(subtree)特點(diǎn)：樹(shù)中至少有一個(gè)結(jié)點(diǎn)——根樹(shù)中各子樹(shù)是互不相交的集合第五章樹(shù)樹(shù)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以A只有根結(jié)點(diǎn)的樹(shù)ABCDEFGHIJKLM有子樹(shù)的樹(shù)根子樹(shù)A只有根結(jié)點(diǎn)的樹(shù)ABCDEFGHIJKLM有子樹(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ù)的根稱為該結(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(m0)棵互不相交的樹(shù)的集合基本術(shù)語(yǔ)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的祖先ABCDEFGHIJKLM結(jié)點(diǎn)A的度：3葉子：K，L，F(xiàn)，G5.2二叉樹(shù)定義定義：二叉樹(shù)是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?shù)(n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹(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ù)均非空5.2二叉樹(shù)A只有根結(jié)點(diǎn)空二叉樹(shù)AB右子樹(shù)為空AB左子樹(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ù)性質(zhì)證明：用歸納法證明之性質(zhì)2：深度為k的二叉樹(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性質(zhì)3：對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的幾種特殊形式的二叉樹(shù)滿二叉樹(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的滿二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為~特點(diǎn)葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)對(duì)任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為l，則其左分支下子孫的最大層次必為l或l+1性質(zhì)性質(zhì)4：幾種特殊形式的二叉樹(shù)特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)1231145891213671014151231145891267101234567123456123114589121367101415123114589性質(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性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層序編號(hào)，則5.3樹(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];5.3樹(shù)的存儲(chǔ)結(jié)構(gòu)typedefstructnodeabcdefhgiacdefghib012235551096012345789dataparent0號(hào)單元不用或存結(jié)點(diǎn)個(gè)數(shù)如何找孩子結(jié)點(diǎn)abcdefhgiacdefghib012235551096孩子表示法多重鏈表：每個(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è)孩子鏈表孩子結(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]不用孩子表示法datachild1child2abcdefhgi6012345789acdefghibdatafc23^45^^978^6^^^^^如何找雙親結(jié)點(diǎn)abcdefhgi6012345789acdefghibda帶雙親的孩子鏈表612345789acdefghibdatafc23459786^^^^^^^^^012235551parentabcdefhgi帶雙親的孩子鏈表612345789acdefghibdata孩子兄弟表示法（二叉樹(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ù)表示法）typedefstruct二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)：按滿二叉樹(shù)的結(jié)點(diǎn)層次編號(hào)，依次存放二叉樹(shù)中的數(shù)據(jù)元素特點(diǎn)：結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中浪費(fèi)空間，適于存滿二叉樹(shù)和完全二叉樹(shù)abcdefgabcde0000fg1234567891011二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)abcdefgabc鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉鏈表typedefstructnode{datatypedata;structnode*lchild,*rchild;}JD;lchilddatarchildABCDEFG在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針域ABCDEFG^^^^^^^^鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)typedefstructnodel三叉鏈表typedefstructnode{datatypedata;structnode*lchild,*rchild,*parent;}JD;lchilddataparentrchildABCDEFGABCDEFG^^^^^^^^^三叉鏈表typedefstructnodelchi樹(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ù)轉(zhuǎn)換ACBED樹(shù)ABCDE二叉樹(shù)A將樹(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ù)轉(zhuǎn)換成二叉樹(shù)ABCDEFGHIABCDEFGHIABCD將二叉樹(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ù)轉(zhuǎn)換成樹(shù)ABCDEFGHIABCDEFGHIABCD森林轉(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森林轉(zhuǎn)換成二叉樹(shù)ABCDEFGHIJABCDEFGHIJAB二叉樹(shù)轉(zhuǎn)換成森林抹線：將二叉樹(shù)中根結(jié)點(diǎn)與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹(shù)還原：將孤立的二叉樹(shù)還原成樹(shù)ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ二叉樹(shù)轉(zhuǎn)換成森林ABCDEFGHIJABCDEFGHIJAB5.4樹(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)5.4樹(shù)和二叉樹(shù)的遍歷ABCDEFGHIJKLMNO先序遍歷：后序遍歷：層次遍歷：ABEFIGCDHJKLNOMEIFGBCJKNOLMHDAABCDEFGHIJKLMNOABCDEFGHIJKLMNO先序遍歷：后序遍歷：層次遍歷：二叉樹(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ù)的遍歷DLRLDR、LRD、DLRADBCDLRADLRDLR>B>>D>>CDLR先序遍歷序列：ABDC先序遍歷:ADBCDLRADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC中序遍歷:ADBCLDRADBCLRDLRDLRD>A>>D>>CLRD后序遍歷序列：DBCA后序遍歷:BADBCLR-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：層次遍歷：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：層次遍歷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);先序序列：ABDCvoidpreorder(JD*bt)主程序Pre(T非遞歸算法ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B訪問(wèn)：C(4)非遞歸算法ABCDEFGpiP->A(1)ABCDEFGpipABCDEFGiP->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)pABCDEFGiP->A訪問(wèn)：CB(5)ABCDEFGiABCDEFGiP->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)ABCDEFGiP->AP->DP->G訪問(wèn)：CBEP=ABCDEFGiP->A訪問(wèn)：CBEGDFp=NULL(13)ABCDEFGi訪問(wèn)：CBEGDFAp(14)ABCDEFGi訪問(wèn)：CBEGDFAp=NULL(15)Ch5_4.cCh5_40.C后序遍歷非遞歸算法ABCDEFGiP->A訪問(wèn)：CBEGDFp=NU遍歷算法應(yīng)用按先序遍歷序列建立二叉樹(shù)的二叉鏈表，已知先序序列為：ABCDEGF求二叉樹(shù)深度算法Ch5_5.cch5_6.cABCDEFGA^B^C^D^E^F^^G^Ch5_1.c統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)算法遍歷算法應(yīng)用求二叉樹(shù)深度算法Ch5_5.cABCDEFG5.5二叉樹(shù)的應(yīng)用哈夫曼樹(shù)(Huffman)——帶權(quán)路徑長(zhǎng)度最短的樹(shù)定義路徑：從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)間的~路徑長(zhǎng)度：路徑上的分支數(shù)樹(shù)的路徑長(zhǎng)度：從樹(shù)根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中所有帶權(quán)結(jié)點(diǎn)的路徑長(zhǎng)度之和Huffman樹(shù)——設(shè)有n個(gè)權(quán)值{w1,w2,……wn}，構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)，每個(gè)葉子的權(quán)值為wi,則wpl最小的二叉樹(shù)叫~5.5二叉樹(shù)的應(yīng)用Huffman樹(shù)——設(shè)有n個(gè)權(quán)值{w1,例有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例有4個(gè)結(jié)點(diǎn)，權(quán)值分別為7，5，2，4，構(gòu)造有4個(gè)葉子構(gòu)造Huffman樹(shù)的方法——Huffman算法構(gòu)造Huffman樹(shù)步驟根據(jù)給定的n個(gè)權(quán)值{w1,w2,……wn}，構(gòu)造n棵只有根結(jié)點(diǎn)的二叉樹(shù)，令起權(quán)值為wj在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作左右子樹(shù)，構(gòu)造一棵新的二叉樹(shù)，置新二叉樹(shù)根結(jié)點(diǎn)權(quán)值為其左右子樹(shù)根結(jié)點(diǎn)權(quán)值之和在森林中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入森林中重復(fù)上述兩步，直到只含一棵樹(shù)為止，這棵樹(shù)即哈夫曼樹(shù)構(gòu)造Huffman樹(shù)的方法——Huffman算法例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118例a7b5c2d4a7b5c2d46a7b5c2d4611a例w={5,29,7,8,14,23,3,11}51429782331114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100例w={5,29,7,8,14,23,3,Huffman算法實(shí)現(xiàn)Ch5_8.c一棵有n個(gè)葉子結(jié)點(diǎn)的Huffman樹(shù)有2n-1個(gè)結(jié)點(diǎn)采用順序存儲(chǔ)結(jié)構(gòu)——一維結(jié)構(gòu)數(shù)組結(jié)點(diǎn)類型定義typedefstruct{intdata;intpa,lc,rc;}JD;Huffman算法實(shí)現(xiàn)Ch5_8.c一棵有n個(gè)葉子結(jié)點(diǎn)的Hulcdatarcpa12345670000000752400000000000000000(1)lcdatarcpa12345670000300752460000004000055000kx1=3,x2=4m1=2,m2=4(2)lcdatarcpa123456700003207524611000004500655600kx1=2,x2=5m1=5,m2=6(3)lcdatarcpa1234567000032175246111800004567655670kx1=1,x2=6m1=7,m2=11(4)Ch5_8.clcdatarcpa12Huffman樹(shù)應(yīng)用最佳判定樹(shù)等級(jí)分?jǐn)?shù)段比例ABCDE0~5960~6970~7980~8990~1000.050.150.400.300.10a<60a<90a<80a<70EYNDYNCYNBYNA70a<80a<60CYNBYNDYNEYNA80a<9060a<70EADECa<80a<70a<60a<90EYNDYNCYNBYNAHuffman樹(shù)應(yīng)用等級(jí)分?jǐn)?shù)段比例ABCDE0~5960~6Huffman編碼：數(shù)據(jù)通信用的二進(jìn)制編碼思想：根據(jù)字符出現(xiàn)頻率編碼，使電文總長(zhǎng)最短編碼：根據(jù)字符出現(xiàn)頻率構(gòu)造Huffman樹(shù)，然后將樹(shù)中結(jié)點(diǎn)引向其左孩子的分支標(biāo)“0”，引向其右孩子的分支標(biāo)“1”；每個(gè)字符的編碼即為從根到每個(gè)葉子的路徑上得到的0、1序列例要傳輸?shù)淖址疍={C,A,S,T,;}

字符出現(xiàn)頻率w={2,4,2,3,3}CS3364224814T;A00110110T:00;:01A:10C:110S:111Huffman編碼：數(shù)據(jù)通信用的二進(jìn)制編碼例要傳輸?shù)淖址g碼：從Huffman樹(shù)根開(kāi)始，從待譯碼電文中逐位取碼。若編碼是“0”，則向左走；若編碼是“1”，則向右走，一旦到達(dá)葉子結(jié)點(diǎn)，則譯出一個(gè)字符；再重新從根出發(fā)，直到電文結(jié)束例電文是{CAS;CAT;SAT;AT}其編碼“11010111011101000011111000011000”電文為“1101000”譯文只能是“CAT”CS3364224814T;A00110110T:00;:01A:10C:110S:111譯碼：從Huffman樹(shù)根開(kāi)始，從待譯碼電文中逐位取碼。若編線索二叉樹(shù)定義：前驅(qū)與后繼：在二叉樹(shù)的先序、中序或后序遍歷序列中兩個(gè)相鄰的結(jié)點(diǎn)互稱為~線索：指向前驅(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)志域lt:若lt=0,lc域指向左孩子；若lt=1,lc域指向其前驅(qū)rt:若rt=0,rc域指向右孩子；若rt=1,rc域指向其后繼結(jié)點(diǎn)定義：typedefstructnode{intdata;intlt,rt;structnode*lc,*rc;}JD;lcltdatartrc線索二叉樹(shù)typedefstructnodelcABCDEABDCET先序序列：ABCDE先序線索二叉樹(shù)00001111^11ABCDEABABCDEABDCET中序序列：BCAED中序線索二叉樹(shù)00001111^11^ABCDEABABCDEABDCET后序序列：CBEDA后序線索二叉樹(shù)0000111111^ABCDEABABCDE0A01B00D11C11E1T中序序列：BCAED帶頭結(jié)點(diǎn)的中序線索二叉樹(shù)

1頭結(jié)點(diǎn)：lt=0,lc指向根結(jié)點(diǎn)rt=1,rc指向遍歷序列中最后一個(gè)結(jié)點(diǎn)遍歷序列中第一個(gè)結(jié)點(diǎn)的lc域和最后一個(gè)結(jié)點(diǎn)的rc域都指向頭結(jié)點(diǎn)ABDCET中序序列：BCAED中序線索二叉樹(shù)00001111^11^ABCDE0A01B0算法按中序線索化二叉樹(shù)Ch5_20.cABCDEt

1prpiP->AJD*zxxsh(JD*bt){JD*p,*pr,*s[M],*t;inti=0;