本章學(xué)習(xí)要點掌握樹的相關(guān)概念、樹的表示掌握二

一、本章學(xué)習(xí)要點1、掌握樹的相關(guān)概念、樹的表示2、掌握二叉樹的相關(guān)概念、性質(zhì)和存儲結(jié)構(gòu)；3.掌握二叉樹運算的實現(xiàn)過程4、掌握樹和森林相互轉(zhuǎn)換過程5、掌握哈夫曼樹的構(gòu)造過程和哈夫曼編碼6、靈活應(yīng)用二叉樹的特點解決復(fù)雜的應(yīng)用問題第六章復(fù)習(xí)及例題分析二、復(fù)習(xí)本章是課程的重點內(nèi)容之一。1、知識點1.1二叉樹的定義、性質(zhì)和存儲結(jié)構(gòu)；1.2二叉樹的遍歷和線索化以及遍歷算法算法的各種描述形式；1.3樹和森林的定義、存儲結(jié)構(gòu)與二叉樹的轉(zhuǎn)換、遍歷；1.4最優(yōu)二叉樹（哈夫曼樹）的特性、構(gòu)成和運用。2、內(nèi)容精要2.1樹的概念和定義

樹是以分支關(guān)系定義的層次結(jié)構(gòu)。

樹(Tree)是n(n≥0)個結(jié)點的有限集。在任意一棵非空樹中：(1)有且僅有一個特定的稱為根(Root)的結(jié)點；(2)當(dāng)n>1時，其余結(jié)點可分為m(m>0)個互不相交的有限集T1，T2，…，Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹(SubTree)。

2.2樹的特性及表示方式樹的結(jié)構(gòu)定義是一個遞歸的定義，即在樹的定義中又用到樹的概念，它道出了樹的固有特性。樹是以分支關(guān)系定義的層次結(jié)構(gòu)。樹中除根結(jié)點外其它結(jié)點都由一個分支引入，而每個結(jié)點可有０至多個分支，因此樹中除根結(jié)點無前趨結(jié)點外，其它結(jié)點都只有一個直接前趨結(jié)點，但可有０至多個直接后繼結(jié)點。顯然數(shù)是一種非線性的結(jié)構(gòu)。樹有多種表示形式，如：樹形表示法、嵌套集合表示法、凹入式表示法、廣義表表示法。２.3樹的相關(guān)術(shù)語結(jié)點結(jié)點的度樹的度葉子結(jié)點雙親結(jié)點孩子結(jié)點兄弟結(jié)點樹的深度（高度）路徑路徑長度樹的路徑長度祖先結(jié)點子孫結(jié)點有序樹森林2.4二叉樹的定義和它的五種形態(tài)

二叉樹(BinaryTree)是一種樹型結(jié)構(gòu)，它的特點是每個結(jié)點至多只有二棵子樹(即二叉樹中不存在度大于2的結(jié)點)，并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。五種形態(tài)為空二叉樹、只有一個根結(jié)點的二叉樹、右子樹為空的二叉樹、左子樹為空的二叉樹、左右子樹非空的二叉樹。

2.5二叉樹的性質(zhì)熟練掌握二叉樹的結(jié)構(gòu)特性，掌握完全二叉樹和滿二叉樹的定義，了解相應(yīng)的證明方法。性質(zhì)1在二叉樹的第i層上至多有2i-1個結(jié)點(i≥1)。

性質(zhì)2深度為k的二叉樹至多有2k-1個結(jié)點，(k≥1)。

性質(zhì)3對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。

性質(zhì)4具有n個結(jié)點的完全二叉樹的深度為[log2n]+1。

性質(zhì)5如果對一棵有n個結(jié)點的完全二叉樹(其深度為[log2n]+1)的結(jié)點按層序編號(從第1層到第[log2n]+1層，每層從左到右)，則對任一結(jié)點i(1≤i≤n)，有(1)如果i=1，則結(jié)點i是二叉樹的根，無雙親；如果i>1，則其雙親PARENT(i)是結(jié)點[i/2]。(2)如果2i>n，則結(jié)點i無左孩子(結(jié)點i為葉子結(jié)點)；否則其左孩子LCHILD(i)是結(jié)點2i。(3)如果2i+1>n，則結(jié)點i無右孩子；否則其右孩子RCHILD(i)是結(jié)點2i+1。2.6二叉樹的存儲結(jié)構(gòu)熟悉二叉樹的各種存儲結(jié)構(gòu)的特點及適用范圍。

1、順序存儲按照順序存儲結(jié)構(gòu)的定義，用一組地址連續(xù)的存儲單元依次自上而下、自左至右存儲完全二叉樹上的結(jié)點元素，即將完全二叉樹上編號為i的結(jié)點元素存儲在如上定義的一維數(shù)組中下標(biāo)為i-l的分量中。優(yōu)點：存儲結(jié)構(gòu)簡單缺點：深度為k的二叉樹需2k-1個存儲單元，空間利用率低。

