第6章 樹和二叉樹,6.1 樹的定義與基本術(shù)語 6.2 二叉樹 6.3 二叉樹的遍歷與線索化 6.4 樹、森林和二叉樹的關(guān)系 6.5 哈夫曼樹及其應(yīng)用 6.6 總結(jié)與提高,6.1 樹的定義與基本術(shù)語,1樹的基本概念 2樹的圖解表示法 3樹的相關(guān)術(shù)語 4樹的抽象數(shù)據(jù)類型,6.1 樹的定義與基本術(shù)語,樹定義：是n（n0）個(gè)結(jié)點(diǎn)的有限集合T。當(dāng)n=0時(shí)，稱為空樹；當(dāng)n0時(shí)，該集合滿足如下條件：,(1) 其中必有一個(gè)稱為根（root）的特定結(jié)點(diǎn)，它沒有直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。,(2) 其余n-1個(gè)結(jié)點(diǎn)可以劃分成m（m0）個(gè)互不相交的有限集T1，T2，T3，Tm，其中Ti又是一棵樹，稱為根root的子樹。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，可有零個(gè)或多個(gè)直接后繼。,1樹的基本概念,例如：一棵樹的邏輯結(jié)構(gòu)圖（6.1）為：,從圖中可以看出它好象一棵倒栽的樹。,2樹的圖解表示法,1）倒置樹結(jié)構(gòu)（樹形表示法）圖6.1,2）文氏圖表示法（嵌套集合形式） 圖6.2,3）廣義表形式（嵌套擴(kuò)號(hào)表示法）,4）凹入表示法 圖6.3,圖6.2 文氏圖表示法,圖6.3 凹入表示法,3.樹的相關(guān)術(shù)語：,結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向其它結(jié)點(diǎn)的分支信息。,結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)的子樹個(gè)數(shù)稱為此結(jié)點(diǎn)的度。,葉結(jié)點(diǎn)：度為0的結(jié)點(diǎn)，即無后繼的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。,分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。,結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開始定義，根結(jié)點(diǎn)的層次為1，根的直接后繼的層次為2，依此類推。,結(jié)點(diǎn)的層次編號(hào)：將樹中的結(jié)點(diǎn)按從上層到下層、同層從左到右的次序排成一個(gè)線性序列，依次給它們編以連續(xù)的自然數(shù)。,樹的度：樹中所有結(jié)點(diǎn)的度的最大值。,樹的高度（深度）：樹中所有結(jié)點(diǎn)的層次的最大值。,有序樹：在樹T中，如果各子樹Ti之間是有先后次序的，則稱為有序樹。,森林：m（m0）棵互不相交的樹的集合。將一棵非空樹的根結(jié)點(diǎn)刪去，樹就變成一個(gè)森林；反之，給森林增加一個(gè)統(tǒng)一的根結(jié)點(diǎn)，森林就變成一棵樹。,同構(gòu)：對(duì)兩棵樹，通過對(duì)結(jié)點(diǎn)適當(dāng)?shù)刂孛?，就可以使兩棵樹完全相等（結(jié)點(diǎn)對(duì)應(yīng)相等，對(duì)應(yīng)結(jié)點(diǎn)的相關(guān)關(guān)系也像等），則稱這兩棵樹同構(gòu)。,雙親結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的直接前驅(qū)稱為該結(jié)點(diǎn)的雙親結(jié)點(diǎn)。上圖中A是B、C的雙親。,兄弟結(jié)點(diǎn)：同一雙親結(jié)點(diǎn)的孩子結(jié)點(diǎn)之間互稱兄弟結(jié)點(diǎn)。上圖中的結(jié)點(diǎn)H、I、J互為兄弟結(jié)點(diǎn)。,祖先結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的祖先結(jié)點(diǎn)是指從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)。如結(jié)點(diǎn)K的祖先結(jié)點(diǎn)是A、B、E。,子孫結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的直接后繼和間接后繼稱為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)。如結(jié)點(diǎn)D的子孫是H、I、J、M。,孩子結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的直接后繼稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。如上圖的B、C是A的孩子。,我們常常借助人類家族樹的術(shù)語，以便于直觀理解結(jié)點(diǎn)間的層次關(guān)系。,堂兄弟：父親是兄弟關(guān)系或堂兄關(guān)系的結(jié)點(diǎn)稱為堂兄弟結(jié)點(diǎn)。在圖6.1中，結(jié)點(diǎn)E、G、H互為堂兄弟。,前輩：層號(hào)比該結(jié)點(diǎn)小的結(jié)點(diǎn)，都稱為該結(jié)點(diǎn)的前輩。,后輩：層號(hào)比該結(jié)點(diǎn)大的結(jié)點(diǎn)，都稱為該結(jié)點(diǎn)的后輩。,4.樹的抽象數(shù)據(jù)類型,數(shù)據(jù)對(duì)象D：一個(gè)集合，該集合中的所有元素具有相同的特性。,數(shù)據(jù)關(guān)系R：若D為空集，則為空樹。若D中僅含有一個(gè)數(shù)據(jù)元素，則R為空集，否則R=H，H是如下的二元關(guān)系：,(1) 在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下沒有前驅(qū)。,(2) 除root以外，D中每個(gè)結(jié)點(diǎn)在關(guān)系H下都有且僅有一個(gè)前驅(qū)。,基本操作：,InitTree（Tree）： 將Tree初始化為一棵空樹。 (2) DestoryTree（Tree）： 銷毀樹Tree。 (3) CreateTree（Tree）： 創(chuàng)建樹Tree。 (4) TreeEmpty（Tree）： 若Tree為空，則返回TRUE，否則返回FALSE。 (5) Root（Tree）： 返回樹Tree的根。 (6) Parent（Tree，x）： 樹Tree存在，x是Tree中的某個(gè)結(jié)點(diǎn)。若x為非根結(jié)點(diǎn)，則返回它的雙親，否則返回“空”。 (7) FirstChild（Tree，x）： 樹Tree存在，x是Tree中的某個(gè)結(jié)點(diǎn)。若x為非葉子結(jié)點(diǎn)，則返回它的第一個(gè)孩子結(jié)點(diǎn)，否則返回“空”。 (8) NextSibling（Tree，x）： 樹Tree存在，x是Tree中的某個(gè)結(jié)點(diǎn)。若x不是其雙親的最后一個(gè)孩子結(jié)點(diǎn)，則返回x后面的下一個(gè)兄弟結(jié)點(diǎn)，否則返回“空”。,基本操作:,(9) InsertChild（Tree，p，Child）： 樹Tree存在，p指向Tree中某個(gè)結(jié)點(diǎn)，非空樹Child與Tree不相交。將Child插入Tree中，做p所指向結(jié)點(diǎn)的子樹。 (10) DeleteChild（Tree，p，i）： 樹Tree存在，p指向Tree中某個(gè)結(jié)點(diǎn)，1id，d為p所指向結(jié)點(diǎn)的度。刪除Tree中p所指向結(jié)點(diǎn)的第i棵子樹。 (11) TraverseTree（Tree，Visit（）： 樹Tree存在，Visit（）是對(duì)結(jié)點(diǎn)進(jìn)行訪問的函數(shù)。按照某種次序?qū)銽ree的每個(gè)結(jié)點(diǎn)調(diào)用Visit（）函數(shù)訪問一次且最多一次。若Visit（）失敗，則操作失敗。,6.2 二叉樹,6.2.1 二叉樹的定義與基本操作,6.2.2 二叉樹的性質(zhì),6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu),6.2.1 二叉樹的定義與基本操作,定義：我們把滿足以下兩個(gè)條件的樹型結(jié)構(gòu)叫做二叉樹（Binary Tree）： （1）每個(gè)結(jié)點(diǎn)的度都不大于2； （2）每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)次序不能任意顛倒。,下面給出二叉樹的五種基本形態(tài)：,二叉樹的基本操作：,Initiate（bt）：將bt初始化為空二叉樹。 (2) Create(bt)：創(chuàng)建一棵非空二叉樹bt。 (3) Destory（bt）： 銷毀二叉樹bt。 (4) Empty（bt）： 若bt為空，則返回TRUE，否則返回FALSE。 (5) Root(bt)： 求二叉樹bt的根結(jié)點(diǎn)。若bt為空二叉樹，則函數(shù)返回“空”。 (6) Parent（bt，x）：求雙親函數(shù)。求二叉樹bt中結(jié)點(diǎn)x的雙親結(jié)點(diǎn)。若結(jié)點(diǎn)x是二叉樹的根結(jié)點(diǎn)或二叉樹bt中無結(jié)點(diǎn)x，則返回“空”。,基本操作：,(7) LeftChild（bt，x）：求左孩子。若結(jié)點(diǎn)x為葉子結(jié)點(diǎn)或x不在bt中，則返回“空”。 (8) RightChild（bt，x）：求右孩子。若結(jié)點(diǎn)x為葉子結(jié)點(diǎn)或x不在bt中，則返回“空”。 (9) Traverse（bt）: 遍歷操作。按某個(gè)次序依次訪問二叉樹中每個(gè)結(jié)點(diǎn)一次且僅一次。 (10) Clear（bt）：清除操作。將二叉樹bt置為空樹。,6.2.2 二叉樹的性質(zhì),性質(zhì)1：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i1)。,當(dāng)i=1時(shí)，整個(gè)二叉樹只有一根結(jié)點(diǎn)，此時(shí)2i-1=20=1，結(jié)論成立。,證明：,假設(shè)i=k時(shí)結(jié)論成立，即第k層上結(jié)點(diǎn)總數(shù)最多為2k-1個(gè)。,現(xiàn)證明當(dāng)i=k+1時(shí)，結(jié)論成立：,因?yàn)槎鏄渲忻總€(gè)結(jié)點(diǎn)的度最大為2，則第k+1層的結(jié)點(diǎn)總數(shù)最多為第k層上結(jié)點(diǎn)最大數(shù)的2倍，即22k-1=2(k+1)-1，故結(jié)論成立。,性質(zhì)2：深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)（k1）。,證明：,因?yàn)樯疃葹閗的二叉樹，其結(jié)點(diǎn)總數(shù)的最大值是將二叉樹每層上結(jié)點(diǎn)的最大值相加，所以深度為k的二叉樹的結(jié)點(diǎn)總數(shù)至多為：,故結(jié)論成立。,性質(zhì)3：對(duì)任意一棵二叉樹T，若終端結(jié)點(diǎn)數(shù)為n0，而其度數(shù)為2的結(jié)點(diǎn)數(shù)為n2，則n0= n2+1 。,證明：設(shè)二叉樹中結(jié)點(diǎn)總數(shù)為n，n1為二叉樹中度為1的結(jié)點(diǎn)總數(shù)。因?yàn)槎鏄渲兴薪Y(jié)點(diǎn)的度小于等于2，所以有 n= n0+ n1+n2 設(shè)二叉樹中分支數(shù)目為B，因?yàn)槌Y(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均對(duì)應(yīng)一個(gè)進(jìn)入它的分支，所以有：n=B+1。 又因?yàn)槎鏄渲械姆种Ф际怯啥葹?和度為2的結(jié)點(diǎn)發(fā)出，所以分支數(shù)目為：B=n1+2n2 整理上述兩式可得到：n=B+1=n1+2n2+1 將n= n0+ n1+n2代入上式得出n0+ n1+n2=n1+2n2+1，整理后得n0= n2+1，故結(jié)論成立。,兩種特殊的二叉樹：,滿二叉樹：深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹。在滿二叉樹中，每層結(jié)點(diǎn)都是滿的，即每層結(jié)點(diǎn)都具有最大結(jié)點(diǎn)數(shù)。,滿二叉樹,完全二叉樹：,關(guān)系：滿二叉樹必為完全二叉樹，而完全二叉樹不一定是滿二叉樹。,深度為k，結(jié)點(diǎn)數(shù)為n的二叉樹，如果其結(jié)點(diǎn)1n的位置序號(hào)分別與滿二叉樹的結(jié)點(diǎn)1n的位置序號(hào)一一對(duì)應(yīng)，則為完全二叉樹,性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為2n+1。,證明：設(shè)n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為k，根據(jù)性質(zhì)2可知，k-1層滿二叉樹的結(jié)點(diǎn)總數(shù)為： 2k-1-1 k層滿二叉樹的結(jié)點(diǎn)總數(shù)為： 2k-1 顯然有： 2k-1 - 1 < n 2k- 1 2k- 1 n < 2k 取對(duì)數(shù)有：k -1 log2n < k 因?yàn)閗是整數(shù)，所以k -1 =log2n ， k= 2n+1 結(jié)論成立。,性質(zhì)5：對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上到下和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點(diǎn)從1開始順序編號(hào)，則對(duì)于任意的序號(hào)為i的結(jié)點(diǎn)有：,(1)若i = 1, 則 i 無雙親結(jié)點(diǎn) 若i 1, 則 i 的雙親結(jié)點(diǎn)為i /2 (2)若2*i n, 則 i 無左孩子 若2*in, 則 i 結(jié)點(diǎn)的左孩子結(jié)點(diǎn)為2*i (3)若 2*i+1 n ,則i 無右孩子 若 2*i+1n, 則i的右孩子結(jié)點(diǎn)為2* i+1,用歸納法證明其中的(2)和(3)。,6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu),二叉樹的結(jié)構(gòu)是非線性的，每一結(jié)點(diǎn)最多可有兩個(gè)后繼。,二叉樹的存儲(chǔ)結(jié)構(gòu)有兩種：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。,1.順序存儲(chǔ)結(jié)構(gòu)：是用一組連續(xù)的存儲(chǔ)單元來存放二叉樹的數(shù)據(jù)元素 。,二叉樹的順序存儲(chǔ)結(jié)構(gòu),對(duì)于一般的二叉樹，我們必須按照完全二叉樹的形式來存儲(chǔ)，就會(huì)造成空間的浪費(fèi)。單支樹就是一個(gè)極端情況。,單支樹,2. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),對(duì)于任意的二叉樹來說，每個(gè)結(jié)點(diǎn)只有兩個(gè)孩子，一個(gè)雙親結(jié)點(diǎn)。我們可以設(shè)計(jì)每個(gè)結(jié)點(diǎn)至少包括三個(gè)域：數(shù)據(jù)域、左孩子域和右孩子域：,二叉鏈表,二叉樹T,二叉鏈表,typedef struct Node DataType data; strct Node * LChild; struct Node * RChild; BiTNode, *BiTree;,用C語言描述定義二叉樹的二叉鏈表結(jié)構(gòu)如下 ：,結(jié)論：若一個(gè)二叉樹含有n個(gè)結(jié)點(diǎn)，則它的二叉鏈表中必含有2n個(gè)指針域，其中必有n1個(gè)空的鏈域。,證明：,分支數(shù)目B=n-1，即非空的鏈域有n-1個(gè)，故空鏈域有2n-(n-1)=n+1個(gè)。,為了便于找到雙親結(jié)點(diǎn)，可以增加一個(gè)Parent域，以指向該結(jié)點(diǎn)的雙親結(jié)點(diǎn)。采用這種結(jié)點(diǎn)結(jié)構(gòu)存放稱做二叉樹的三叉鏈表存儲(chǔ)結(jié)構(gòu)。,6.3 二叉樹的遍歷與線索化,6.3.1 二叉樹的遍歷 6.3.2 遍歷算法應(yīng)用 6.3.3 基于棧的遞歸消除 6.3.4 線索二叉樹 6.3.5 由遍歷序列確定二叉樹,6.3 二叉樹的遍歷與線索化,二叉樹的遍歷：指按一定規(guī)律對(duì)二叉樹中的每個(gè)結(jié)點(diǎn)進(jìn)行訪問且僅訪問一次。,二叉樹的基本結(jié)構(gòu)由根結(jié)點(diǎn)、左子樹和右子樹組成,如圖示,6.3.1 二叉樹的遍歷,用L、D、R分別表示遍歷左子樹、訪問根結(jié)點(diǎn)、遍歷右子樹，那么對(duì)二叉樹的遍歷順序就可以有：,訪問根，遍歷左子樹，遍歷右子樹(記做DLR)。 訪問根，遍歷右子樹，遍歷左子樹(記做DRL)。 遍歷左子樹，訪問根，遍歷右子樹(記做LDR)。 遍歷左子樹，遍歷右子樹，訪問根 (記做LRD)。 遍歷右子樹，訪問根，遍歷左子樹 (記做RDL)。 遍歷右子樹，遍歷左子樹，訪問根 (記做RLD)。,在以上六種遍歷方式中，如果我們規(guī)定按先左后右的順序，那么就只剩有 DLR 、LDR 和LRD三種。根據(jù)對(duì)根的訪問先后順序不同，分別稱DLR為先序遍歷或先根遍歷；LDR為中序遍歷（對(duì)稱遍歷）；LRD為后序遍歷。,注意：先序、中序、后序遍歷是遞歸定義的，即在其子樹中亦按上述規(guī)律進(jìn)行遍歷。,三種遍歷方法的遞歸定義：,（1）先序遍歷（DLR）操作過程：,若二叉樹為空，則空操作，否則依次執(zhí)行如下操作： 訪問根結(jié)點(diǎn)； 按先序遍歷左子樹； 按先序遍歷右子樹。,若二叉樹為空，則空操作，否則依次執(zhí)行如下操作： 按中序遍歷左子樹； 訪問根結(jié)點(diǎn)； 按中序遍歷右子樹。,（2）中序遍歷（LDR）操作過程,（3）后序遍歷（LRD）操作過程：,若二叉樹為空，則空操作，否則依次執(zhí)行如下操作： 按后序遍歷左子樹； 按后序遍歷右子樹； 訪問根結(jié)點(diǎn)。,對(duì)于如下圖的二叉樹，其先序、中序、后序遍歷的序列為： 先序遍歷： A、B、D、F、G、C、E、H 。 中序遍歷： B、F、D、G、A、C、E、H 。 后序遍歷： F、G、D、B、H、E、C、A 。,以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，討論二叉樹的遍歷算法,1) 先序遍歷,void PreOrder(BiTree root) /*先序遍歷二叉樹, root為指向二叉樹(或某一子樹)根結(jié)點(diǎn)的指針*/ if (root!=NULL) Visit(root -data); /*訪問根結(jié)點(diǎn)*/ PreOrder(root -LChild); /*先序遍歷左子樹*/ PreOrder(root -RChild); /*先序遍歷右子樹*/ ,2) 中序遍歷,void InOrder(BiTree root) /*中序遍歷二叉樹, root為指向二叉樹(或某一子樹)根結(jié)點(diǎn)的指針*/ if (root!=NULL) InOrder(root -LChild); /*中序遍歷左子樹*/ Visit(root -data); /*訪問根結(jié)點(diǎn)*/ InOrder(root -RChild); /*中序遍歷右子樹*/ ,3) 后序遍歷,void PostOrder(BiTree root) /* 后序遍歷二叉樹，root為指向二叉樹(或某一子樹)根結(jié)點(diǎn)的指針*/ if(root!=NULL) PostOrder(root -LChild); /*后序遍歷左子樹*/ PostOrder(root -RChild); /*后序遍歷右子樹* Visit(root -data); /*訪問根結(jié)點(diǎn)*/ ,以中序遍歷為例來說明中序遍歷二叉樹的遞歸過程,A,B,D,C,E,第一次經(jīng)過,第二次經(jīng)過,第三次經(jīng)過,6.3.2 遍歷算法應(yīng)用,1.輸出二叉樹種的結(jié)點(diǎn),【算法描述】 void PreOrder(BiTree root) /* 先序遍歷輸出二叉樹結(jié)點(diǎn), root為指向二叉樹根結(jié)點(diǎn)的指針 */ if (root!=NULL) printf (root -data); /* 輸出根結(jié)點(diǎn) */ PreOrder(root -LChild); /* 先序遍歷左子樹 */ PreOrder(root -RChild); /* 先序遍歷右子樹 */ ,【算法思想】輸出二叉樹中的結(jié)點(diǎn)并無次序要求，因此可用三種遍歷算法中的任何一種完成，只需將訪問操作具體變?yōu)榇蛴〔僮骷纯?。下面給出采用前序遍歷實(shí)現(xiàn)的算法。,2.輸出二叉樹中的葉子結(jié)點(diǎn),【算法思想】輸出二叉樹中的葉子結(jié)點(diǎn)與輸出二叉樹中的結(jié)點(diǎn)相比，它是一個(gè)有條件的輸出問題，即在遍歷過程中走到每一個(gè)結(jié)點(diǎn)時(shí)需進(jìn)行測(cè)試，看是否滿足葉子結(jié)點(diǎn)的條件。,【算法描述】 void PreOrder(BiTree root) /* 先序遍歷輸出二叉樹中的葉子結(jié)點(diǎn) , root為指向二叉樹根結(jié)點(diǎn)的指針 */ if (root!=NULL) if (root -LChild=NULL /* 先序遍歷右子樹 */ ,3.統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)目,【算法思想】統(tǒng)計(jì)二叉樹中的葉子結(jié)點(diǎn)數(shù)目并無次序要求，因此可用三種遍歷算法中的任何一種完成，只需將訪問操作具體變?yōu)榕袛嗍欠駷槿~子結(jié)點(diǎn)及統(tǒng)計(jì)操作即可。,【算法描述】 /* LeafCount為保存葉子結(jié)點(diǎn)數(shù)目的全局變量,調(diào)用之前初始化值為0 */ void leaf(BiTree root) if(root!=NULL) leaf(root-LChild); leaf(root-RChild); if (root -LChild=NULL ,方法一：,【算法思想】采用遞歸算法，如果是空樹，返回0；如果只有一個(gè)結(jié)點(diǎn)，返回1；否則為左右子樹的葉子結(jié)點(diǎn)數(shù)之和。,【算法描述】 int leaf(BiTree root) int LeafCount; if(root=NULL) LeafCount =0; else if (root-LChild=NULL) ,方法二：,3.統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)目,4.建立二叉鏈表方式存儲(chǔ)的二叉樹,【算法思想】采用類似先序遍歷的遞歸算法，首先讀入當(dāng)前根結(jié)點(diǎn)的數(shù)據(jù)，如果是.則將當(dāng)前樹根置為空，否則申請(qǐng)一個(gè)新結(jié)點(diǎn)，存入當(dāng)前根結(jié)點(diǎn)的數(shù)據(jù)，分別用當(dāng)前根結(jié)點(diǎn)的左子域和右子域進(jìn)行遞歸調(diào)用，創(chuàng)建左右子樹。,【算法描述】 void CreateBiTree(BiTree *bt) char ch; ch=getchar(); if(ch=.) *bt=NULL; else *bt=(BiTree)malloc(sizeof(BiTNode); (*bt)-data=ch; CreateBiTree( ,5.求二叉樹的高度,設(shè)函數(shù)表示二叉樹bt的高度，則遞歸定義如下: 若bt為空，則高度為0 若bt非空，其高度應(yīng)為其左右子樹高度的最大值加1,左 子 樹,右 子 樹,bt,hl,hr,High=max(hl+hr)+1,【算法思想】二叉樹bt的高度可以遞歸定義如下： l 若bt為空，則高度為0 l若bt非空，其高度應(yīng)為其左右子樹高度的最大值加1,【算法描述】 int PostTreeDepth(BiTree bt) /* 后序遍歷求二叉樹bt高度的遞歸算法 */ int hl, hr, max; if(bt!=NULL) hl=PostTreeDepth(bt-LChild); /* 求左子樹的深度 */ hr=PostTreeDepth(bt-RChild); /* 求右子樹的深度 */ max=hlhr?hl:hr; /* 得到左、右子樹深度較大者*/ return(max+1); /* 返回樹的深度 */ else return(0); /* 如果是空樹，則返回0 */ ,求二叉樹的高度是也可用前序遍歷的方式實(shí)現(xiàn)。,【算法思想】二叉樹的高度（深度）為二叉樹中結(jié)點(diǎn)層次的最大值。設(shè)根結(jié)點(diǎn)為第1層的結(jié)點(diǎn)，所有h層的結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)在h+1層。故可以通過遍歷計(jì)算二叉樹中的每個(gè)結(jié)點(diǎn)的層次，其中最大值即為二叉樹的高度。,【算法描述】 void PreTreeDepth(BiTeee bt, int h) /* 先序遍歷求二叉樹bt高度的遞歸算法，h為bt指向結(jié)點(diǎn)所在層次，初值為1*/ /*depth為當(dāng)前求得的最大層次，為全局變量，調(diào)用前初值為0 */ if(bt!=NULL) if(hdepth) depth = h; /*如果該結(jié)點(diǎn)層次值大于depth，更新depth的值*/ PreTreeDepth(bt-Lchild, h+1); /* 遍歷左子樹 */ PreTreeDepth(bt-Rchild, h+1); /* 遍歷右子樹 */ ,6. 按樹狀打印的二叉樹,假設(shè)以二叉鏈表存儲(chǔ)的二叉樹中，每個(gè)結(jié)點(diǎn)所含數(shù)據(jù)元素均為單字母，要求實(shí)現(xiàn)如下圖的打印結(jié)果。,分析：這是二叉樹的橫向顯示問題，橫向顯示應(yīng)是豎向顯示的900旋轉(zhuǎn)，又由于二叉樹的橫向顯示算法一定是中序遍歷算法，所以把橫向顯示的二叉樹算法改為RDL結(jié)構(gòu)，實(shí)現(xiàn)算法為：,【算法思想】 （1）二叉樹的橫向顯示應(yīng)是二叉樹豎向顯示的90。旋轉(zhuǎn)。分析圖6.15圖示可知，這種樹形打印格式要求先打印右子樹，再打印根，最后打印左子樹，按由上而下順序看，其輸出的結(jié)點(diǎn)序列為：CFEADB，這恰為逆中序順序。解決二叉樹的橫向顯示問題采用“逆中序”遍歷框架，所以橫向顯示二叉樹算法為先右子樹、再根結(jié)點(diǎn)、再左子樹的RDL結(jié)構(gòu)。 （2）在這種輸出格式中，結(jié)點(diǎn)的左右位置與結(jié)點(diǎn)的層深有關(guān)，故算法中設(shè)置了一個(gè)表示當(dāng)前根結(jié)點(diǎn)層深的參數(shù)，以控制輸出結(jié)點(diǎn)的左右位置，每當(dāng)遞歸進(jìn)層時(shí)層深參數(shù)加1。這些操作應(yīng)在訪問根結(jié)點(diǎn)時(shí)實(shí)現(xiàn)。,【算法描述】 void PrintTree(BiTree bt, int nLayer) /* 按豎向樹狀打印的二叉樹 */ if(bt = =NULL) return; PrintTree(bt -RChild, nLayer+1); PrintTree(bt -LChild , nLayer+1); ,for(int i=0; idata); /*按逆中序輸出結(jié)點(diǎn)，用層深決定的左右位置*/,思考：對(duì)二叉樹實(shí)現(xiàn)左右子樹交換，是否可采用先序、中序、后序中的任何一種算法實(shí)現(xiàn)，請(qǐng)簡(jiǎn)要說明原因。,6.3.3 基于棧的遞歸消除,1. 中序遍歷二叉樹的非遞歸算法,首先應(yīng)用遞歸進(jìn)層的三件事與遞歸退層的三件事的原則,直接先給出中序遍歷二叉樹的非遞歸算法基本實(shí)現(xiàn)思路。,在大量復(fù)雜的情況下，遞歸的問題無法直接轉(zhuǎn)換成循環(huán)，需要采用工作棧消除遞歸。工作棧提供一種控制結(jié)構(gòu)，當(dāng)遞歸算法進(jìn)層時(shí)需要將信息保留；當(dāng)遞歸算法出層時(shí)需要從棧區(qū)退出信息。,【算法思想】 （1）針對(duì)左遞歸，寫出遞歸進(jìn)層的三件事 （2）接著寫出左遞歸返回時(shí)應(yīng)執(zhí)行的語句：訪問根結(jié)點(diǎn) （3）接著針對(duì)右遞歸，寫出遞歸進(jìn)層的三件事 （4）針對(duì)遞歸退層，寫出遞歸退層的三件事（左、右遞歸公用）,void inorder(BiTree root); int i=0; p=bt; L1: if (p!=NULL) /* 遍歷左子樹 */ top=top+2; if(topm); stop-1=p; /* 本層參數(shù)進(jìn)棧 */ stop=L2; /* 返回地址進(jìn)棧 */ p=p-LChild; /* 給下層參數(shù)賦值 */ goto L1; /* 轉(zhuǎn)向開始 */ L2: Visit(p-data); /* 訪問根 */ top=top+2; if(top<m); stop-1=p; /* 遍歷右子樹 */,【算法描述】,stop=L3; p=p-RChild; goto L1; L3: if(top!=0) addr=stop; p=stop-1; /* 取出返回地址 */ top=top-2; /* 退出本層參數(shù) */ goto addr; ,可以看到，直接按定義得到的上述算法結(jié)構(gòu)并不好，為使程序合理組織，需去掉goto語句，用循環(huán)句代替if與goto，此時(shí)返回?cái)帱c(diǎn)已無保留的必要，棧區(qū)只需保留本層參數(shù)。,整理后的算法框圖如下圖所示：,【算法思想】 從根結(jié)點(diǎn)開始，只要當(dāng)前結(jié)點(diǎn)存在，或者棧不空，則重復(fù)下面操作：,（1）從當(dāng)前結(jié)點(diǎn)開始，進(jìn)棧并走左子樹，直到左子樹為空。 （2）退棧并訪問。 （3）走右子樹。,【算法描述】 /*sm 表示棧，top表示棧頂指針*/ void inorder(BiTree root) /* 中序遍歷二叉樹，root為二叉樹的根結(jié)點(diǎn) */ top=0; p=root; do while(p!=NULL) if (topm) return; top=top+1; stop=p; p=p-LChild ; /* 遍歷左子樹 */ if(top!=0) p=stop; top=top-1; Visit(p-data); /* 訪問根結(jié)點(diǎn) */ p=p-RChild; /* 遍歷右子樹 */ while(p!=NULL | top!=0) ,【算法思想】 從根結(jié)點(diǎn)開始，只要當(dāng)前結(jié)點(diǎn)存在，或者棧不空，則重復(fù)下面操作：,(1)如果當(dāng)前結(jié)點(diǎn)存在，則進(jìn)棧并走左子樹。 (2)否則退棧并訪問，然后走右子樹。,【算法描述】 void InOrder（BiTree root）/* 中序遍歷二叉樹的非遞歸算法 */ InitStack ( ,遞歸算法的時(shí)間復(fù)雜度分析： 對(duì)有n個(gè)結(jié)點(diǎn)二叉樹，該算法每循環(huán)一次，p指向一個(gè)結(jié)點(diǎn)或空（無左孩子或無右孩子的結(jié)點(diǎn)的空鏈域），因此指向空的次數(shù)為n+1，n為結(jié)點(diǎn)個(gè)數(shù)，故循環(huán)次數(shù)為n+(n+1)=2n+1,從而算法的復(fù)雜度為O(n)。 遞歸算法的空間復(fù)雜度分析：所需棧的空間最多等于二叉樹深度K乘以每個(gè)結(jié)點(diǎn)所需空間數(shù)，記作O(K)，。表面上看，遞歸算法好象并沒有使用棧，實(shí)際上遞歸算法的執(zhí)行，需要反復(fù)多次的自己調(diào)用自己。每調(diào)用一次，系統(tǒng)內(nèi)部都有系統(tǒng)運(yùn)行棧區(qū)在支持，這是隱含的棧，需要保留本層參數(shù)、臨時(shí)變量與返回地址等等。隨著函數(shù)遞歸調(diào)用，運(yùn)行棧繼續(xù)增長(zhǎng)，直到函數(shù)執(zhí)行完，才徹底釋放占用的?？臻g。因此遞歸算法比非遞歸算法占用的空間更多。,2.后序遍歷二叉樹的非遞歸算法,【算法思想】 從根結(jié)點(diǎn)開始，只要當(dāng)前結(jié)點(diǎn)存在，或者棧不空，則重復(fù)下面操作：,(1)從當(dāng)前結(jié)點(diǎn)開始，反復(fù)入棧并左走，直到空的左子樹； (2) 如果棧頂結(jié)點(diǎn)的右子為空，或者頂結(jié)點(diǎn)的右子為剛訪問過的結(jié)點(diǎn)，則退棧并訪問； (3) 否則，右走一步 。,【算法描述】 void PostOrder（BiTree root） BiTNode * p,*q； BiTree sStack_Size; int top=0; q=NULL; p=root; while(p!=NULL | top!=0) while(p!=NULL) top=+; if(top=Stack_Size) OverFlow(); /*棧溢出處理*/ stop=p; p=p-LChild; /*遍歷左子樹*/ if(top0) p=stop; if(p-RChild=NULL) |(p-RChild=q) /* 無右孩子，或右孩子已遍歷過 */, visit(p-data); /* 訪問根結(jié)點(diǎn)* / q=p; /* 保存到q，為下一次已處理結(jié)點(diǎn)前驅(qū) */ top-; p=NULL; else p=p-RChild; ,6.3.4 線索二叉樹,1. 基本概念,二叉樹的遍歷運(yùn)算是將二叉樹中結(jié)點(diǎn)按一定規(guī)律線性化的過程。當(dāng)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)，只能找到結(jié)點(diǎn)的左、右孩子信息，而不能直接得到結(jié)點(diǎn)在遍歷序列中的前驅(qū)和后繼信息。要得到這些信息，第一種方法是將二叉樹遍歷一遍，在遍歷過程中便可得到結(jié)點(diǎn)的前驅(qū)和后繼，但這種動(dòng)態(tài)訪問浪費(fèi)時(shí)間；第二種方法是充分利用二叉鏈表中的空鏈域，將遍歷過程中結(jié)點(diǎn)的前驅(qū)、后繼信息保存下來。,在有n個(gè)結(jié)點(diǎn)的二叉鏈表中共有2n個(gè)鏈域，但只有n-1個(gè)有用非空鏈域，其余n+1個(gè)鏈域是空的。我們可以利用剩下的n+1個(gè)空鏈域來存放遍歷過程中結(jié)點(diǎn)的前驅(qū)和后繼信息。 現(xiàn)作如下規(guī)定：,若結(jié)點(diǎn)有左子樹，則其LChild域指向其左孩子，否則LChild域指向其前驅(qū)結(jié)點(diǎn)；若結(jié)點(diǎn)有右子樹，則其RChild域指向其右孩子，否則RChild域指向其后繼結(jié)點(diǎn)。,為了區(qū)分孩子結(jié)點(diǎn)和前驅(qū)、后繼結(jié)點(diǎn)，為結(jié)點(diǎn)結(jié)構(gòu)增設(shè)兩個(gè)標(biāo)志域，如下圖所示：,其中：,線索：在這種存儲(chǔ)結(jié)構(gòu)中，指向前驅(qū)和后繼結(jié)點(diǎn)的指針叫做線索。,線索鏈表：以這種結(jié)構(gòu)組成的二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，叫做線索鏈表。,線索化：對(duì)二叉樹以某種次序進(jìn)行遍歷并且加上線索的過程叫做線索化。,線索二叉樹：線索化了的二叉樹稱為線索二叉樹。,2. 二叉樹的線索化,【算法思想】,（1）中序線索化采用中序遞歸遍歷算法框架。 （2）加線索操作就是訪問結(jié)點(diǎn)操作。 （3）加線索操作需要利用剛訪問過結(jié)點(diǎn)與當(dāng)前結(jié)點(diǎn)的關(guān)系，因此設(shè)置一個(gè)指針pre，始終記錄剛訪問過的結(jié)點(diǎn)，其操作如下： 如果當(dāng)前遍歷結(jié)點(diǎn)root的左子域?yàn)榭?，則讓左子域指向pre ； 如果前驅(qū)pre的右子域?yàn)榭?，則讓右子域指向當(dāng)前遍歷結(jié)點(diǎn)root； 為下次做準(zhǔn)備，當(dāng)前訪問結(jié)點(diǎn)root作為下一個(gè)訪問結(jié)點(diǎn)的前驅(qū)pre。,void Inthread(BiTree root) /* 對(duì)root所指的二叉樹進(jìn)行中序線索化，其中pre始終指向剛訪問過的結(jié)點(diǎn)，其初值為NULL* / if (root!=NULL) Inthread(root-LChild); /* 線索化左子樹 */ if (root-LChild=NULL) root-Ltag=1; root-LChile=pre; / *置前驅(qū)線索 */ if (pre!=NULL /*線索化右子樹*/ ,【算法描述】,3.在線索二叉樹中找前驅(qū)、后繼結(jié)點(diǎn),(1) 找結(jié)點(diǎn)的中序前驅(qū)結(jié)點(diǎn),【算法描述】 BiTNode * InPre(BiTNode * p) /* 在中序線索二叉樹中查找p的中序前驅(qū), 并用pre指針返回結(jié)果 */ if(p-Ltag=1) pre= p-LChild; /*直接利用線索*/ else /* 在p的左子樹中查找“最右下端”結(jié)點(diǎn) */ for(q= p-LChild;q-Rtag=0;q=q-RChild); pre=q; return(pre); ,下面是對(duì)同一棵二叉樹的遍歷方法不同得到的不同線索樹。,NULL,(2)在中序線索樹中找結(jié)點(diǎn)后繼,對(duì)于結(jié)點(diǎn)p，若要找其后繼結(jié)點(diǎn)，當(dāng)p-Rtag=1時(shí)，p-RChild即為p的后繼結(jié)點(diǎn)；當(dāng)p-Rtag=0時(shí)，說明p有右子樹，此時(shí)p的中序后繼結(jié)點(diǎn)即為其右子樹的“最左下端”的結(jié)點(diǎn)。其查找算法如下：,【算法描述】 BiTNode * InNext(BiTNode * p) /*在中序線索二叉樹中查找p的中序后繼結(jié)點(diǎn)，并用Next指針返回結(jié)果*/ if (p-Rtag=1) Next= p- RChild; /*直接利用線索*/ else /*在p的右子樹中查找“最左下端”結(jié)點(diǎn)*/ for(q= p-RChild; q-Ltag=0 ;q=q-LChild ); Next=q; return(Next) ,4.遍歷中序線索樹,(1)在中序線索樹上求中序遍歷的第一個(gè)結(jié)點(diǎn),【算法描述】 BiTNode * InFirst(BiTree Bt) BiTNode *p=Bt; If(!p) return (NULL); while(p-LTag=0) p=p-Lchild; return p; ,(2)遍歷中序二叉線索樹,【算法描述】 void TInOrder(BiTree Bt) BITNode *p; P=InFirst(Bt); While(p) Visit(p); p = InNext(p)； ,5. 線索二叉樹的插入、刪除運(yùn)算,二叉樹加上線索之后，當(dāng)插入或刪除一結(jié)點(diǎn)時(shí)，可能會(huì)破壞原樹的線索。所以在線索二叉樹中插入或刪除結(jié)點(diǎn)的難點(diǎn)在于：插入一個(gè)結(jié)點(diǎn)后，仍要保持正確的線索。,我們主要以中序線索二叉樹為例，說明線索二叉樹的插入和刪除運(yùn)算。,（1）插入結(jié)點(diǎn)運(yùn)算,在中序線索二叉樹中插入結(jié)點(diǎn)可分為兩種情況： 第一種：將新的結(jié)點(diǎn)插入到二叉樹中，作某結(jié)點(diǎn)的左孩子； 第二種：將新的結(jié)點(diǎn)插入到二叉樹中，作某結(jié)點(diǎn)的右孩子。,我們僅討論后一種情況。,InsNode(BiTNode * p, BiTNode * r)表示在線索二叉樹中插入r所指向的結(jié)點(diǎn)，做p所指結(jié)點(diǎn)的右孩子。,若結(jié)點(diǎn)p的右孩子為空，則插入結(jié)點(diǎn)r的過程很簡(jiǎn)單。原來p的后繼變?yōu)閞的后繼，結(jié)點(diǎn)p變?yōu)閞的前驅(qū)，結(jié)點(diǎn)r成為p的右孩子。結(jié)點(diǎn)r的插入對(duì)p原來的后繼結(jié)點(diǎn)沒有任何的影響。,結(jié)點(diǎn)的右孩子為空時(shí)的插入過程為：,插入前,插入后,若p的右孩子不為空，則插入后，p的右孩子變?yōu)閞的右孩子結(jié)點(diǎn)，p變?yōu)閞的前驅(qū)結(jié)點(diǎn)，r變?yōu)閜的右孩子結(jié)點(diǎn)。這時(shí)還需要修改原來p的右子樹中“最左下端”結(jié)點(diǎn)的左指針域，使它由原來的指向結(jié)點(diǎn)p變?yōu)橹赶蚪Y(jié)點(diǎn)r。插入過程為：,插入前,插入后,void InsNode(BiTNode * p , BiTNode * r) if (p-Rtag=1) /* p無右孩子 */ r-RChild=p-RChild; /* p的后繼變?yōu)閞的后繼 */ r-Rtag=1; p-RChild=r; /* r成為p的右孩子 */ r-LChild=p; /* p變?yōu)閞的前驅(qū) */ r-Ltag=1; else /* p有右孩子 */ s=p-RChild; while(s-Ltag=0) s=s-LChild; /* 查找p結(jié)點(diǎn)的右子樹的“最左下端”結(jié)點(diǎn) */ r-RChild=p-RChild; /* p的右孩子變?yōu)閞的右孩子 */ r-Rtag=0; r-LChild=p; /* p變?yōu)閞的前驅(qū) */ r-Ltag=1; p-RChild=r; /* r變?yōu)閜的右孩子 */ s-LChild=r; /* r變?yōu)閜原來右子樹的“最左下端”結(jié)點(diǎn)的前驅(qū) */ ,【算法描述】,（2）刪除結(jié)點(diǎn)運(yùn)算,與插入操作一樣，在線索二叉樹中刪除一個(gè)結(jié)點(diǎn)也會(huì)破壞原來的線索，所以需要在刪除的過程中保持二叉樹的線索化。,在中序線索二叉樹中刪除結(jié)點(diǎn)r的過程為：,6.3.5 由遍歷序列確定二叉樹,由定義，二叉樹的前序遍歷是先訪問根結(jié)點(diǎn)D，其次遍歷左子樹L，最后遍歷右子樹R。即在結(jié)點(diǎn)的前序序列中，第一個(gè)結(jié)點(diǎn)必是根D；而另一方面，由于中序遍歷是先遍歷左子樹L，然后訪問根D，最后遍歷右子樹R，則根結(jié)點(diǎn)D將中序序列分割成兩部分：在D之前是左子樹結(jié)點(diǎn)的中序序列，在D之后是右子樹結(jié)點(diǎn)的中序序列。反過來，根據(jù)左子樹的中序序列中結(jié)點(diǎn)個(gè)數(shù)，又可將前序序列除根以外分成左子樹的前序序列和右子樹的前序序列兩個(gè)部分。依次類推，便可遞歸得到整棵二叉樹 。,例：已知結(jié)點(diǎn)的前序序列和中序序列分別為： 前序序列：18 14 7 3 11 22 35 27 中序序列：3 7 11 14 18 22 27 35 則可按上述分解求得整棵二叉樹。,6.4 樹、森林和二叉樹的關(guān)系,6.4.1 樹的存儲(chǔ)結(jié)構(gòu) 6.4.2 樹、森林與二叉樹的相互轉(zhuǎn)換 6.4.3 樹與森林遍歷,6.4.1 樹的存儲(chǔ)結(jié)構(gòu),樹的主要存儲(chǔ)方法有： 1.雙親表示法 2.孩子表示法 3.孩子兄弟表示法,1. 雙親表示法：用一組連續(xù)的空間來存儲(chǔ)樹中的結(jié)點(diǎn)，在保存每個(gè)結(jié)點(diǎn)的同時(shí)附設(shè)一個(gè)指示器來指示其雙親結(jié)點(diǎn)在表中的位置，其結(jié)點(diǎn)的結(jié)構(gòu)如下：,樹的雙親表示法如下圖：,雙親表示法的優(yōu)點(diǎn)： 利用了樹中每個(gè)結(jié)點(diǎn)（根結(jié)點(diǎn)除外）只有一個(gè)雙親結(jié)點(diǎn)的性質(zhì)，使得查找某個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)非常容易。,雙親表示法的缺點(diǎn)： 在求某個(gè)結(jié)點(diǎn)的孩子時(shí)，需要遍歷整個(gè)向量。,雙親表示法的存儲(chǔ)結(jié)構(gòu),#define MAX 100 typedef struct TNode DataType data; int parent; TNode;,一棵樹可以定義為：,typedef struct TNode treeMAX; int nodenum; /*結(jié)點(diǎn)數(shù)*/ ParentTree;,2. 孩子表示法：通常是把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來，構(gòu)成一個(gè)單鏈表，稱為孩子鏈表。n個(gè)結(jié)點(diǎn)共有n個(gè)孩子鏈表（葉結(jié)點(diǎn)的孩子鏈表為空表），而n個(gè)結(jié)點(diǎn)的數(shù)據(jù)和n個(gè)孩子鏈表的頭指針又組成一個(gè)順序表。,r,孩子表示法的存儲(chǔ)結(jié)構(gòu)：,typedef struct ChildNode /* 孩子鏈表結(jié)點(diǎn)的定義 */ int Child; /* 該孩子結(jié)點(diǎn)在線性表中的位置 */ struct ChildNode * next; /*指向下一個(gè)孩子結(jié)點(diǎn)的指針 */ ChildNode; typedef struct /* 順序表結(jié)點(diǎn)的結(jié)構(gòu)定義 */ DataType data; /* 結(jié)點(diǎn)的信息 */ ChildNode * FirstChild ; /* 指向孩子鏈表的頭指針 */ DataNode; typedef struct /* 樹的定義 */ DataNode nodesMAX; /* 順序表 */ int root,num; /* 該樹的根結(jié)點(diǎn)在線性表中的位置和該樹的結(jié)點(diǎn)個(gè)數(shù) */ ChildTree;,3. 孩子兄弟表示法（二叉鏈表表示法）：鏈表中每個(gè)結(jié)點(diǎn)設(shè)有兩個(gè)鏈域，分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟（右兄弟）結(jié)點(diǎn)。,孩子兄弟表示法的存儲(chǔ)結(jié)構(gòu)：,typedef struct CSNode DataType data; /*結(jié)點(diǎn)信息*/ Struct CSNode *FirstChild, *Nextsibling; /*第一個(gè)孩子,下一個(gè)兄弟*/ CSNode, *CSTree;,優(yōu)點(diǎn)：便于實(shí)現(xiàn)樹的各種操作。,6.4.2 樹、森林與二叉樹的相互轉(zhuǎn)換,1. 樹轉(zhuǎn)換為二叉樹,我們約定樹中每一個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)按從左到右的次序順序編號(hào)，也就是說，把樹作為有序樹看待。,例如：右圖的樹,將一棵樹轉(zhuǎn)換為二叉樹的方法：, 樹中所有相鄰兄弟之間加一條連線。 對(duì)樹中的每個(gè)結(jié)點(diǎn)，只保留其與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去其與其它孩子結(jié)點(diǎn)之間的連線。 以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次分明。,結(jié)論：從轉(zhuǎn)換過程可看出：樹中的任意一個(gè)結(jié)點(diǎn)都對(duì)應(yīng)于二叉樹中的一個(gè)結(jié)點(diǎn)。樹中某結(jié)點(diǎn)的第一個(gè)孩子在二叉樹中是相應(yīng)結(jié)點(diǎn)的左孩子，樹中某結(jié)點(diǎn)的右兄弟結(jié)點(diǎn)在二叉樹中是相應(yīng)結(jié)點(diǎn)的右孩子。也就是說，在二叉樹中，左分支上的各結(jié)點(diǎn)在原來的樹中是父子關(guān)系，而右分支上的各結(jié)點(diǎn)在原來的樹中是兄弟關(guān)系。由于樹的根結(jié)點(diǎn)沒有兄弟，所以變換后的二叉樹的根結(jié)點(diǎn)的右孩子必然為空。,樹與二叉樹的對(duì)應(yīng)關(guān)系及轉(zhuǎn)換方法,2. 森林轉(zhuǎn)換為二叉樹,森林轉(zhuǎn)換為二叉樹的方法為：,（1）將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。 （2）第一棵二叉樹不動(dòng)，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。,森林轉(zhuǎn)換為二叉樹的過程,將森林F看作樹的有序集F=T1，T2，,TN，它對(duì)應(yīng)的二叉樹為B（F）：則有： （1）若N=0，則B（F）為空。 （2）若N0，二叉樹B（F）的根為森林中第一棵樹T1的根； B（F）的左子樹為B（T11，T1m），其中T11，T1m是T1的子樹森林；B（F）的右子樹是B（T2，TN）。 。,用遞歸的方法描述上述轉(zhuǎn)換過程：,3. 二叉樹還原為樹或森林,一棵二叉樹還原為樹或森林，具體方法為：,（1）若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子、都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連起來。 （2）刪掉原二叉樹中所有雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線。 （3）整理由（1）、（2）兩步所得到的樹或森林，使之結(jié)構(gòu)層次分明。,用遞歸的方法描述其轉(zhuǎn)換過程為：,若B是一棵二叉樹，T是B的根結(jié)點(diǎn)，L是B的左子樹，R為B的右子樹，且B對(duì)應(yīng)的森林F（B）中含有的n棵樹為T1,T2, ,Tn，則有：,（1）B為空，則F（B）為空的森林（n0）。,（2）B非空，則F（B）中第一棵樹T1的根為二叉樹B的根T；T1中根結(jié)點(diǎn)的子樹森林由B的左子樹L轉(zhuǎn)換而成，即F（L）=T11,T1m；B的右子樹R轉(zhuǎn)換為F（B）中其余樹組成的森林，即F(R) T2, T3, ,Tn。,6.4.3 樹與森林的遍歷,1. 樹的遍歷,樹的遍歷方法主要有以下兩種：,（1）先根遍歷,若樹非空，則遍歷方法為： 訪問根結(jié)點(diǎn)。 從左到右，依次先根遍歷根結(jié)點(diǎn)的每一棵子樹。,如圖中樹的先根遍歷序列為：ABECFHGD。,(2)后根遍歷,若樹非空，則遍歷方法為：,從左到右，依次后根遍歷根結(jié)點(diǎn)的每一棵子樹。 訪問根結(jié)點(diǎn)。,如圖中樹的后根遍歷序列為：EBHFGCDA。,樹的遍歷結(jié)果與由樹轉(zhuǎn)化成的二叉樹有如下對(duì)應(yīng)關(guān)系： 樹的先根遍歷 轉(zhuǎn)化二叉樹的前序遍歷 樹的后根遍歷 轉(zhuǎn)化二叉樹的中序遍歷,2.樹的遍歷算法實(shí)現(xiàn),void RootFirst(CSTree root) if (root!=NULL) Visit(root -data); /* 訪問根結(jié)點(diǎn) */ p= root- FirstChild; while (p!=NULL) RootFirst( p ); /* 訪問以p為根的子樹 */ p = p - Nextsibling; ,方法一,void RootFirst(CSTree root) if (root!=NULL) Visit (root -data); /*訪問根結(jié)點(diǎn)*/ RootFirst (root-FirstChild); /*先根遍歷首子樹*/ RootFirst (root-Nextsibling); /*先根遍歷兄弟樹*/ ,方法二,3. 森林的遍歷,森林的遍歷方法主要有以下三種：,(1)先序遍歷,若森林非空，則遍歷方法為：,訪問森林中第一棵樹的根結(jié)點(diǎn)。 先序遍歷第一棵樹的根結(jié)點(diǎn)的子樹森林。 先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。,(2)中序遍歷,若森林非空，則遍歷方法為：,中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林。 訪問第一棵樹的根結(jié)點(diǎn)。 中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。,(3)后序遍歷,若森林非空，則遍歷方法為：,后序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林。 后序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。 訪問第一棵樹的根結(jié)點(diǎn)。,6.5 哈夫曼樹及其應(yīng)用,6.5.1 哈夫曼樹 6.5.2 哈夫曼編碼,1. 哈夫曼樹的基本概念：,路徑：指從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支序列。 路徑長(zhǎng)度：指從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)所經(jīng)過的分支數(shù)目。 結(jié)點(diǎn)的權(quán)：給樹的每個(gè)結(jié)點(diǎn)賦予一個(gè)具有某種實(shí)際意義的實(shí)數(shù)，我們稱該實(shí)數(shù)為這個(gè)結(jié)點(diǎn)的權(quán)。 帶權(quán)路徑長(zhǎng)度：在樹形結(jié)構(gòu)中，我們把從樹根到某一結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積，叫做該結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度。 樹的帶權(quán)路徑長(zhǎng)度：為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，通常記為： 其中n為葉子結(jié)點(diǎn)的個(gè)數(shù)， wi為第i個(gè)葉子結(jié)點(diǎn)的權(quán)值，li為第i個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。,例如下圖所示的具有不同帶權(quán)路徑長(zhǎng)度的二叉樹,WPL(a)=7252224236 WPL(b)=4273532146 WPL(c)=7152234335,問題1：什么樣的二叉樹的路徑長(zhǎng)度PL最?。?一棵樹的路徑長(zhǎng)度為0結(jié)點(diǎn)至多只有1個(gè)（根）； 路徑長(zhǎng)度為1結(jié)點(diǎn)至多只有2個(gè)（兩個(gè)孩子）； 路徑長(zhǎng)度為2結(jié)點(diǎn)至多只有4個(gè)； 依此類推：路徑長(zhǎng)度為K結(jié)點(diǎn)至多只有2k個(gè)，所以n個(gè)結(jié)點(diǎn)二叉樹其路徑長(zhǎng)度至少等于如下序列的前n項(xiàng)之和。,路徑長(zhǎng)度 0 ，1 ， 1 ，2， 2， 2， 2，3， 3，3，3，3，3，3，3，4，4，. 結(jié)點(diǎn)數(shù)n n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 . K=15,由此可知，結(jié)點(diǎn)n對(duì)應(yīng)的路徑長(zhǎng)度為 log2n ，所以前n項(xiàng)之和為:,完全二叉樹的路徑長(zhǎng)度為：,h為樹的深度，其路徑長(zhǎng)度可達(dá)到最小，所以完全二叉樹具有最小路徑長(zhǎng)度的性質(zhì)，但不具有唯一性。,例如：下列不同形狀的二叉樹具有最小的路徑長(zhǎng)度,問題2：什么樣的帶權(quán)樹路徑長(zhǎng)度最??？,例如：給定一個(gè)權(quán)值序列2,3,4,7，可構(gòu)造的多種二叉樹的形態(tài)。,2. 構(gòu)造哈夫曼樹,哈夫曼樹又叫最優(yōu)二叉樹，它是由n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹中帶權(quán)路徑長(zhǎng)度WPL最短的二叉樹。,構(gòu)造哈夫曼算法的步驟如下：,(1)用給定的n個(gè)權(quán)值w1,w2, ,wn對(duì)應(yīng)的n個(gè)結(jié)點(diǎn)構(gòu)成n棵二叉樹的森林F=T1,T2, ,Tn，其中每一棵二叉樹Ti (1in)都只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn)，其左、右子樹為空。 (2)在森林F中選擇兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹，作為一棵新二叉樹的左、右子樹，標(biāo)記新二叉樹的根結(jié)點(diǎn)權(quán)值為其左右子樹的根結(jié)點(diǎn)權(quán)值之和。 (3)從F中刪除被選中的那兩棵二叉樹，同時(shí)把新構(gòu)成的二叉樹加入到森林F中。 (4)重復(fù)（2）、（3）操作，直到森林中只含有一棵二叉樹為止，此時(shí)得到的這棵二叉樹就是哈夫曼樹。,直觀地看，在哈夫曼樹中權(quán)越大的葉子離根越近，則其具有最小帶權(quán)路徑長(zhǎng)度。,哈夫曼樹的手工構(gòu)造的方法也非常簡(jiǎn)單：,給定數(shù)列W1.Wn，以n個(gè)權(quán)值構(gòu)成n棵樹的森林F；將F=T1.Tn按權(quán)從小到大排列； 取T1和T2合并組成一棵樹，使其根結(jié)點(diǎn)的權(quán)值T=T1+T2，再按大小插入F，反復(fù)此過程直到只有一棵樹為止。,3.哈夫曼樹的類型定義,(1)存儲(chǔ)結(jié)構(gòu) 哈夫曼樹是一種二叉樹 ,由于哈夫曼樹中沒有度為1的結(jié)點(diǎn)，則一棵有n個(gè)葉子的哈夫曼樹共有2n1個(gè)結(jié)點(diǎn)，可以用一個(gè)大小為2n1 的一維數(shù)組存放哈夫曼樹的各個(gè)結(jié)點(diǎn)。由于每個(gè)結(jié)點(diǎn)同時(shí)還包含其雙親信息和孩子結(jié)點(diǎn)的信息，所以構(gòu)成一個(gè)靜態(tài)三叉鏈表。,靜態(tài)三叉鏈表中：每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)為 :,各結(jié)點(diǎn)存儲(chǔ)在一維數(shù)組中，0號(hào)單元不使用，從1號(hào)位置開始使用。,(2)哈夫曼樹的類型定義,用靜態(tài)三叉鏈表實(shí)現(xiàn)的哈夫曼樹類型定義如下： #define N 20 /* 葉子結(jié)點(diǎn)的最大值。*/ #define M 2*N-1 /* 所有結(jié)點(diǎn)的最大值*/ typedef struct int weight ; /* 結(jié)點(diǎn)的權(quán)值*/ int parent ; /* 雙親的下標(biāo)*/ int LChild ; /* 左孩子結(jié)點(diǎn)的下標(biāo)*/ int RChild ; /* 右孩子結(jié)點(diǎn)的下標(biāo)*/ HTNode, HuffmanTreeM+1; /* HuffmanTree是一個(gè)結(jié)構(gòu)數(shù)組類型，0號(hào)單元不用。 */,4. 哈夫曼樹的算法實(shí)現(xiàn),【算法描述】 void CrtHuffmanTree(HuffmanTree ht, int w , int n) /*構(gòu)造哈夫曼樹htM+1， w 存放n個(gè)權(quán)值。*/ for(i=1;i<=n;i+) hti = wi,0,0,0; /* 1 n號(hào)單元存放葉子結(jié)點(diǎn)，初始化*/ m=2*n-1; for(i=n+1;i<=m;i+) hti =0,0,0,0; /*初始化完畢！對(duì)應(yīng)算法步驟1*/ for(i=n+1; i<=m; i+) /*創(chuàng)建非葉結(jié)點(diǎn)，建哈夫曼樹*/ select(ht, i-1, s1, s2); /* 在 ht1 hti-1 的范圍內(nèi)選擇兩個(gè)parent為0且 weight最小的結(jié)點(diǎn)，其序號(hào)分別賦值給s1、s2返回 */ ht i.weight= ht s1.weight+ ht s2.weight; ht s1.parent=i; ht s2.parent=i; ht i.LChild=s1; ht i.RChild=s2; /*哈夫曼樹建立完畢*/ ,例：傳送數(shù)據(jù)中的二進(jìn)制編碼。要傳送數(shù)據(jù)state,seat,act,tea,cat,set,a,eat，如何使傳送的長(zhǎng)度最短？,為了保證長(zhǎng)度最短，先計(jì)算各個(gè)字符出現(xiàn)的次數(shù)，然后將出現(xiàn)次數(shù)當(dāng)作權(quán)。,字符 s t a e c 字符出現(xiàn)的次數(shù) 3 8 7 5 2,按權(quán)構(gòu)造哈夫曼樹的過程如下圖：,按照創(chuàng)建哈夫曼樹的算法，對(duì)上圖建立哈夫曼樹的結(jié)果如下表：,6.5.2 哈夫曼編碼,哈夫曼樹最典型的應(yīng)用是在編碼技術(shù)上的應(yīng)用。利用哈夫曼樹，我們可以得到平均長(zhǎng)度最短的編碼。,例如：設(shè)有一臺(tái)模型機(jī)，共有7種不同的指令，其使用頻率為：,變長(zhǎng)編碼為：,1.哈夫曼編碼的概念,(1)前綴碼：如果在一個(gè)編碼系統(tǒng)中，任一個(gè)編碼都不是其他任何編碼的前綴（最左子串），則稱該編碼系統(tǒng)中的編碼是前綴碼。例如，一組編碼01，001，010，100，110就不是前綴碼，因?yàn)?1是010的前綴，若去掉01或010就是前綴碼。例如，名字中的鄭霞、鄭霞錦就不是前綴碼。 (2)哈夫曼編碼：對(duì)一棵具有n個(gè)葉子的哈夫曼樹，若對(duì)樹中的每個(gè)左分支賦予0，右分支賦予1，則從根到每個(gè)葉子的通路上，各分支的賦值分別構(gòu)成一個(gè)二進(jìn)制串，該二進(jìn)制串就稱為哈夫曼編碼。,定理6-1 哈夫曼編碼是前綴碼。 證明：哈夫曼編碼是根到葉子路徑上的邊的編碼的序列，也就是等價(jià)邊序列，而由樹的特點(diǎn)知，若路徑A是另一條路經(jīng)B的最左部分，則B經(jīng)過了A，因此，A的終點(diǎn)不是葉子。而哈夫曼編碼都對(duì)應(yīng)終點(diǎn)為葉子的路徑，所以，任一哈夫曼碼都不會(huì)與任意其他哈夫曼編碼的前部分完全重疊，因此哈夫曼編碼是前綴碼。,定理