第章樹(shù)教學(xué)內(nèi)容

第5章樹(shù)大連東軟信息學(xué)院計(jì)算機(jī)系課前導(dǎo)學(xué)[內(nèi)容提要]樹(shù)和森林二叉樹(shù)的定義、性質(zhì)二叉樹(shù)的遍歷；樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換；線索二叉樹(shù)二叉樹(shù)的應(yīng)用2考綱要求第1節(jié)樹(shù)和森林了解：樹(shù)和森林的基本概念和術(shù)語(yǔ)。掌握：樹(shù)和森林的存儲(chǔ)結(jié)構(gòu)定義。重點(diǎn)掌握：樹(shù)與森林的遍歷第2節(jié)二叉樹(shù)了解：二叉樹(shù)的定義。掌握：二叉樹(shù)的基本性質(zhì)及存儲(chǔ)結(jié)構(gòu)定義。重點(diǎn)掌握：二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)。第3節(jié)二叉樹(shù)的遍歷了解：二叉樹(shù)的遍歷的機(jī)制。掌握：二叉樹(shù)的遍歷的四種算法、遞歸算法的非遞歸轉(zhuǎn)化。重點(diǎn)掌握：二叉樹(shù)的遍歷的遞歸算法。3第4節(jié)樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換了解：樹(shù)、森林與二叉樹(shù)的關(guān)系。掌握：樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換方法。第5節(jié)線索二叉樹(shù)了解：線索二叉樹(shù)的概念。掌握：線索二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)定義。重點(diǎn)掌握：線索二叉樹(shù)的創(chuàng)建和遍歷算法。第6節(jié)二叉樹(shù)的應(yīng)用了解：二叉樹(shù)的應(yīng)用范圍。掌握：二叉樹(shù)的幾種應(yīng)用算法，如表達(dá)式求值、堆排序樹(shù)、哈夫曼樹(shù)。重點(diǎn)掌握：二叉樹(shù)的遍歷應(yīng)用。46A只有根結(jié)點(diǎn)的樹(shù)ABCDEFKHIJ有子樹(shù)的樹(shù)根子樹(shù)樹(shù)的表示法G樹(shù)的基本術(shù)語(yǔ)結(jié)點(diǎn)（node）：表示樹(shù)中的元素，包括數(shù)據(jù)項(xiàng)及若干指向其子樹(shù)的分支。結(jié)點(diǎn)的度（degree）：是指結(jié)點(diǎn)擁有的子樹(shù)個(gè)數(shù)。樹(shù)的度：一棵樹(shù)中最大的結(jié)點(diǎn)度數(shù)。分支結(jié)點(diǎn)（branch）：度大于0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)或者非終端結(jié)點(diǎn)。葉子結(jié)點(diǎn)（leaf）：度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)或者終端結(jié)點(diǎn)。7樹(shù)的基本術(shù)語(yǔ)孩子結(jié)點(diǎn)（child）：結(jié)點(diǎn)子樹(shù)的根稱為該結(jié)點(diǎn)的孩子。雙親結(jié)點(diǎn)（parents）：孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的雙親結(jié)點(diǎn)。兄弟結(jié)點(diǎn)（sibling）：同一雙親的孩子互稱為兄弟結(jié)點(diǎn)。堂兄弟結(jié)點(diǎn)（cousin）：雙親在同一層上的結(jié)點(diǎn)互稱為堂兄弟結(jié)點(diǎn)。祖先結(jié)點(diǎn)（ancestor）：從根到該結(jié)點(diǎn)的所經(jīng)路徑上的所有結(jié)點(diǎn)均稱為祖先結(jié)點(diǎn)。子孫結(jié)點(diǎn)：以某結(jié)點(diǎn)為根的子樹(shù)中任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)。8樹(shù)的基本術(shù)語(yǔ)結(jié)點(diǎn)的層次（level）：樹(shù)具有層次結(jié)構(gòu)。從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層，……，依此類推。樹(shù)的深度（depth）：樹(shù)中結(jié)點(diǎn)的最大層次數(shù)稱為樹(shù)的深度或高度。有序樹(shù)和無(wú)序樹(shù)：如果樹(shù)中各結(jié)點(diǎn)的子樹(shù)是按照從左到右或者從右到左確定的，也就是說(shuō)是有次序的，那么該樹(shù)稱為有序樹(shù)，否則稱為無(wú)序樹(shù)。例如，家族樹(shù)就是一棵有序樹(shù)。森林（forest）：m(m≥0)棵互不相交的樹(shù)的集合。由0棵樹(shù)組成的森林成為空森林。910結(jié)點(diǎn)A的度：結(jié)點(diǎn)B的度：結(jié)點(diǎn)K的度：葉子：結(jié)點(diǎn)A的孩子：結(jié)點(diǎn)B的孩子：結(jié)點(diǎn)I的雙親：結(jié)點(diǎn)K的雙親：結(jié)點(diǎn)B，C，D為兄弟結(jié)點(diǎn)I，J為兄弟樹(shù)的度：結(jié)點(diǎn)A的層次：結(jié)點(diǎn)K的層次：樹(shù)的深度：結(jié)點(diǎn)F，G為堂兄弟結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的祖先320B，C，DE，F(xiàn)3F，H，I，J，KEG144樹(shù)的存儲(chǔ)結(jié)構(gòu)雙親表示法孩子表示法多重鏈表表示法孩子鏈表表示法孩子兄弟表示法11樹(shù)的存儲(chǔ)結(jié)構(gòu)結(jié)點(diǎn)的一般形式為:12DataPointers樹(shù)的標(biāo)準(zhǔn)存儲(chǔ)結(jié)構(gòu)結(jié)點(diǎn)的數(shù)據(jù)類型定義如下：structnode{chardata;structnode*child[m];}typedefstructnodeNODE;NODE*root1;13結(jié)點(diǎn)的一般形式為:Datachild0，child1，…樹(shù)的逆形式存儲(chǔ)結(jié)構(gòu)結(jié)點(diǎn)的數(shù)據(jù)類型定義如下：structr_node{chardata;structr_node*parent;}typedefstructr_nodeR_NODE;R_NODE*root1;14結(jié)點(diǎn)的一般形式為:DataParent樹(shù)的擴(kuò)充標(biāo)準(zhǔn)形式存儲(chǔ)結(jié)構(gòu)結(jié)點(diǎn)的數(shù)據(jù)類型定義如下：structe_node{chardata;structe_node*child[m];structe_node*parent;}typedefstructe_nodeNODE;NODE*root2;15結(jié)點(diǎn)的一般形式為:Datachild0，child1，…Parent16171819樹(shù)和森林的遍歷通常有3種遍歷樹(shù)的方法:前序(先根)遍歷：:首先訪問(wèn)根結(jié)點(diǎn)。然后，若根結(jié)點(diǎn)有子樹(shù)，則按從左至右的次序前序遍歷根結(jié)點(diǎn)的各棵子樹(shù);若根結(jié)點(diǎn)沒(méi)有子樹(shù)，則遍歷結(jié)束。后序(后根)遍歷：若根結(jié)點(diǎn)有子樹(shù)，則先按從左至右的次序后序遍歷根結(jié)點(diǎn)的各棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn);若根結(jié)點(diǎn)沒(méi)有子樹(shù)，則直接訪問(wèn)根結(jié)點(diǎn)。層次遍歷：首先訪問(wèn)處于第一層上的根結(jié)點(diǎn)，然后按從左至右的次序訪問(wèn)處于第二層上的各個(gè)結(jié)點(diǎn)，依此類推……20樹(shù)的遍歷算法遞歸實(shí)現(xiàn)voidTreePreOrder(NODE*t，intm)//前序遍歷{inti;if(t!=NULL){printf("%c",t->data);for(i=0;i<m;i++)TreePreOrder(t->child[i],m);}}后續(xù)遍歷類似，見(jiàn)書P97.21遍歷森林森林也有前序和后序兩種遍歷方法。森林的前序遍歷：若森林為空，則遍歷結(jié)束;否則，訪問(wèn)森林的第1棵樹(shù)的根結(jié)點(diǎn)，然后前序遍歷第1棵樹(shù)的根結(jié)點(diǎn)的各子樹(shù)所構(gòu)成的森林，接著遍歷除森林的第1棵樹(shù)以外的其他各樹(shù)所構(gòu)成的森林。森林的后序遍歷：若森林為空，則遍歷結(jié)束;否則，后序遍歷森林的第1棵樹(shù)的根結(jié)點(diǎn)的各子樹(shù)所構(gòu)成的森林，然后訪問(wèn)森林中第1棵樹(shù)的根結(jié)點(diǎn)，最后后序遍歷除森林的第1棵樹(shù)以外的其他各樹(shù)所構(gòu)成的森林。225.2二叉樹(shù)二叉樹(shù)的定義：

