1、第7章 樹和二叉樹,樹 二叉樹 以結(jié)點(diǎn)類為基礎(chǔ)的二叉樹設(shè)計(jì) 二叉樹類 二叉樹的分步遍歷 線索二叉樹 哈夫曼樹 樹與二叉樹的轉(zhuǎn)換 樹的遍歷,主要知識(shí)點(diǎn),7.1 樹,1.樹的定義,樹是由n(n0)個(gè)結(jié)點(diǎn)組成的有限集合T。n=0的樹稱為空樹；對(duì)n0的樹，有:(1)僅有一個(gè)特殊的結(jié)點(diǎn)稱為根結(jié)點(diǎn)，根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)；(2)當(dāng)n1時(shí)，除根結(jié)點(diǎn)外其余的結(jié)點(diǎn)分為m(m0)個(gè)互不相交的有限集合T1,T2，Tm，其中每個(gè)集合Ti本身又是一棵結(jié)構(gòu)和樹類似的子樹。,注：樹的定義具有遞歸性，即“樹中還有樹”。,若干術(shù)語,結(jié)點(diǎn)：由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之 間關(guān)系的指針組成,結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù),葉結(jié)點(diǎn)：度為0

2、的結(jié)點(diǎn)，也稱作 終端結(jié)點(diǎn),分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn),孩子結(jié)點(diǎn)：樹中一個(gè)結(jié)點(diǎn)的子樹的根結(jié)點(diǎn),雙親結(jié)點(diǎn)：若樹中某結(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),樹的度：樹中所有結(jié)點(diǎn)的度的最大值,結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)到樹中某結(jié)點(diǎn)所經(jīng)路徑上的分支數(shù),樹的深度：樹中所有結(jié)點(diǎn)的層次的最大值,無序樹：樹中任意一個(gè)結(jié)點(diǎn)的各孩子結(jié)點(diǎn)之間的次序 構(gòu)成無關(guān)緊要的樹,有序樹：樹中任意一個(gè)結(jié)點(diǎn)的各孩子結(jié)點(diǎn)有嚴(yán)格排列 次序的樹,森林：m（m0）棵樹的集合,2.樹的表示方法,(1)直觀表示法,(2)形式化表示法,(3)凹入表示法,3.樹的抽象數(shù)據(jù)類型,數(shù)據(jù)集合: 樹的結(jié)點(diǎn)集合，

3、每個(gè)結(jié)點(diǎn)由數(shù)據(jù)元素和構(gòu)造數(shù) 據(jù)元素之間關(guān)系的指針組成。 操作集合: (1)創(chuàng)建樹MakeTree(T) (2)撤消樹DestroyTree(T) (3)查找樹中當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)Parent(T,curr) (4)查找樹中當(dāng)前結(jié)點(diǎn)的左孩子結(jié)點(diǎn)LeftChild(T,curr) (5)查找樹中當(dāng)前結(jié)點(diǎn)的右兄弟結(jié)點(diǎn)RightSibling(T,curr) (6)遍歷樹Traverse(T,Visit( ),4.樹的存儲(chǔ)結(jié)構(gòu),樹的結(jié)點(diǎn)之間的邏輯關(guān)系主要有雙親-孩子關(guān)系，兄弟關(guān)系。因此，從結(jié)點(diǎn)之間的邏輯關(guān)系分，樹的存儲(chǔ)結(jié)構(gòu)主要有：雙親表示法、孩子表示法、雙親孩子表示法和孩子兄弟表示法四種組合。,(1)

4、雙親表示法,(a)一棵樹,（b)仿真指針的雙親表示法存儲(chǔ)結(jié)構(gòu),樹及其使用仿真指針的雙親表示法,(2)孩子表示法,雙親孩子表示法,(3)雙親孩子表示法,(4)孩子兄弟表示法,常規(guī)指針的孩子兄弟表示法,7.2 二叉樹,一、二叉樹：是n(n0)個(gè)結(jié)點(diǎn)的有限集合。n=0的樹稱為空二叉樹；n0的二叉樹由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成 。 邏輯結(jié)構(gòu)： 一對(duì)二（1:2） 基本特征: 每個(gè)結(jié)點(diǎn)最多只有兩棵子樹（不存在度大于2的結(jié)點(diǎn)）； 左子樹和右子樹次序不能顛倒。所以下面是兩棵不同的樹,1.二叉樹的定義,二、滿二叉樹：在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左 子樹和右子樹，并

