第六章-樹與二叉樹課件

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

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

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

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

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

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

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

B=n1+2n2

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

(1)如果i=1，則結(jié)點i是二叉樹的根，無雙親；如果i>1，則其雙親是

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

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

下面的C語言函數(shù)是實現(xiàn)對給定的二叉樹T的層次遍歷。函數(shù)使用一個順序存儲的隊列q[100],存放還沒有處理的子樹的根結(jié)點的地址。注意,隊首和隊尾指針分別指向隊首結(jié)點和下次進隊結(jié)點的存放位置。

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;}}第六章-樹與二叉樹線索二叉樹定義：前驅(qū)與后繼：在二叉樹的先序、中序或后序遍歷序列中兩個相鄰的結(jié)點互稱為~線索：指向前驅(qū)或后繼結(jié)點的指針稱為~線索二叉樹：加上線索的二叉鏈表表示的二叉樹叫~線索化：對二叉樹按某種遍歷次序使其變?yōu)榫€索二叉樹的過程叫~實現(xiàn)在有n個結(jié)點的二叉鏈表中必定有n+1個空鏈域在線索二叉樹的結(jié)點中增加兩個標志域ltag:若ltag=0,lchild域指向左孩子；若ltar=1,lchild域指向其前驅(qū)rtag:若rtag=0,rchild域指向右孩子；若rtag=1,rchild域指向其后繼第六章-樹與二叉樹ABCDEABDCET先序序列：ABCDE先序線索二叉樹00001111^11typedefstructnode{intdata;intltag,rtag;structnode*lchild,*rchild;}JD;lchildltagdatartagrchild第六章-樹與二叉樹ABCDEABDCET中序序列：BCAED中序線索二叉樹00001111^11^第六章-樹與二叉樹ABCDEABDCET后序序列：CBEDA后序線索二叉樹0000111111^第六章-樹與二叉樹ABCDE0A01B00D11C11E1T中序序列：BCAED帶頭結(jié)點的中序線索二叉樹

0

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

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

0

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

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

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

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

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

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

為第i個葉子結(jié)點的路徑長度。二、構(gòu)造哈夫曼樹1．哈夫曼樹的定義在一棵二叉樹中，若帶權(quán)路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffmantree)。第六章-樹與二叉樹例有4個結(jié)點，權(quán)值分別為7，5，2，4，構(gòu)造有4個葉子結(jié)點的二叉樹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第六章-樹與二叉樹2．哈夫曼樹的構(gòu)造假設有n個權(quán)值，則構(gòu)造出的哈夫曼樹有n個葉子結(jié)點。n個權(quán)值分別設為w1,w2,…,wn,則哈夫曼樹的構(gòu)造規(guī)則為：(1)將w1,w2,…,wn看成是有n棵樹的森林(每棵樹僅有一個結(jié)點)；(2)在森林中選出兩個根結(jié)點的權(quán)值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點權(quán)值為其左、右子樹根結(jié)點權(quán)值之和；(3)從森林中刪除選取的兩棵樹，并將新樹加入森林；(4)重復(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為我們所求得的哈夫曼樹。第六章-樹與二叉樹下面給出哈夫曼樹的構(gòu)造過程，假設給定的葉子結(jié)點的權(quán)分別為1,5,7,3，則構(gòu)造哈夫曼樹過程如圖7-24所示。第六章-樹與二叉樹從圖7-24可知，n個權(quán)值構(gòu)造哈夫曼樹需n-1次合并，每次合并，森林中的樹數(shù)目減1，最后森林中只剩下一棵樹，即為我們求得的哈夫曼樹。構(gòu)造哈夫曼樹的模擬演示第六章-樹與二叉樹3、哈夫曼樹構(gòu)造程序一棵有n個葉子結(jié)點的Huffman樹有2n-1個結(jié)點采用順序存儲結(jié)構(gòu)——一維結(jié)構(gòu)數(shù)組存儲結(jié)點信息結(jié)點類型定義為：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;}

第六章-樹與二叉樹

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;}}第六章-樹與二叉樹哈夫曼樹的算法模擬演示第六章-樹與二叉樹

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