二叉樹(shù)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?shù)(n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹(shù)和右子樹(shù)的互不相交的二叉樹(shù)構(gòu)成。

二叉樹(shù)的特點(diǎn)：

1）每個(gè)結(jié)點(diǎn)至多有二棵子樹(shù)(即不存在度大于2的結(jié)點(diǎn)) 2）二叉樹(shù)的子樹(shù)有左、右之分，且其次序不能任意顛倒23二叉樹(shù)的五種基本形態(tài)24（a） （b） （c） （d） （e）（a）空二叉樹(shù)（b）只有根結(jié)點(diǎn)的二叉樹(shù)（c）只有左子樹(shù)的二叉樹(shù)（d）只有右子樹(shù)的二叉樹(shù)（e）有左、右子樹(shù)的二叉樹(shù)滿二叉樹(shù)定義：

在一棵二叉樹(shù)中，如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子結(jié)點(diǎn)都在同一層上，這樣的一棵二叉樹(shù)稱作滿二叉樹(shù)。 25擬滿樹(shù)（完全二叉樹(shù)）定義：一棵深度為k的有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，對(duì)樹(shù)中的結(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號(hào)，如果編號(hào)為i（1≤i≤n）的結(jié)點(diǎn)與滿二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)在二叉樹(shù)中的位置相同，則這棵二叉樹(shù)稱為完全二叉樹(shù)。26豐滿樹(shù)假設(shè)T是一棵高度為h的二叉樹(shù)，若將T的第h層的結(jié)點(diǎn)全部去掉，得到二叉樹(shù)T'，若T'是滿二叉樹(shù)，則稱二叉樹(shù)T為豐滿樹(shù)。滿樹(shù)一定是擬滿樹(shù)，擬滿樹(shù)一定是豐滿樹(shù)。反之無(wú)效。27281231145891213671014151231145891267101234567123456二叉樹(shù)的性質(zhì)性質(zhì)1

在二叉樹(shù)第i層上至多有２i-1

個(gè)結(jié)點(diǎn)（i≥1）。

證明：用歸納法證明之。當(dāng)i=1時(shí)，二叉樹(shù)的第1層只有一個(gè)根結(jié)點(diǎn)。2i-1=21-1=20=1成立。假設(shè)該命題對(duì)所有j（1<j<i）成立，即第j層上至多有2j-1個(gè)結(jié)點(diǎn)，那么第i-1層至多有2i-2個(gè)結(jié)點(diǎn)。因?yàn)槎鏄?shù)每個(gè)結(jié)點(diǎn)的度不超過(guò)2，因此，第i層的結(jié)點(diǎn)個(gè)數(shù)最多是第i-1層結(jié)點(diǎn)個(gè)數(shù)的2倍，即最多不超過(guò)2*2i-2=2i-1。命題得證。29二叉樹(shù)的性質(zhì)：性質(zhì)2深度為k（k≥1）的二叉樹(shù)至多有２k－1個(gè)結(jié)點(diǎn)。證明：由性質(zhì)1可知，深度為k（k≥1）的二叉樹(shù)的最大結(jié)點(diǎn)個(gè)數(shù)為每層的最大結(jié)點(diǎn)個(gè)數(shù)之和，即命題得證。