5、且所有葉子結(jié)點(diǎn)都在同一層上，這樣的 二叉樹稱為滿二叉樹。 三、完全二叉樹：如果一棵深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹中各 結(jié)點(diǎn)能夠與深度為k的順序編號(hào)的滿二叉樹從1到n標(biāo)號(hào)的 結(jié)點(diǎn)相對(duì)應(yīng)的二叉樹稱為完全二叉樹。如下圖所示,(a)滿二叉樹,(b)完全二叉樹,數(shù)據(jù)集合：二叉樹的結(jié)點(diǎn)集合，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之間關(guān)系的指針組成。 操作集合： (1)創(chuàng)建二叉樹 MakeTree(T) (2)撤消二叉樹 DestroyTree(T) (3)左插入結(jié)點(diǎn) InsertLeftNode(curr,x) (4)右插入結(jié)點(diǎn) InsertRightNode(curr,x) (5)左刪除子樹 DeleteLef

6、tTree(curr) (6)右刪除子樹 DeleteRightTree(curr) (7)遍歷二叉樹 Traverse(T,Visit(),2.二叉樹抽象數(shù)據(jù)類型,3.二叉樹的性質(zhì),性質(zhì)1:在一棵非空二叉樹的第i層上至多有2i個(gè)結(jié)點(diǎn)（i0）。,性質(zhì)2:深度為k的二叉樹至多有2k+1-1個(gè)結(jié)點(diǎn)(k-1)。,性質(zhì)3: 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度k為不超過log2(n+1)-1的最大整數(shù)。,證明：根據(jù)性質(zhì)2，對(duì)于有n個(gè)接點(diǎn)的深度為k的完全二叉樹有 2k-1n2k+1-1，移項(xiàng)，有 2kn+12k+1 對(duì)不等式求對(duì)數(shù)，有klog2(n+1)k+1，因?yàn)閗必須是整數(shù)，所以k=log2(n+1)-1

7、,性質(zhì)4:對(duì)于一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹，按照從上至下和從左至右的順序?qū)λ薪Y(jié)點(diǎn)從0開始順序編號(hào),則對(duì)于序號(hào)為i的結(jié)點(diǎn)(0in),有： (1)如果i0，則其雙親是結(jié)點(diǎn)(i-1)/2(“/”表示整除） ；如果i=0，則結(jié)點(diǎn)I是根結(jié)點(diǎn)，無雙親。 (2)如果2i+1n ，其左孩子是結(jié)點(diǎn)2i+1；如果2i+1n，則結(jié)點(diǎn)i無左孩子。 (3)如果2i2n，其右孩子是結(jié)點(diǎn)2i2；如果2i2n，則結(jié)點(diǎn)i無右孩子。,二叉樹的存儲(chǔ)結(jié)構(gòu)主要有三種：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié) 構(gòu)和仿真指針存儲(chǔ)結(jié)構(gòu)。 (1) 二叉樹的順序存儲(chǔ)結(jié)構(gòu) 完全二叉樹的結(jié)點(diǎn)可按從上至下和從左至右的次序存儲(chǔ)在一維數(shù)組中，其結(jié)點(diǎn)之間的關(guān)系可由公式計(jì)算