2、二叉鏈表存儲結(jié)構(gòu)設(shè)計不同的結(jié)點結(jié)構(gòu)可構(gòu)成不同形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)。這種存儲結(jié)構(gòu)的優(yōu)點是訪問結(jié)點的孩子很方便。且空間利用率高。2.7遍歷二叉樹和線索二叉樹遍歷二叉樹是二叉樹各種操作的基礎(chǔ)。實現(xiàn)二叉樹遍歷的各種算法與所采用的存儲結(jié)構(gòu)有關(guān)。不僅要熟練掌握各種遍歷策略的遞歸和非遞歸算法，了解遞歸過程中棧的作用和狀態(tài)，而且能靈活運用遍歷算法實現(xiàn)二叉樹的其他操作。理解二叉樹線索化的實質(zhì)是建立結(jié)點與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系，熟悉掌握二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點的前驅(qū)和后繼的方法。二叉樹的線索化過程是基于對二叉樹進(jìn)行遍歷，而線索二叉樹上的線索又為相應(yīng)的遍歷提供了方便。2.8樹的存儲結(jié)構(gòu)及與二叉樹的轉(zhuǎn)換

熟悉樹的各種存儲結(jié)構(gòu)（雙親表示法、孩子表示法、孩子兄弟表示法）及其特點，因為樹和二叉樹都可以用二叉鏈表表示，則以二叉鏈表為媒介很容易導(dǎo)出樹與二叉樹之間的對應(yīng)關(guān)系。掌握樹和森林與二叉樹的轉(zhuǎn)換方法。建立存儲結(jié)構(gòu)是其它操作的前提，因此應(yīng)掌握1至2種建立二叉樹和樹的存儲結(jié)構(gòu)方法（雙親表示法、孩子表示法、孩子兄弟表示法）。2.9森林與二叉樹的轉(zhuǎn)換（略）2.10樹和森林的遍歷樹與森林的先根序遍歷結(jié)果與對應(yīng)的二叉樹的先序序列相同，后根序遍歷與對應(yīng)二叉樹的中序序列相同。2.11最優(yōu)二叉樹（哈夫曼樹）的概念樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點的帶權(quán)路徑長度之和，通常記作WPL，帶權(quán)路徑長度WPL最小的二叉樹稱做最優(yōu)二叉樹或赫夫曼樹。2.13赫夫曼樹構(gòu)造算法。(1)根據(jù)給定的n個權(quán)值{Wl，W2，…，Wn}構(gòu)成n棵二叉樹的集合F={T1，T2，…，Tn}，其中每棵二叉樹Ti中只有一個帶權(quán)為Wi的根結(jié)點，其左右子樹均空。(2)在F中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和。(3)在F中刪除這兩棵樹，同時將新得到的二叉樹加入到F中。(4)重復(fù)(2)和(3)，直到F只含一棵樹為止。這棵樹便是赫夫曼樹。2.14哈夫曼樹的應(yīng)用1、哈夫曼編碼了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和哈夫曼編碼的方法。2、最佳判定