30二叉樹(shù)的性質(zhì)：性質(zhì)3

對(duì)任何一顆二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2,則n0=n2+1。證明：假設(shè)n1為二叉樹(shù)T中度為1的結(jié)點(diǎn)數(shù)，因?yàn)槎鏄?shù)中所有結(jié)點(diǎn)的度均小于或等于2，所以，二叉樹(shù)的結(jié)點(diǎn)總數(shù)

n=n0+n1+n2 （公式4.1）又知二叉樹(shù)中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都只有一個(gè)分支進(jìn)入。設(shè)B為分支總數(shù)，則二叉樹(shù)的結(jié)點(diǎn)總數(shù)

n=B+1 （公式4.2）又知所有分支均由度為1和度為2的結(jié)點(diǎn)射出，因此分支總數(shù)

B=n1+2n2 （公式4.3）由公式4.2和公式4.3可以得到

n=n1+2n2+1 （公式4.4）由公式4.1和公式4.4可以得到n0=n2+131二叉樹(shù)的性質(zhì)：性質(zhì)4

具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為

log2n

+1。證明：由完全二叉樹(shù)的定義可知，假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為k（k≥1），則從第1層都第k-1層都是滿的，第k層結(jié)點(diǎn)個(gè)數(shù)為1＜n≤2k-1，則根據(jù)性質(zhì)2和完全二叉樹(shù)的定義，有2k-1-1＜n≤2k-1，則有