8、得到，這就是二叉樹的順序存儲(chǔ)結(jié)構(gòu)。下面兩棵樹在數(shù)組中的存儲(chǔ)結(jié)構(gòu)分別為：,4.二叉樹的存儲(chǔ)結(jié)構(gòu),對(duì)于一般的非完全二叉樹顯然不能直接使用二叉樹的順序存儲(chǔ)結(jié)構(gòu)?？梢允紫仍诜峭耆鏄渲性鎏硪恍┎⒉淮嬖诘目战Y(jié)點(diǎn)使之變成完全二叉樹的形態(tài)，然后再用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。,(a)一般二叉樹,(b)完全二叉樹形態(tài),(c) 在數(shù)組中的存儲(chǔ)形式,(2) 二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用指針建立二叉樹中結(jié)點(diǎn)之間的關(guān)系。二叉樹最常用的的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是二叉鏈。二叉鏈存儲(chǔ)結(jié)構(gòu)的每個(gè)結(jié)點(diǎn)包含三個(gè)域，分別是數(shù)據(jù)域data、左孩子指針域leftChild和右孩子指針域rightChild。二叉鏈存儲(chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)的圖

9、示結(jié)構(gòu)為：,二叉鏈存儲(chǔ)結(jié)構(gòu)的二叉樹也有不帶頭結(jié)點(diǎn)和帶頭結(jié)點(diǎn)兩種。帶頭結(jié)點(diǎn)的二叉鏈存儲(chǔ)結(jié)構(gòu)的二叉樹見下圖(b)，不帶頭結(jié)點(diǎn)的二叉鏈存儲(chǔ)結(jié)構(gòu)的二叉樹如下圖(a)所示。,圖7-10 二叉鏈存儲(chǔ)結(jié)構(gòu)的二叉樹,(a)不帶頭結(jié)點(diǎn)的二叉樹,(b)帶頭結(jié)點(diǎn)的二叉樹,(3)二叉樹的仿真指針 二叉樹的仿真指針存儲(chǔ)結(jié)構(gòu)是用數(shù)組存儲(chǔ)二叉樹中的結(jié)點(diǎn)，數(shù)組中每個(gè)結(jié)點(diǎn)除數(shù)據(jù)元素域外，再增加仿真指針域用于仿真常規(guī)指針建立二叉樹中結(jié)點(diǎn)之間的關(guān)系。,二叉樹的仿真二叉鏈存儲(chǔ)結(jié)構(gòu),7.3 以結(jié)點(diǎn)類為基礎(chǔ)的二叉樹設(shè)計(jì),二叉樹的實(shí)現(xiàn)有兩種基本方法：一種方法是首先設(shè)計(jì)二叉樹結(jié)點(diǎn)類，然后在二叉樹結(jié)點(diǎn)類的基礎(chǔ)上，用結(jié)點(diǎn)類的外部函數(shù)實(shí)現(xiàn)二叉樹的

10、操作；另一種方法是在二叉樹結(jié)點(diǎn)類的基礎(chǔ)上，再設(shè)計(jì)二叉樹類。,1.二叉樹的結(jié)點(diǎn)類,模板形式的二叉樹結(jié)點(diǎn)類定義和實(shí)現(xiàn)代碼如下：,template class BiTreeNode private: BiTreeNode *leftChild;/左子樹指針 BiTreeNode *rightChild;/右子樹指針 public: T data; /數(shù)據(jù)域 BiTreeNode():leftChild(NULL), rightChild(NULL) BiTreeNode(T item, BiTreeNode *left = NULL, BiTreeNode *right = NULL): data(

11、item), leftChild(left), rightChild(right) BiTreeNode(),BiTreeNode* 設(shè)計(jì)說明： （1）成員變量通常設(shè)計(jì)成私有訪問權(quán)限，但考慮到外部函數(shù)要頻繁使用結(jié)點(diǎn)類中的成員變量，所以這里成員變量data設(shè)計(jì)成公有訪問權(quán)限。 （2）二叉樹也有帶頭結(jié)點(diǎn)（或稱根結(jié)點(diǎn)）和不帶頭結(jié)點(diǎn)兩種情況。這里設(shè)計(jì)了兩個(gè)構(gòu)造函數(shù)，第一個(gè)可用于帶頭結(jié)點(diǎn)結(jié)構(gòu)中頭結(jié)點(diǎn)對(duì)象的定義，第二個(gè)用于常規(guī)結(jié)點(diǎn)對(duì)象的定義。 （3）訪問指針域的成員函數(shù)Left ()和Right()的返回值類型設(shè)計(jì)為指針的引用類型是十分必要的，引用類型變量意味著相應(yīng)的變量是同一個(gè)變量，這使得這兩個(gè)函數(shù)不僅