三、例題分析例1若一棵二叉樹有2003個結(jié)點，且無度為1的結(jié)點，則葉結(jié)點的個數(shù)為（）【解】由二叉樹的性質(zhì)3可知，葉結(jié)點的個數(shù)比雙分支結(jié)點個數(shù)多1，設(shè)葉結(jié)點個數(shù)為n0，則雙分支結(jié)點個數(shù)為n0+1,又已知二叉樹中只有雙分支結(jié)點和葉結(jié)點，則有：n0+n0+1=2003,因此n0為1001，即葉結(jié)點個數(shù)為1001.1001例2試找出分別滿足下面條件的所有二叉樹。（1）先序序列和中序序列相同（2）中序序列和后序序列相同（3）先序序列和后序序列相同【解】(1)先序序列和中序序列相同的二叉樹為空樹或任一結(jié)點均無左孩子的非空二叉樹；（2）中序序列和后序序列相同的二叉樹為空樹或任一結(jié)點均無右孩子的非空二叉樹；（3）先序序列和后序序列相同的二叉樹為空樹或僅有一個結(jié)點的二叉樹。例3某二叉樹結(jié)點的中序序列為ABCDEFG,后序序列為BDCAFGE則該二叉樹結(jié)點的前序序列為（）.【解】由二叉樹本身的性質(zhì)可知，已知其中序和后序，可求其前序。其方法的第1步是確定二叉樹的根結(jié)點，然后分別確定左右子樹。在左右子樹中重復(fù)此方法，直到確定所有結(jié)點的位置。由后序列可知，其最后一個結(jié)點為二叉樹的根結(jié)點，由中序序列可知根結(jié)點左邊的結(jié)點序列是遍歷左子樹得到的，而根結(jié)點右邊的結(jié)點序列是遍歷右子樹得到的。EACBDGFEABCDFGEAGBCDFBEAGCFD例4設(shè)n0為哈夫曼樹的葉子結(jié)點數(shù)目，則該哈夫曼樹共有（）個結(jié)點?！窘狻抗蚵鼧渲袥]有單分支結(jié)點，它只有雙分支結(jié)點和葉結(jié)點，設(shè)度為2的結(jié)點數(shù)為n2，由二叉樹的性質(zhì)3(n0=n2+1)可得n2=n0-1,因此，哈夫曼樹中的葉子結(jié)點數(shù)n=2n0-1。2n0-1例5設(shè)高度為h的二叉樹上只有度為0或度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為（）?！窘狻拷Y(jié)點最少的情況如下圖所示。除根結(jié)點層只有1個結(jié)點外，其余h-1層均有兩個結(jié)點，結(jié)點總數(shù)=2（h-1)+1=2h-1h例6對一個滿二叉樹，m個樹葉，n個結(jié)點，深度為h，則（）?！窘狻繉τ谏疃葹閔的滿二叉樹，n=20+21+22+……+2h-1=2h-1即n=2h-1例7深度為K的完全二叉樹至少有（）個結(jié)點，至多有（）個結(jié)點，若按自上而下，從左到右次序給結(jié)點編號（從1開始），則編號最小的葉子結(jié)點的編號是（）.【解】深度為K的完全二叉樹結(jié)點最少的情況是第K層只有1個結(jié)點，第1到第K-1層為滿二叉樹，結(jié)點個數(shù)為2k-1-1,此時完全二叉樹的結(jié)點個數(shù)=2k-1-1+1=

2k-1.編號最小的葉子結(jié)點為第k層的最左結(jié)點，第1到第k-1層為滿二叉樹，結(jié)點個數(shù)為2k-1-1，該結(jié)點的編號為2k-1-1+1=

2k-1.因此本題答案為（1）2K-1(2)2k-1(3)2K-1例8

有一二叉鏈表，試編寫按層次順序遍歷二叉樹的算法算法

【解】本算法要借用隊列來完成，基本思想是，只要隊列不為空，就出隊列，然后判斷該結(jié)點是否有左孩子和右孩子，如有就依次輸出左、右孩子的值，然后讓左、右孩子進(jìn)隊列。

voidlayorder(bitreptrT){initqueue(q)/*隊列初始化*/if(T!=NULL){printf(“%f”,T->data);enqueue(q,T);/*入隊列*/while(notemptyqueue(q))/*若隊列非空*/{outqueue(q,p);/*出隊*/if(p->lchild!=NULL){printf(“%f”,p->lchild->data);enqueue(q,p->lchild);/*入隊列*/}if(p->rchild!=NULL){printf(“%”,p->rchild->data);enqueue(q,p->rchild);/*入隊列*/}}}}例9已知二叉樹以二叉鏈表存儲，編寫算法完成：對于樹中每一個元素值為x的結(jié)點，刪去以它為根的子樹，并釋放相應(yīng)的空間?！窘狻縿h除以元素值x為根的子樹，只要能刪除其左右子樹，就可以釋放值為x的根結(jié)點，因此宜采用后序遍歷。刪除值為x結(jié)點，意味著應(yīng)將其父結(jié)點的左(右)孩子指針置空，用層次遍歷易于找到某結(jié)點的父結(jié)點。本題要求刪除樹中每一個元素值為x的結(jié)點的子樹，因此要遍歷完整棵二叉樹。voidDeleteXTree(BiTreebt)

//刪除以bt為根的子樹{DeleteXTree(bt->lchild);DeleteXTree(bt->rchild);

//刪除bt的左子樹、右子樹free(bt);}//DeleteXTree

//釋放被刪結(jié)點所占的存儲空間

voidSearch(BiTreebt,ElemTypex)//在二叉樹上查找所有以x為元素值的結(jié)點，并刪除以其為根的子樹

{BiTreeQ[];

//Q是存放二叉樹結(jié)點指針的隊列，容量足夠大

if(bt){if(bt->data==x){DeleteXTree(bt);exit(0);}//若根結(jié)點的值為x，則刪除整棵樹

{QueueInit(Q);QueueIn(Q,bt);while(!QueueEmpty(Q)){p=QueueOut(Q);if(p->lchild)

//若左子女非空if(p->lchild->data==x)

//左子女結(jié)點值為x,應(yīng)刪除當(dāng)前結(jié)點的左子樹{DeleteXTree(p->lchild);p->lchild=null;}//父結(jié)點的左子女置空elseEnqueue(Q,p->lchild);