2k-1＜n+1≤2k或2k-1≤n＜2k得到

k-1≤log2n＜k或

log2n＜k≤log2n+1因?yàn)閗為整數(shù)，所以k=

log2n+1。32二叉樹(shù)的性質(zhì)：

性質(zhì)5如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層序編號(hào)，則對(duì)任一結(jié)點(diǎn)i（1≤i≤n），有：(1)如果i=1，則結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)雙親；如果i>1，則其雙親是

i/2

；(2)如果2i>n，則結(jié)點(diǎn)i無(wú)左孩子；如果2i≤n，則其左孩子是2i；(3)如果2i+1>n，則結(jié)點(diǎn)i無(wú)右孩子；如果2i+1≤n，則其右孩子是2i+1。33證明：當(dāng)i＝1時(shí)，由完全二叉樹(shù)的定義知其左孩子是結(jié)點(diǎn)2。若2>n，即不存在結(jié)點(diǎn)2，此時(shí)結(jié)點(diǎn)i無(wú)左孩子。結(jié)點(diǎn)i的右孩子也只能是結(jié)點(diǎn)3，若結(jié)點(diǎn)3不存在，即3>n，此時(shí)結(jié)點(diǎn)i無(wú)右孩子。結(jié)論成立。當(dāng)i=k（1<k<

log2n

）時(shí)，第k層的第一個(gè)結(jié)點(diǎn)的編號(hào)為i（由二叉樹(shù)的定義和性質(zhì)2可知i＝2k-1），則其左孩子必為第i+1層的第一個(gè)結(jié)點(diǎn)，其編號(hào)為2k＝2*2k-1＝2i，若2i>n，則編號(hào)為2i的結(jié)點(diǎn)不存在，即結(jié)點(diǎn)i無(wú)左孩子；其右孩子必為第i+1層的第二個(gè)結(jié)點(diǎn)，其編號(hào)為2k+1＝2i+1。若2i+1>n，則編號(hào)為2i+1的結(jié)點(diǎn)不存在，即結(jié)點(diǎn)i無(wú)右孩子。又若2i+1<n，則其左孩子為2i，右孩子為2i+1。結(jié)論成立。34二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)二叉鏈表三叉鏈表35二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)首先要該樹(shù)中每個(gè)結(jié)點(diǎn)進(jìn)行編號(hào)，然后以各結(jié)點(diǎn)的編號(hào)為下標(biāo)，把各結(jié)點(diǎn)的值對(duì)應(yīng)存儲(chǔ)到一維數(shù)組中。完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)：