12、可以位于賦值號(hào)的左邊，而且還可以位于賦值號(hào)的右邊。,由結(jié)點(diǎn)構(gòu)造二叉樹的基本函數(shù)： template BiTreeNode *GetTreeNode(const T item, BiTreeNode *left = NULL, BiTreeNode *right = NULL) BiTreeNode *p; p = new BiTreeNode (item, left, right); return p; ,2.二叉樹的遍歷,(1)二叉樹遍歷的基本方法,從二叉樹的定義知，一棵二叉樹由三部分組成：根結(jié)點(diǎn)、左子樹和右子樹。若規(guī)定D,L,R分別代表“訪問根結(jié)點(diǎn)”、“遍歷根結(jié)點(diǎn)的左子樹”和“遍歷根結(jié)點(diǎn)的

13、右子樹”，根據(jù)遍歷算法對(duì)訪問根結(jié)點(diǎn)處理的位置，稱下面三種遍歷算法分別為前序遍歷（DLR）、中序遍歷（LDR）和后序遍歷（LRD）。,前序遍歷（DLR）遞歸算法為： 若二叉樹為空則算法結(jié)束；否則： （1）訪問根結(jié)點(diǎn)； （2）前序遍歷根結(jié)點(diǎn)的左子樹； （3）前序遍歷根結(jié)點(diǎn)的右子樹。,中序遍歷（LDR）遞歸算法為： 若二叉樹為空則算法結(jié)束；否則： （1）中序遍歷根結(jié)點(diǎn)的左子樹； （2）訪問根結(jié)點(diǎn)； （3）中序遍歷根結(jié)點(diǎn)的右子樹。 后序遍歷（LRD）遞歸算法為： 若二叉樹為空則算法結(jié)束；否則： （1）后序遍歷根結(jié)點(diǎn)的左子樹； （2）后序遍歷根結(jié)點(diǎn)的右子樹； （3）訪問根結(jié)點(diǎn)。,此外，二叉樹還有層序遍歷

14、。層序遍歷的要求是：按二叉樹的層序次序（即從根結(jié)點(diǎn)層至葉結(jié)點(diǎn)層），同一層中按先左子樹再右子樹的次序遍歷二叉樹。 它的特點(diǎn)是，在所有未被訪問結(jié)點(diǎn)的集合中，排列在已訪問結(jié)點(diǎn)集合中最前面結(jié)點(diǎn)的左子樹的根結(jié)點(diǎn)將最先被訪問，然后是該結(jié)點(diǎn)的右子樹的根結(jié)點(diǎn)。這樣，如果把已訪問的結(jié)點(diǎn)放在一個(gè)隊(duì)列中，那么，所有未被訪問結(jié)點(diǎn)的訪問次序就可以由存放在隊(duì)列中的已訪問結(jié)點(diǎn)的出隊(duì)列次序決定。因此可以借助隊(duì)列實(shí)現(xiàn)二叉樹的層序遍歷。,當(dāng)對(duì)一個(gè)二叉樹用一種特定的遍歷方法來遍歷時(shí)，其遍歷序列一定是線性的，且是惟一的。,二叉樹的層序遍歷算法如下： （1）初始化設(shè)置一個(gè)隊(duì)列； （2）把根結(jié)點(diǎn)指針入隊(duì)列； （3）當(dāng)隊(duì)列非空時(shí)，循環(huán)執(zhí)行