36二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)(續(xù))非完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)：37二叉鏈表一般的二叉樹(shù)使用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)在數(shù)組中浪費(fèi)的空間比較多?？梢允褂面湵韥?lái)存儲(chǔ)二叉樹(shù)，并使用兩個(gè)指針?lè)謩e指向二叉樹(shù)的左子樹(shù)和右子樹(shù)，這樣就形成了二叉鏈表。在二叉鏈表中，每個(gè)結(jié)點(diǎn)包含三個(gè)域：數(shù)據(jù)域、左指針域和右指針域。38二叉鏈表二叉鏈表的類型定義：typedefstructBTNode{TElemTypedata;structBTNode*lchild,*rchild;}BTNode;BTNode*bt;39二叉鏈表非完全二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)40三叉鏈表有時(shí)需要查找某個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)，這時(shí)使用二叉鏈表很不方便。因此，人們想到了在結(jié)點(diǎn)中再設(shè)一個(gè)指針域，用來(lái)指向結(jié)點(diǎn)的雙親結(jié)點(diǎn)，這就是三叉鏈表。三叉鏈表中每個(gè)結(jié)點(diǎn)包括四個(gè)域：數(shù)據(jù)域、左指針域、右指針域和雙親指針域。41三叉鏈表三叉鏈表的定義：typedefstructBTNode{TElemTypedata;structBTNode*lchild,*rchild,*parent;}BTNode;BTNode*bt;42三叉鏈表非完全二叉樹(shù)的三叉鏈表存儲(chǔ)結(jié)構(gòu)43二叉樹(shù)的遍歷1)二叉樹(shù)的前序遍歷:若二叉樹(shù)為空，則遍歷結(jié)束;否則，①先訪問(wèn)根結(jié)點(diǎn)，②再前序遍歷根結(jié)點(diǎn)的左子樹(shù)，③最后前序遍歷根結(jié)點(diǎn)的右子樹(shù)。2)二叉樹(shù)的中序遍歷:若二叉樹(shù)為空，則遍歷結(jié)束;否則，①先中序遍歷根結(jié)點(diǎn)的左子樹(shù)，②再訪問(wèn)根結(jié)點(diǎn)，③最后中序遍歷根結(jié)點(diǎn)的右子樹(shù)。3)二叉樹(shù)的后序遍歷:若二叉樹(shù)為空，則遍歷結(jié)束;否則，①先后序遍歷根結(jié)點(diǎn)的左子樹(shù)，②再后序遍歷根結(jié)點(diǎn)的右子樹(shù)，③最后訪問(wèn)根結(jié)點(diǎn)。4)二叉樹(shù)層次遍歷:若二叉樹(shù)為空，則遍歷結(jié)束:否則，首先訪問(wèn)處于第1層上的根結(jié)點(diǎn)，然后按從左至右的次序訪問(wèn)處于第二層上的各個(gè)結(jié)點(diǎn)，......，依此類推，按從左至右的次序依次訪問(wèn)處于以后各層上的結(jié)點(diǎn)。5.4樹(shù)、森林向二叉樹(shù)的轉(zhuǎn)換樹(shù)向二叉樹(shù)的轉(zhuǎn)換森林向二叉樹(shù)的轉(zhuǎn)換45樹(shù)向二叉樹(shù)的轉(zhuǎn)換方法：樹(shù)中結(jié)點(diǎn)的孩子放在二叉樹(shù)的左子樹(shù)中，樹(shù)中結(jié)點(diǎn)的兄弟放在二叉樹(shù)的右子樹(shù)中，簡(jiǎn)而言之就是，左孩子右兄弟。轉(zhuǎn)換步驟：（1）在兄弟節(jié)點(diǎn)之間連一條線；（2）每個(gè)結(jié)點(diǎn)僅保留其與最左孩子之間的連線，其余連線刪除；（3）以根為軸心將整棵樹(shù)順時(shí)針旋轉(zhuǎn)45度。46樹(shù)向二叉樹(shù)的轉(zhuǎn)換47思考：如何將一棵二叉樹(shù)轉(zhuǎn)換成樹(shù)？森林向二叉樹(shù)的轉(zhuǎn)換方法：先把森林中的每一棵樹(shù)轉(zhuǎn)換成二叉樹(shù)，然后從最后一棵樹(shù)開(kāi)始，把后一棵樹(shù)作為前一棵樹(shù)的右孩子。485.4.2二叉樹(shù)還原為樹(shù)、森林假設(shè)T是一棵二叉樹(shù)，把T還原為森林F(T)=(T0，T1,…,Tm-1)的方法如下:1)如果T為空二叉樹(shù)，則F(T)為空;2)如果T為非空二叉樹(shù)，則F(T)中的第一棵樹(shù)T0的根結(jié)點(diǎn)為T的根結(jié)點(diǎn);T0的根結(jié)點(diǎn)的子樹(shù)所組成的序列是由T的左子樹(shù)還原而成的森林F(T的左子樹(shù));F中除T0以外的其余的樹(shù)所組成的序列(T1，T2，…，Tm-1)是由T的右子樹(shù)還原而成的森林F(T的右子樹(shù))。49例5051線索二叉樹(shù)線索：指向前驅(qū)或后繼結(jié)點(diǎn)的指針?lè)Q為線索。線索二叉樹(shù)：加上了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹(shù)稱為線索二叉樹(shù)。對(duì)二叉樹(shù)以某種次序進(jìn)行遍歷以使其變成線索二叉樹(shù)的過(guò)程，稱之為二叉樹(shù)的線索化。lchildlflagdatarflagrchild52其中：左標(biāo)志lflag=0表示lchild是指向結(jié)點(diǎn)的左孩子的指針，否則，為指向結(jié)點(diǎn)的前驅(qū)的左線索。右標(biāo)志rflag=0表示rchild是指向結(jié)點(diǎn)的右孩子的指針，否則，為指向結(jié)點(diǎn)的后繼的右線索。

線索二叉樹(shù)類型定義：typedefstructBTNode{ ElemTypedata;

intlflag,rflag; structBTNode*lchild,*rchild;}BTNode;根據(jù)遍歷的順序，線索二叉樹(shù)可以分為先序線索二叉樹(shù)、中序線索二叉樹(shù)和后序線索二叉樹(shù)。53二叉樹(shù)線索化的步驟（1）設(shè)兩個(gè)指針，分別指向當(dāng)前結(jié)點(diǎn)和當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。（2）若前驅(qū)結(jié)點(diǎn)不為空，或者說(shuō)根結(jié)點(diǎn)不是序列中的第一個(gè)結(jié)點(diǎn)，同時(shí)前驅(qū)結(jié)點(diǎn)rflag=1（即前驅(qū)結(jié)點(diǎn)沒(méi)有右孩子）時(shí)，則將根結(jié)點(diǎn)的指針賦給前驅(qū)結(jié)點(diǎn)的右指針域，即給前驅(qū)結(jié)點(diǎn)加右線索。（3）若根結(jié)點(diǎn)沒(méi)有左孩子，則令lflag=1，同時(shí)把前驅(qū)結(jié)點(diǎn)的指針賦給根結(jié)點(diǎn)的左指針域，即給根結(jié)點(diǎn)加左線索。（4）若根結(jié)點(diǎn)沒(méi)有右孩子，則令rflag=l，以便訪問(wèn)到下一個(gè)結(jié)點(diǎn)時(shí)，給它加右線索。（5）將根結(jié)點(diǎn)指針賦給保存前驅(qū)結(jié)點(diǎn)指針的變量，以便當(dāng)訪問(wèn)下一個(gè)結(jié)點(diǎn)時(shí)，此根結(jié)點(diǎn)成為前驅(qū)結(jié)點(diǎn)。54中序線索二叉樹(shù)55中序線索鏈表565.5.2二叉樹(shù)的線索化P113-114InThread函數(shù)：線索化樹(shù)的函數(shù)。InOrderThread函數(shù)：調(diào)用InThread函數(shù)，完成整棵樹(shù)的線索化。575.5.3線索二叉樹(shù)的操作查找前驅(qū)節(jié)點(diǎn)算法：P114pre函數(shù)查找后繼節(jié)點(diǎn)算法：P115succ函數(shù)遍歷算法（非遞歸）：P115ThTreeInOrder函數(shù)58二叉樹(shù)的遍歷練習(xí)59先序遍歷：1,2,4,8,9,5,10,11,3,6,12,7中序遍歷：8,4,9,2,10,5,11,1,12,6,3,7后序遍歷：8,9,4,10,11,5,2,12,6,7,3,1二叉樹(shù)的遍歷練習(xí)60先序遍歷：1,2,4,8,9,5,10,11,3,6,12,13,7,14,15中序遍歷：8,4,9,2,10,5,11,1,12,6,13,3,14,7,15后序遍歷：8,9,4,10,11,5,2,12,13,6,14,15,7,3,1