15、步驟（3.a）到步驟（3.c）； （3.a）出隊(duì)列取得一個(gè)結(jié)點(diǎn)指針，訪問該結(jié)點(diǎn)； （3.b）若該結(jié)點(diǎn)的左子樹非空，則將該結(jié)點(diǎn)的左子樹指針入隊(duì)列； （3.c）若該結(jié)點(diǎn)的右子樹非空，則將該結(jié)點(diǎn)的右子樹指針入隊(duì)列； （4）結(jié)束。,(2)二叉樹的遍歷方法和二叉樹的結(jié)構(gòu) 二叉樹是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)會(huì)有零個(gè)、一個(gè)或兩個(gè)孩子結(jié)點(diǎn)，一個(gè)二叉樹的遍歷序列不能決定一棵二叉樹，但某些不同的遍歷序列組合可以惟一確定一棵二叉樹。可以證明，給定一棵二叉樹的前序遍歷序列和中序遍歷序列可以惟一確定一棵二叉樹的結(jié)構(gòu)。,(3)二叉樹遍歷的實(shí)現(xiàn) template void PreOrder(BiTreeNode *t, void

16、 Visit(T item) /使用Visit(item)函數(shù)前序遍歷二叉樹t if(t != NULL) Visit(t-data); PreOrder(t-Left(), Visit); PreOrder(t-Right(), Visit); 為了通用性，把訪問操作設(shè)計(jì)成前序遍歷二叉樹函數(shù)的一個(gè)函數(shù)虛參 Visit()。,template void InOrder(BiTreeNode *t, void Visit(T item) /使用Visit(item)函數(shù)中序遍歷二叉樹t if(t != NULL) InOrder(t-Left(), Visit); Visit(t-data);

17、InOrder(t-Right(), Visit); template void PostOrder(BiTreeNode *t, void Visit(T item) /使用Visit(item)函數(shù)后序遍歷二叉樹t if(t != NULL) PostOrder(t-Left(), Visit); PostOrder(t-Right(), Visit); Visit(t-data); ,3.二叉樹遍歷的應(yīng)用,(1)二叉樹的撤消操作 在釋放某個(gè)結(jié)點(diǎn)的存儲(chǔ)空間前必須先釋放該結(jié)點(diǎn)左孩子結(jié)點(diǎn)的存儲(chǔ)空間和右孩子結(jié)點(diǎn)的存儲(chǔ)空間，因此，二叉樹撤消操作必須是后序遍歷的具體應(yīng)用。撤消操作函數(shù)實(shí)現(xiàn)如下： te

18、mplate void Destroy(BiTreeNode * ,(2) 打印二叉樹 把二叉樹逆時(shí)針旋轉(zhuǎn)900C，按照二叉樹的凹入表示法打印二叉樹?？砂汛撕瘮?shù)設(shè)計(jì)成遞歸函數(shù)。由于把二叉樹逆時(shí)針旋轉(zhuǎn)900C后，在屏幕上方的首先是右子樹，然后是根結(jié)點(diǎn)，最后是左子樹，所以打印二叉樹算法是一種特殊的中序遍歷算法。 template void PrintBiTree(BiTreeNode* ,(3)查找數(shù)據(jù)元素 在二叉樹中查找數(shù)據(jù)元素操作的要求是：在bt為根結(jié)點(diǎn)指針的二叉樹中查找數(shù)據(jù)元素x，若查找到數(shù)據(jù)元素x時(shí)返回該結(jié)點(diǎn)的指針；若查找不到數(shù)據(jù)元素x時(shí)返回空指針。 在二叉樹bt中查找數(shù)據(jù)元素x函數(shù)可設(shè)計(jì)成先序遍歷函數(shù)，此時(shí)查找結(jié)點(diǎn)的次序是：首先在根結(jié)點(diǎn)查找，然后在左子樹查找，最后在右子樹查找。但是，和常規(guī)遞歸算法不同的是，此函數(shù)當(dāng)一個(gè)分支上的結(jié)點(diǎn)比較完仍未查找到數(shù)據(jù)元素x時(shí)，要返回到該結(jié)點(diǎn)的雙親結(jié)點(diǎn)處繼續(xù)查找。因此，這是回溯算法的一個(gè)應(yīng)用。 實(shí)現(xiàn)如下：,template BiTreeNode *Search(BiTreeNode *t, T x) BiTreeNode *p;if(t = NULL) return NULL;/空二叉樹時(shí)的查找失敗出口if(t-data = x) return t;/查找成功出口if(t-Left()