61中序遍歷的非遞歸算法ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B訪問(wèn)：C(4)62pABCDEFGiP->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)63ABCDEFGiP->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)64ABCDEFGiP->A訪問(wèn)：CBEGDFp=NULL(13)ABCDEFGi訪問(wèn)：CBEGDFAp(14)ABCDEFGi訪問(wèn)：CBEGDFAp=NULL(15)二叉樹(shù)遍歷操作應(yīng)用舉例求二叉樹(shù)中以值為x的結(jié)點(diǎn)為根的子樹(shù)深度在二叉樹(shù)中求指定結(jié)點(diǎn)的層數(shù)。按先序序列建立二叉樹(shù)的二叉鏈表。求二叉樹(shù)的葉子數(shù)65二叉樹(shù)的應(yīng)用（1）用二叉樹(shù)表示表達(dá)式的運(yùn)算假定有表達(dá)式a+b*(c-d)-e/f，則可以用二叉樹(shù)表示如下：66二叉樹(shù)的應(yīng)用（2）用二叉樹(shù)表示雙人比賽的所有可能結(jié)局。假定要舉行個(gè)人乒乓球比賽，比賽規(guī)則為三局兩勝制，則運(yùn)動(dòng)員A與運(yùn)動(dòng)員B的比賽的所有可能結(jié)局如圖67應(yīng)用實(shí)例算術(shù)表達(dá)式的中綴、前綴和后綴表示法如果用一棵二叉樹(shù)表示一個(gè)表達(dá)式，那么使用先序、中序和后序遍歷二叉樹(shù)就分別得到表達(dá)式的前綴表示、中綴表示和后綴表示。68應(yīng)用實(shí)例例1要求使用遞歸方法建立表達(dá)式（4*8+6/2）的二叉樹(shù)，并分別以先序、中序、后序的遞歸遍歷算法輸出表達(dá)式的前綴表示、中綴表示和后綴表示，最后計(jì)算該表達(dá)式的值。69分析：圖中的二叉樹(shù)使用中序遍歷得到的遍歷序列為：4*8+6/2；使用先序遍歷得到的遍歷序列為：+*48/62；使用后序遍歷得到的遍歷序列為：48*62/+。要建立表達(dá)式二叉樹(shù)，可以先建立根結(jié)點(diǎn)，然后遞歸建立左子樹(shù)和右子樹(shù)。要輸出表達(dá)式的前綴表示、中綴表示和后綴表示，只需要前序、中序和后序遍歷二叉樹(shù)并輸出遍歷結(jié)點(diǎn)的值。要計(jì)算表達(dá)式的值，需要遞歸計(jì)算左子樹(shù)和右子樹(shù)的值，然后利用根結(jié)點(diǎn)的運(yùn)算符將這兩個(gè)值進(jìn)行運(yùn)算。704.7哈夫曼樹(shù)哈夫曼樹(shù)的基本概念構(gòu)造哈夫曼樹(shù)哈夫曼編碼71哈夫曼樹(shù)的基本概念路徑：從樹(shù)中一個(gè)結(jié)點(diǎn)A到另一個(gè)結(jié)點(diǎn)B的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。注意：這兩個(gè)結(jié)點(diǎn)之間必須存在前后繼關(guān)系，也就說(shuō)，從結(jié)點(diǎn)A到結(jié)點(diǎn)B的路徑上所有結(jié)點(diǎn)都是結(jié)點(diǎn)B的祖先結(jié)點(diǎn)。路徑長(zhǎng)度：從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)所經(jīng)過(guò)的分支個(gè)數(shù)，稱為路徑長(zhǎng)度。結(jié)點(diǎn)的權(quán)：在實(shí)際應(yīng)用中，很多結(jié)點(diǎn)都帶有一個(gè)有意義的（表示自己的地位）數(shù)，稱該數(shù)為結(jié)點(diǎn)的權(quán)。帶權(quán)路徑長(zhǎng)度：從根節(jié)點(diǎn)到該結(jié)點(diǎn)的路徑長(zhǎng)度乘以該結(jié)點(diǎn)的權(quán)，就得到該結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度。72哈夫曼樹(shù)的基本概念樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)的帶權(quán)路徑長(zhǎng)度是樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，通常記作其中，n是樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)，wk和lk分別是葉子結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長(zhǎng)度。哈夫曼樹(shù)：又稱最優(yōu)二叉樹(shù)，是指帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)。它最早是在1952年由Haffman提出的，因此稱為哈夫曼樹(shù)。73哈夫曼樹(shù)的基本概念從結(jié)點(diǎn)B到結(jié)點(diǎn)G的路徑是結(jié)點(diǎn)序列B、E、G，路徑長(zhǎng)度為2。假設(shè)結(jié)點(diǎn)D和結(jié)點(diǎn)G的權(quán)分別為3和4，則結(jié)點(diǎn)D的帶權(quán)路徑長(zhǎng)度為2*3=6，結(jié)點(diǎn)G的帶權(quán)路徑長(zhǎng)度為3*4=12。假設(shè)結(jié)點(diǎn)D、G、F的權(quán)分別為3、4、5，則樹(shù)的帶權(quán)路徑長(zhǎng)度為3*2+4*3+5*2=28。74舉例假定有4個(gè)節(jié)點(diǎn)A、B、C、D，它們的權(quán)分別是8、6、3、1，則以這四個(gè)結(jié)點(diǎn)為葉子結(jié)點(diǎn)的二叉樹(shù)如圖。75（a）WPL=8*2+6*2+3*2+1*2=36（b）WPL=8*2+6*3+3*3+1*1=44（c）WPL=8*1+6*2+3*3+1*3=32舉例有些課程需要將最終的分?jǐn)?shù)由百分制轉(zhuǎn)換成五級(jí)分制，語(yǔ)句如下：if(a<60) b="不及格";elseif(a<70) b="及格";elseif(a<80) b="中等";elseif(a<90) b="良好";else b="優(yōu)秀";76構(gòu)造哈夫曼樹(shù)哈夫曼算法（1）根據(jù)給定的n個(gè)權(quán)值{w1,w2,…wn}，構(gòu)成n棵二叉樹(shù)的集合F={T1,T2,…Tn}，其中每棵樹(shù)Ti都只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹(shù)為空。（2）在F中選兩個(gè)根結(jié)點(diǎn)的權(quán)最小的樹(shù)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，且設(shè)樹(shù)的根結(jié)點(diǎn)的權(quán)為左右子樹(shù)的根結(jié)點(diǎn)的權(quán)的和。（3）在F中刪除這兩個(gè)樹(shù)，把新得到的二叉樹(shù)加入F中。（4）重復(fù)第（2）步和第（3）步，直到F中只有一棵樹(shù)。得到的樹(shù)就是哈夫曼樹(shù)。77構(gòu)造哈夫曼樹(shù)例進(jìn)行五級(jí)分制轉(zhuǎn)換，概率分?jǐn)?shù)0-5960-6970-7980-8990-100等級(jí)不及格及格中等良好優(yōu)秀概率0.050.150.400.300.1078構(gòu)造哈夫曼樹(shù)構(gòu)造過(guò)程79哈夫曼編碼8081

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

00010010101100三、哈夫曼樹(shù)的應(yīng)用(哈夫曼編碼)

若將編碼設(shè)計(jì)為長(zhǎng)度不等的二進(jìn)制編碼，即讓待傳字符串中出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼，則轉(zhuǎn)換的二進(jìn)制字符串便可能減少。8283設(shè)要傳送的字符為：ABACCDA若編碼為：A—0B—00 C—1D---01

關(guān)鍵：要設(shè)計(jì)長(zhǎng)度不等的編碼，則必須使任一字符的編碼都不是另一個(gè)字符的編碼的前綴。這種編碼稱作前綴編碼。ABACCDA

000011010但：0000AAAAABABB重碼84設(shè)要傳送的字符為：ABACCDA若編碼為：A—0B—110 C—10D---111

0110010101110ACBD000111采用二叉樹(shù)設(shè)計(jì)二進(jìn)制前綴編碼規(guī)定：左分支用“0”表示；右分支用“1”表示85譯碼過(guò)程：分解接收字符串：遇“0”向左，遇“1”向右；一旦到達(dá)葉子結(jié)點(diǎn)，則譯出一個(gè)字符，反復(fù)由根出發(fā)，直到譯碼完成。

0110010101110ACBD000111ABACCDA86求Huffman編碼：由葉子→根，若：（1）從左分支下去，則分支為“0”；（2）從右分支下去，則分支為“1”。

ACBD00011187例：已知某系統(tǒng)在通訊時(shí)，只出現(xiàn)C，A，S，T，B五種字符，它們出現(xiàn)的頻率依次為2，4，2，3，3，試設(shè)計(jì)Huffman編碼。

W（權(quán)）={2，4，2，3，3}，葉子結(jié)點(diǎn)個(gè)數(shù)n=5148464220001113301構(gòu)造的Huffman樹(shù)TBACS88例：已知某系統(tǒng)在通訊時(shí)，只出現(xiàn)C，A，S，T，B五種字符，它們出現(xiàn)的頻率依次為2，4，2，3，3，試設(shè)計(jì)Huffman編碼。

由Huffman樹(shù)得Huffman編碼為：TBACS000110110111148464220001113301TBACS出現(xiàn)頻率越大的字符，其Huffman編碼越短。堆和堆排序堆排序在最壞情況下時(shí)間復(fù)雜度是O(nlog2n)，空間復(fù)雜性是O(1)。堆排序是借助于擬滿二叉樹(shù)來(lái)進(jìn)行的。若擬滿二叉樹(shù)滿足條件:任意結(jié)點(diǎn)的值均不小于它的左子結(jié)點(diǎn)和右子結(jié)點(diǎn)的值(如果左子結(jié)點(diǎn)或右子結(jié)點(diǎn)存在)，則稱該擬滿樹(shù)為大堆。堆適合用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。8990大堆例:(96，83，27，38，11，9)小堆例：(13，38，27，50，76，65，49，97)962791138831327384965765097可將堆序列看成完全二叉樹(shù)，則堆頂元素（完全二叉樹(shù)的根）必為序列中n個(gè)元素的最大或最小值堆的定義91

堆排序的基本思路：對(duì)一組待排序的