數(shù)據(jù)結(jié)構(gòu)樹型結(jié)構(gòu)

1、數(shù)據(jù)結(jié)構(gòu)樹型結(jié)構(gòu),學(xué)習(xí)要點(diǎn),熟練掌握二叉樹的結(jié)構(gòu)特性，了解相應(yīng)的證明方法。 建立存儲(chǔ)結(jié)構(gòu)是進(jìn)行操作的前提。故須熟悉二叉樹的各種存儲(chǔ)結(jié)構(gòu)、并把握各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍。 遍歷二叉樹是二叉樹各種操作的基礎(chǔ)。實(shí)現(xiàn)二叉樹遍歷的具體算法與所采用的存儲(chǔ)結(jié)構(gòu)有關(guān)。掌握各種遍歷策略的遞歸算法，靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其他操作。理解包括層次遍歷在內(nèi)的各種非遞歸遍歷的算法。 理解二叉樹線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系，熟練掌握二叉樹的線索化過程以及在中序線索化二叉樹上找到給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。二叉樹的線索化過程是基于對二叉樹進(jìn)行遍歷，而線索二叉樹上的線索又為相應(yīng)的遍

2、歷提供了方便。 熟悉樹的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹和森林與二叉樹的轉(zhuǎn)換方法。 學(xué)會(huì)編寫實(shí)現(xiàn)樹的各種操作的算法。 理解等價(jià)關(guān)系和等價(jià)類問題。 了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和赫夫曼編碼的方法。,樹型結(jié)構(gòu),樹型結(jié)構(gòu)是一種典型的分支結(jié)構(gòu)，并且具有明顯的層次特征。 樹型結(jié)構(gòu)在客觀世界中是廣泛存在的，如家族譜、組織機(jī)構(gòu)、博弈等都可用樹型結(jié)構(gòu)形象地表示。 樹型結(jié)構(gòu)在計(jì)算機(jī)領(lǐng)域中也有著廣泛的應(yīng)用：編譯程序、數(shù)據(jù)庫系統(tǒng)、分析算法,1 樹、森林的定義及基本術(shù)語,樹(tree)是n ( )個(gè)結(jié)點(diǎn)的有限集t，當(dāng)n=0時(shí)稱為空樹，否則滿足以下兩個(gè)條件： 有且僅有一個(gè)特定的結(jié)點(diǎn)，稱為樹的根(root) 其余結(jié)點(diǎn)可分

3、為m( )個(gè)互不相交的子集t1,t2,tm，其中每一個(gè)子集本身又是一棵樹，并稱其為根結(jié)點(diǎn)的子樹(subtree),1 樹、森林的定義及基本術(shù)語,森林是m（m0）棵互不相交的樹的集合。 用森林的定義也可定義樹：一棵非空的樹由根結(jié)點(diǎn)及其子樹森林所構(gòu)成。 樹和森林均為典型的樹型結(jié)構(gòu)，從形態(tài)上看，樹結(jié)構(gòu)類似于自然界倒長的一棵樹,1樹、森林的定義及基本術(shù)語,基本術(shù)語 結(jié)點(diǎn)：包含了數(shù)據(jù)元素及若干個(gè)指向其子樹的分支。 結(jié)點(diǎn)的度：結(jié)點(diǎn)的子樹數(shù)目或分支個(gè)數(shù)。 樹的度：在樹中取各結(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)所

4、經(jīng)分支和結(jié)點(diǎn)構(gòu)成結(jié)點(diǎn)的路徑。 結(jié)點(diǎn)的路徑長度：根結(jié)點(diǎn)到該結(jié)點(diǎn)路徑上所經(jīng)分支的數(shù)目。,1樹、森林的定義及基本術(shù)語,基本術(shù)語 結(jié)點(diǎn)的層次：設(shè)根結(jié)點(diǎn)的層次為1，則其子樹的根結(jié)點(diǎn)層次為2；第l 層結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)層次為l+1。 樹的深度：樹中結(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)又稱為孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)。 兄弟結(jié)點(diǎn)：擁有同一個(gè)雙親結(jié)點(diǎn)的若干個(gè)結(jié)點(diǎn)互稱為兄弟結(jié)點(diǎn)。 堂兄弟結(jié)點(diǎn)：在同一層次上，但雙親結(jié)點(diǎn)不同的若干個(gè)結(jié)點(diǎn)稱為堂兄弟結(jié)點(diǎn)。,1樹、森林的定義及基本術(shù)語,基本術(shù)語 祖先結(jié)點(diǎn)：根結(jié)點(diǎn)到該結(jié)點(diǎn)路徑上的所有結(jié)點(diǎn)均為該結(jié)點(diǎn)的祖先結(jié)點(diǎn)。

5、子孫結(jié)點(diǎn)：某結(jié)點(diǎn)的子樹中所包含的所有結(jié)點(diǎn)均為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)。 無序樹：子樹之間不存在次序關(guān)系，即子樹能夠調(diào)換，則稱該樹為無序樹。 有序樹：子樹之間映射客觀存在的次序關(guān)系（子樹不能調(diào)換），則稱該樹為有序樹。,線性結(jié)構(gòu)和樹型結(jié)構(gòu)的比較,2 二叉樹,2.1 二叉樹的結(jié)構(gòu)定義 二叉樹定義 二叉樹是n（n0）個(gè)結(jié)點(diǎn)的有限集，當(dāng)n=0時(shí)，二叉樹為空；當(dāng)n0時(shí)，二叉樹由一個(gè)根結(jié)點(diǎn)及至多兩棵互不相交的左右子樹組成，且左右子樹都是二叉樹。 二叉樹特點(diǎn) 每個(gè)結(jié)點(diǎn)至多有二棵子樹(即不存在度大于2的結(jié)點(diǎn)) 二叉樹的子樹有左、右之分，且其次序不能任意顛倒,2.1 二叉樹的結(jié)構(gòu)定義,二叉樹的基本形態(tài),空二叉樹,只有根結(jié)

6、點(diǎn)的二叉樹,右子樹為空,左子樹為空,左右子樹均非空,2.2 幾種特殊形態(tài)的二叉樹,滿二叉樹：一棵深度為k的二叉樹若每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大則稱其為滿二叉樹。 完全二叉樹：一棵具有n個(gè)結(jié)點(diǎn)且深度為k的二叉樹若前 k1層的結(jié)點(diǎn)數(shù)都達(dá)到最大，剩余的結(jié)點(diǎn)在第k層中從左至右連續(xù)分布則稱其為完全二叉樹。 擬滿二叉樹：一棵具有n個(gè)結(jié)點(diǎn)且深度為k的二叉樹若前 k1層的結(jié)點(diǎn)數(shù)都達(dá)到最大，剩余的結(jié)點(diǎn)在第k層中隨機(jī)分布則稱其為擬滿二叉樹。 正則二叉樹：在一棵二叉樹中，如果只存在度為0和度為2的結(jié)點(diǎn)則稱其為正則二叉樹。 平衡二叉樹：在一棵二叉樹中，若其任一子樹型均滿足：|左子樹的深度右子樹的深度|1，則稱其為平衡二

7、叉樹。,2.2 幾種特殊形態(tài)的二叉樹,2.3 二叉樹的性質(zhì),二叉樹性質(zhì)1 在二叉樹的第 i 層上至多有2i-1 個(gè)結(jié)點(diǎn)。 (i1) 證明：用歸納法證明之 i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，2i-1 = 20 = 1；是對的 假設(shè)對所有j(1 ji)命題成立，即第j層上至多有2j-1 個(gè)結(jié)點(diǎn)，那么，第i-1層至多有2i-2 個(gè)結(jié)點(diǎn)又二叉樹每個(gè)結(jié)點(diǎn)的度至多為2，第i層上最大結(jié)點(diǎn)數(shù)是第i-1層的2倍，即2i-2 * 2 = 2i-1 故命題得證,2.3 二叉樹的性質(zhì),二叉樹性質(zhì)2 深度為 k 的二叉樹上至多含 2k-1 個(gè)結(jié)點(diǎn)（k1）。 證明基于上一條性質(zhì)，深度為 k 的二叉樹上的結(jié)點(diǎn)數(shù)至多為20+21+

8、+2k-1 = 2k-1 。,2.3 二叉樹的性質(zhì),二叉樹性質(zhì)3 對任何一棵二叉樹，若它含有n0 個(gè)葉子結(jié)點(diǎn)、n2 個(gè)度為 2 的結(jié)點(diǎn)，則必存在關(guān)系式：n0 = n2+1。 證明：設(shè)n1 為二叉樹中度為1的結(jié)點(diǎn)數(shù)，二叉樹上結(jié)點(diǎn)總數(shù) n = n0 + n1 + n2 ，又二叉樹上分支總數(shù) b = n1 +2 n2 ，而 b = n-1 = n0 + n1 + n2 - 1，由此， n0 = n2 + 1 。,一棵完全二叉樹的例子,2.3 二叉樹的性質(zhì),二叉樹性質(zhì)4 具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 +1 證明設(shè)完全二叉樹的深度為 k 則根據(jù)第二條性質(zhì)得 2k-1 n 2k 即 k-1 log

9、2 n k因?yàn)?k 只能是整數(shù)，因此， k = + 1 。,2.3 二叉樹的性質(zhì),二叉樹性質(zhì)5 若對含 n 個(gè)結(jié)點(diǎn)的完全二叉樹從上到下且從左至右 進(jìn)行 1 至 n 的編號，則對完全二叉樹中任意一個(gè)編號為 i 的結(jié)點(diǎn)： 若 i=1，則該結(jié)點(diǎn)是二叉樹的根，無雙親，否則，編號 為i/2 的結(jié)點(diǎn)為其雙親結(jié)點(diǎn)； 若 2in，則該結(jié)點(diǎn)無左孩子，否則，編號為 2i 的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)； 若 2i+1n，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)，否則，編號為2i+1 的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。,2.3 二叉樹的性質(zhì),用歸納法證明如下： 當(dāng)i=1 時(shí)，由完全二叉樹的定義及編號規(guī)則可知，i 結(jié)點(diǎn)是二叉樹的根，其左孩子若存在編號是2 即

10、2i，右孩子若存在編號是3 即2i+1，性質(zhì)成立。 設(shè)編號為i-1 的結(jié)點(diǎn)其左孩子若存在編號是2(i-1)，右孩子若存在編號是2(i-1) +1 性質(zhì)成立。 由完全二叉樹的定義及編號規(guī)則可知，對于第i 個(gè)結(jié)點(diǎn)，其左孩子若存在，編號必為編號為i-1 的那個(gè)結(jié)點(diǎn)的左孩子位序加2，即2(i-1)+2=2i；右孩子若存在，編號必為編號為i-1 的那個(gè)結(jié)點(diǎn)的右孩子位序加2，即2(i-1) +1+2=2 i+1，故和成立。 性質(zhì)得證。,2.4 二叉樹的存儲(chǔ)結(jié)構(gòu),順序存儲(chǔ)結(jié)構(gòu) 特點(diǎn) 結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中 浪費(fèi)空間，適于存滿二叉樹和完全二叉樹 實(shí)現(xiàn)：按滿二叉樹的結(jié)點(diǎn)層次編號，依次存放二叉樹中的數(shù)據(jù)元素

11、,const maxsize=100; / 暫定二叉樹中結(jié)點(diǎn)數(shù)的最大值為100 struct sqbitree elemtype *base; /存儲(chǔ)空間基址 int nodenum; /二叉樹中結(jié)點(diǎn)數(shù) ;,二叉樹的存儲(chǔ)結(jié)構(gòu)(順序存儲(chǔ)),2.4 二叉樹的存儲(chǔ)結(jié)構(gòu),二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 二叉鏈表,/ btnode.h，二叉鏈表結(jié)點(diǎn)結(jié)構(gòu) template struct btnode elemtype data; btnode *lchild , *rchild ; ;,lchild,data,rchild,二叉鏈表例,a,b,c,d,e,f,g,在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針域,root

12、,2.4 二叉樹的存儲(chǔ)結(jié)構(gòu),二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)三叉鏈表,template struct btnode elemtype data; btnode *lchild , *rchild; btnode *parent; ;,lchild,data,rchild,parent,三叉鏈表例,root,2.5 二叉鏈表類的定義,二叉鏈表類模板,/binarytree.h #ifndef _binarytree_h #define _binarytree_h #include #include #include btnode.h using namespace std; template /二叉鏈表類

13、class binarytree public: binarytree():m_root(null) / 構(gòu)造函數(shù) binarytree(const binarytree ,2.5 二叉鏈表類的定義,二叉鏈表類模板,binarytree,2.5 二叉鏈表類的定義,二叉鏈表類模板,/先序遞歸遍歷二叉樹的接口函數(shù) void preordertraverse (void (*visit)(const elemtype . ,2.6 二叉樹的遞歸遍歷,問題的提出 順著某一條搜索路徑巡訪二叉樹中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。 “訪問”的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等。 “遍歷”

14、是任何類型均有的操作，對線性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)，故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)有兩個(gè)后繼， 則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。,2.6 二叉樹的遞歸遍歷,從下圖中可以看到，二叉樹是由根結(jié)點(diǎn)（d）、左子樹（l）及右子樹（r）三部分組成。 由這三部分的組合可得到以下的搜索路徑：dlr、ldr、lrd、drl、rdl、rld。 其中，先左后右的搜索方式是最常用的遍歷二叉樹的方法。,2.6 二叉樹的遞歸遍歷,先序遍歷二叉樹（dlr ） 若二叉樹為空樹，則空操作；否則， 訪問根結(jié)點(diǎn) 先序遍歷左子樹 先序遍歷右子樹。 先序遍歷右圖得到:

15、a b d e g h c f,2.6 二叉樹的遞歸遍歷,/先序遞歸遍歷二叉樹 template void binarytree :_preordertraverse (btnode*t, void(*visit)(const elemtype ,2.6 二叉樹的遞歸遍歷,中序遍歷二叉樹（ldr ） 若二叉樹為空樹，則空操作；否則， 中序遍歷左子樹 訪問根結(jié)點(diǎn) 中序遍歷右子樹。 中序遍歷右圖得到: d b g h e a f c,2.6 二叉樹的遞歸遍歷,后序遍歷二叉樹（lrd ） 若二叉樹為空樹，則空操作；否則， 后序遍歷左子樹 后序遍歷右子樹 訪問根結(jié)點(diǎn) 后序遍歷右圖得到: d h g e

16、 b f c a,2.7 幾個(gè)二叉樹基本操作的例子,建立二叉樹 對前頁所示的二叉樹進(jìn)行先序遍歷，得到一個(gè)變通的遍歷結(jié)果： a b d # # e g # h # # # c f # # # 建立二叉鏈表的存儲(chǔ)結(jié)構(gòu)，利用先序遍歷思想，以變通的遍歷結(jié)果作為輸入數(shù)據(jù)，執(zhí)行以下操作： 若當(dāng)前輸入數(shù)據(jù)為特殊字符，則當(dāng)前二叉樹根結(jié)點(diǎn)為空，否則： 1. 生成根結(jié)點(diǎn)，當(dāng)前數(shù)據(jù)寫入根結(jié)點(diǎn)數(shù)據(jù)域 2. 建立左子樹 3.建立右子樹,2.7 幾個(gè)二叉樹基本操作的例子,建立二叉樹,/按先序次序輸入結(jié)點(diǎn)值的方式建立二叉樹t template void binarytree:_create1(btnode * ,2.7 幾

17、個(gè)二叉樹基本操作的例子,銷毀二叉樹 如果二叉樹為空則結(jié)束，否則： （1）銷毀左子樹。 （2）銷毀右子樹。 （3）釋放根結(jié)點(diǎn)。 顯然，這是一個(gè)遞歸的過程，借助了后序遍歷的思想,2.7 幾個(gè)二叉樹基本操作的例子,銷毀二叉樹,/銷毀二叉鏈表形式的二叉樹t template void binarytree:_destroy(btnode* ,2.7 幾個(gè)二叉樹基本操作的例子,求二叉樹深度的算法 如果二叉樹為空則深度為0，否則： （1）求二叉樹左子樹的深度。 （2）求二叉樹右子樹的深度。 （3）二叉樹的深度是左、右深度大的那棵子樹的深度加1。 這也是一個(gè)遞歸的過程，可借助后序遍歷思想實(shí)現(xiàn)。,2.7 幾個(gè)

18、二叉樹基本操作的例子,求二叉樹深度的算法,/求二叉樹的深度 template int binarytree:_depth(btnode* t) if(!t) return 0; int h1,h2; h1=_depth(t-lchild); h2=_depth(t-rchild); return h1h2?h1+1:h2+1; ,2.8 二叉樹的非遞歸遍歷,/ 中序遍歷二叉樹的非遞歸算法(利用棧) template void binarytree :inordertraversenonrecursive ( void (*visit)(constelemtype / 向左走到盡頭 ,2.8 二

19、叉樹的非遞歸遍歷,/ 中序遍歷二叉樹的非遞歸算法(利用棧)（續(xù)） s.pop(); / 空指針退棧 if(!s.empty() / 訪問結(jié)點(diǎn),向右一步 p=s.top (); s.pop(); visit(p-data); s.push(p-rchild); ,中序非遞歸遍歷二叉樹時(shí)棧的變化示例,2.8 二叉樹的非遞歸遍歷,/ 層次遍歷二叉樹的非遞歸算法(利用隊(duì)列) template void binarytree :leveltraverse( void (*visit)(const elemtype / 非空的右孩子指針進(jìn)隊(duì) ,2.9 其他部分成員函數(shù)的實(shí)現(xiàn),/返回二叉樹t中結(jié)點(diǎn)的左兄弟結(jié)

20、點(diǎn)指針 template btnode* binarytree :leftsibling (btnode *p) btnode *father; father=parent (p); if(father ,2.9 其他部分成員函數(shù)的實(shí)現(xiàn),/返回二叉樹t中元素值為e的結(jié)點(diǎn)的雙親結(jié)點(diǎn)指針 template btnode* binarytree :_parent(btnode* t,btnode* p) if(t=null | t=p) return null; if(t-lchild=p | t-rchild=p) return t; btnode *q; q=_parent (t-lchild,

21、 p); if(q) return q; q =_parent (t-rchild,p); return q; ,2.9 其他部分成員函數(shù)的實(shí)現(xiàn),/復(fù)制一棵子樹 template btnode* binarytree:_copy( btnode* t) if(t=null) return null; btnode *p; p=new btnode; p-data=t-data; p-lchild=_copy(t-lchild); p-rchild=_copy(t-rchild); return p; ,2.9 其他部分成員函數(shù)的實(shí)現(xiàn),/ 設(shè)置條件插入 / 初始條件：二叉樹m_t存在,e是m_t

22、中某個(gè)結(jié)點(diǎn),lr為0或1,以復(fù)制對象的方式獲 / 得的非空二叉樹s與m_t不相交且右子樹為空。操作結(jié)果：根據(jù)lr為0或1,插入s / 為t中e結(jié)點(diǎn)的左或右子樹 e結(jié)點(diǎn)的原有左或右子樹則成為s的右子樹 template bool binarytree:insertchild(btnode *p, const int /對象復(fù)制,2.9 其他部分成員函數(shù)的實(shí)現(xiàn),/ 設(shè)置條件插入（續(xù)） if (lr=0) s-rchild=p-lchild; p-lchild=s; else s-rchild=p-rchild; p-rchild=s; return true; return false; ,2.1

23、0 主函數(shù),（演示二叉鏈表類部分基本操作的執(zhí)行結(jié)果）,2.11 線索二叉樹,遍歷二叉樹的結(jié)果是，求得結(jié)點(diǎn)的一個(gè)線性序列。 先序序列: a b c d e f g h k 中序序列: b d c a h g k f e 后序序列: d c b h k g f e a,a,b,c,d,e,f,g,h,k,2.11 線索二叉樹,線索二叉樹 在二叉樹的結(jié)點(diǎn)中，為了遍歷方便，可以加入按某種遍歷的線性序中的“前驅(qū)”和“后繼” 的指針，稱作“線索” 包含 “線索” 的存儲(chǔ)結(jié)構(gòu)，稱作 “線索鏈表”，與其相應(yīng)的二叉樹，稱作 “線索二叉樹” 對二叉樹按某種遍歷次序使其變?yōu)榫€索二叉樹的過程稱作“線索化”,2.11

24、線索二叉樹,線索二叉樹的約定 在二叉鏈表的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域ltag和rtag，并作如下規(guī)定： 若該結(jié)點(diǎn)的左子樹不空，則lchild域的指針指向其左子樹，且左標(biāo)志域ltag的值為“l(fā)ink”；否則，lchild域的指針指向其“前驅(qū)”，且左標(biāo)志域ltag的值為“thread” 若該結(jié)點(diǎn)的右子樹不空，則rchild域的指針指向其右子樹，且右標(biāo)志域rtag的值為“l(fā)ink”；否則，rchild域的指針指向其“后繼”，且右標(biāo)志域rtag的值為“thread”,3 遍歷二叉樹和線索二叉樹,線索二叉樹的類型描述,enum pointertag link=0 ,thread=1 ; template st

25、ruct bithrnode elemtype data; bithrnode* lchild; bithrnode* rchild; pointertag ltag, rtag; ;,中序線索二叉樹的結(jié)構(gòu),0,1,0,0,1,1,1,1,0,0,1,1,頭結(jié)點(diǎn),根結(jié)點(diǎn),a,b,c,d,e,2.11 線索二叉樹,由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡化了遍歷的算法。 線索二叉樹中序遍歷的關(guān)鍵問題 中序遍歷的第一個(gè)結(jié)點(diǎn) ? 左子樹上處于“最左下”（沒有左子樹）的結(jié)點(diǎn)。 在中序線索化鏈表中結(jié)點(diǎn)的后繼 ？ 若無右子樹，則為后繼線索所指結(jié)點(diǎn)；否則為對其右子樹進(jìn)行中序遍歷時(shí)訪

26、問的第一個(gè)結(jié)點(diǎn)。,for (p = firstnode(t); p; p = succ(p) visit(p);,2.11 線索二叉樹,中序線索二叉樹的遍歷算法,template void binarythrtree : traverse_inorderbithrtree( void (*visit)(const elemtype ,2.11 線索二叉樹,建立線索鏈表的方法 在中序遍歷過程中修改結(jié)點(diǎn)的左、右指針域，以保存當(dāng)前訪問結(jié)點(diǎn)的“前驅(qū)”和“后繼”信息。 遍歷過程中，附設(shè)指針pre, 并始終保持指針pre指向當(dāng)前訪問的指針p所指結(jié)點(diǎn)的前驅(qū)。 若p結(jié)點(diǎn)沒有左子樹，則令其左指針指向它的前驅(qū)（p

27、re所指結(jié)點(diǎn)）并將其左標(biāo)志改為thread（1）。 若pre結(jié)點(diǎn)沒有右子樹，則令它的右指針指向它的后繼（p所指結(jié)點(diǎn)）并將其右標(biāo)志改為thread（1）。在訪問下一結(jié)點(diǎn)前pre=p；p再移至下一訪問結(jié)點(diǎn)。,中序遍歷進(jìn)行中序線索化,/ 中序線索化二叉樹t,thrt指向頭結(jié)點(diǎn),ltag.rtag初始值均為link template void binarythrtree:_inorderthreading( bithrnode* / 右指針回指,中序遍歷進(jìn)行中序線索化,/ 中序線索化二叉樹t(續(xù)) /thrt指向頭結(jié)點(diǎn),ltag.rtag初始值均為link if(!t) / 若二叉樹空，則左指針回指

28、thrt-lchild=thrt; else thrt-lchild=t; pre=thrt; _threading(t, pre); / 中序遍歷的方式線索化二叉樹 pre-rchild=thrt; pre-rtag=thread; / 最后一個(gè)結(jié)點(diǎn)線索化 thrt-rchild=pre; t=thrt; ,中序遍歷進(jìn)行中序線索化的算法,/ 中序遍歷的方式線索化二叉樹p template void binarythrtree :_threading(bithrnode* / 遞歸右子樹線索化 ,3 樹和森林的再討論,4.3.1 樹的存儲(chǔ)結(jié)構(gòu) 樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 依據(jù)樹的度設(shè)立指向孩子結(jié)點(diǎn)的指針

29、個(gè)數(shù) 依據(jù)結(jié)點(diǎn)的度設(shè)立指向孩子結(jié)點(diǎn)的指針個(gè)數(shù) 孩子-兄弟表示法（樹的二叉鏈表結(jié)構(gòu)） 二個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)孩子和下一個(gè)兄弟。 特點(diǎn)：找孩子容易，找兄弟容易。同樣適用于森林。,/模板形式定義的結(jié)點(diǎn)結(jié)構(gòu) template struct treenode elemtype data; treenode * firstchild; treenode * nextsibling; ；,孩子兄弟表示法例,a,c,b,d,e,f,g,a,c,b,d,e,f,g,3.1 樹的存儲(chǔ)結(jié)構(gòu),靜態(tài)樹表包括：雙親表示法和孩子表示法 雙親表示法 所有的樹中結(jié)點(diǎn)存儲(chǔ)在一個(gè)地址連續(xù)的存儲(chǔ)空間中，結(jié)點(diǎn)中除數(shù)據(jù)域外只設(shè)一

30、個(gè)指向雙親的游標(biāo)。 結(jié)點(diǎn)的結(jié)構(gòu)為：,/模板形式定義的結(jié)點(diǎn)結(jié)構(gòu) template struct ptnode elemtype data; / 結(jié)點(diǎn)的數(shù)據(jù)域 int parent; / 結(jié)點(diǎn)的雙親游標(biāo) ;,雙親表示法的結(jié)構(gòu),樹的結(jié)構(gòu),struct ptree ptnode nodesmax _size; int n, root; /n為 結(jié)點(diǎn)個(gè)數(shù)、root為根結(jié)點(diǎn)的位置 ）,樹的雙親表示法例,3.1 樹的存儲(chǔ)結(jié)構(gòu),孩子表示法 實(shí)現(xiàn)：把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來，看成是一個(gè)線性表，且以單鏈表作存儲(chǔ)結(jié)構(gòu)，n個(gè)結(jié)點(diǎn)有n個(gè)孩子鏈表；而n個(gè)頭指針又組成一個(gè)線性表，為便于查找，用順序存儲(chǔ)。 特點(diǎn)：找孩子容易

31、，找雙親難。,孩子表示法的結(jié)構(gòu),孩子的結(jié)點(diǎn)結(jié)構(gòu) 頭結(jié)點(diǎn)結(jié)構(gòu),template struct ctnode elemtype data; / 結(jié)點(diǎn)的數(shù)據(jù)域 clinklist *firstchild;/ 結(jié)點(diǎn)的孩子鏈表指針域 ;,struct clinklist int child; clinklist *next; ;,孩子表示法的結(jié)構(gòu),樹的結(jié)構(gòu),struct ctree ctnode nodesmax _size; int n, root; /n為 結(jié)點(diǎn)個(gè)數(shù)、root為根結(jié)點(diǎn)的位置 ）,孩子表示法例,0,1,7,2,6,4,5,3,8,2,4,5,6,8,7,data,firstchild,

32、孩子雙親鏈表表示法例,0,1,7,2,6,4,5,3,8,2,4,5,6,8,7,data,firstchild,parent,3.2 樹和森林的遍歷,樹的遍歷 先根(次序)遍歷 若樹不空，則先訪問根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹。 后根(次序)遍歷 若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點(diǎn)。 按層次遍歷 若樹不空，則自上而下自左至右訪問樹中每個(gè)結(jié)點(diǎn)。,樹的遍歷例,先根(次序)遍歷: a b d e g h i c f 后根(次序)遍歷: d g h i e b f c a 層次(次序)遍歷: a b c d e f g h i,3.2 樹和森林的遍歷,森林由三部分組成： 1森林中第

33、一棵樹的根結(jié)點(diǎn)； 2森林中第一棵樹的子樹森林； 3森林中其它樹構(gòu)成的森林。,3.2 樹和森林的遍歷,森林的先序遍歷 若森林不空，則 訪問森林中第一棵樹的根結(jié)點(diǎn)； 先序遍歷森林中第一棵樹的子樹森林； 先序遍歷森林中（除第一棵樹之外）其余樹構(gòu)成的森林。 即：依次從左至右對森林中的每一棵樹進(jìn)行先根遍歷。,3.2 樹和森林的遍歷,森林的中序遍歷 若森林不空，則 中序遍歷森林中第一棵樹的子樹森林； 訪問森林中第一棵樹的根結(jié)點(diǎn)； 中序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。 即：依次從左至右對森林中的每一棵樹進(jìn)行后根遍歷。,森林的遍歷例,先序遍歷：a b c d e f g h i j 中序遍歷：b

34、 c d a f e h j i g 當(dāng)以二叉鏈表作樹的存儲(chǔ)結(jié)構(gòu)時(shí)，樹的先根遍歷和后根遍歷可借用二叉樹的先序遍歷和中序遍歷的算法實(shí)現(xiàn)。 森林的先序和中序遍歷即為其對應(yīng)二叉樹的先序和中序遍歷,樹和二叉樹遍歷的對應(yīng)關(guān)系 ？,求樹深度的算法,/求樹的深度 template int tree:depth (treenode * ,4 樹型結(jié)構(gòu)的應(yīng)用,4.1 算術(shù)表達(dá)式求值 此應(yīng)用中的算術(shù)表達(dá)式求值限于二元運(yùn)算符。 表達(dá)式定義如下： 表達(dá)式=(操作數(shù))+(運(yùn)算符)+(操作數(shù)) 操作數(shù)=無符號整數(shù) | 表達(dá)式 表達(dá)式可以有三種標(biāo)識方法，設(shè)exp=s1+op+s2，則 op+s1+s2為表達(dá)式的前綴表示法；

35、 s1+op+s2為表達(dá)式的中綴表示法； s1+s2+op為表達(dá)式的后綴表示法,4.1 算術(shù)表達(dá)式求值,將表達(dá)式用一棵二叉樹表示，則: 二叉樹的先序遍歷次序恰好為表達(dá)式的前綴表示（波蘭式）。 二叉樹的中序遍歷次序恰好為表達(dá)式的中綴表示。 二叉樹的后序遍歷次序恰好為表達(dá)式的后綴表示（逆波蘭式）。,4.1 算術(shù)表達(dá)式求值,由表達(dá)式的三種不同的標(biāo)識方法，可得到以下結(jié)論： 操作數(shù)之間的相對次序不變。 運(yùn)算符的相對次序不同。 中綴式丟失了括弧信息，致使運(yùn)算的次序不確定。 前綴式的運(yùn)算規(guī)則為：連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們之前且緊靠它們的運(yùn)算符構(gòu)成一最小表達(dá)式。 后綴式的運(yùn)算規(guī)則為：運(yùn)算符在式中出現(xiàn)的順序恰

36、為表達(dá)式的運(yùn)算順序；每個(gè)運(yùn)算符和在它之前出現(xiàn)且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式。,4.1 算術(shù)表達(dá)式求值,設(shè)binaryexptree是用二叉鏈表結(jié)構(gòu)定義的表達(dá)式類，在建立了二叉算術(shù)表達(dá)式樹后，類binaryexptree的求值過程（成員函數(shù)_evaluate）如下：,/用后序遍歷的方式對表達(dá)式樹求值 int binaryexptree :_evaluate(btnode* ,4.1 算術(shù)表達(dá)式求值,成員函數(shù)_opreate過程如下：,/ 字符theta決定a與b 執(zhí)行何種運(yùn)算 int binaryexptree:_opreate(const int ,4.1 算術(shù)表達(dá)式求值,成員函數(shù)_

37、create 過程如下：,/已知二叉樹的先序遍歷次序及中序遍歷次序，建立二叉樹t 其中：ch1 /為表達(dá)式的前綴表示，ch2為表達(dá)式的中綴表示，low、 high分別為中 /綴次序的起始位置和最終位置，本函數(shù)根據(jù)先序次序和中序次序的形成規(guī) /律，運(yùn)用先序遞歸遍歷的思想逐個(gè)為先序次序中的第k個(gè)元素（k的初值為0） /生成二叉鏈表中的結(jié)點(diǎn)。 void binaryexptree : _create (btnode* ,4.1 算術(shù)表達(dá)式求值,成員函數(shù)_ create 過程如下：,if (ch2i = ch1k) k+; _create (t-lchild,ch1,ch2,low,i-1,k); /

38、 建立左子樹 _create (t-rchild,ch1,ch2,i+1,high,k); / 建立右子樹 ,4.1 算術(shù)表達(dá)式求值,完整的算術(shù)表達(dá)式求值類代碼,4.2 樹與等價(jià)問題,等價(jià)關(guān)系：若集合s中的關(guān)系r是自反的、對稱的和可傳遞的，則稱它是一個(gè)等價(jià)關(guān)系。 等價(jià)類：設(shè)r是集合s的等價(jià)關(guān)系，對任意xs，由 x r = y | y s / x r y )給出的集合x rs稱為由 xs 生成的一個(gè)r等價(jià)類。 若r是s上的一個(gè)等價(jià)關(guān)系，由r可以產(chǎn)生這個(gè)集合s的一個(gè)唯一的劃分s1, s2, , sn。這些集合互不相交，其并為s，則這些子集si便稱為s的r等價(jià)類。 等價(jià)類問題可描述為：假設(shè)集合s有n

39、個(gè)元素，已知m個(gè)形如 (x, y)( x, ys )的等價(jià)偶對確定了等價(jià)關(guān)系r，求s的劃分。,4.2 樹與等價(jià)問題,求解等價(jià)類問題的算法如下： 令s中每個(gè)元素各自形成一個(gè)只含單個(gè)成員的子集，記作s1, s2, , sn。 重復(fù)讀入m個(gè)關(guān)系（偶對），對每個(gè)讀入的偶對（x，y），判定x和y所屬的子集，若這兩個(gè)子集不相等，則合并它們并取代這兩個(gè)子集。 當(dāng)所有的m個(gè)關(guān)系處理完后，剩下的這些非空子集即為s的r等價(jià)類。,求解等價(jià)類問題的示例,有一個(gè)集合s= a, b, c, d, e, f 初始時(shí)每個(gè)元素各自形成一個(gè)等價(jià)類：a、b、c、d、e、f。 設(shè)有等價(jià)關(guān)系r=(a, c), (b, d), (a,

40、f), (e, f）。 則當(dāng)討論完等關(guān)系r中的偶對后，集合中的元素形成二個(gè)等價(jià)類：a , c, e, f、b, d。,4.2 樹與等價(jià)問題,由求解等價(jià)類問題的算法可知，劃分等價(jià)類需對集合進(jìn)行以下的幾個(gè)基本操作： 構(gòu)造只含一個(gè)元素的集合。 判定某個(gè)元素所在的子集。 合并兩個(gè)互不相交的集合。 這些基本操作的實(shí)現(xiàn)當(dāng)然需建立在存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)上，靜態(tài)樹表中的雙親表示法是一合適的選擇。,/ ptnode.h struct ptnode char data; / 結(jié)點(diǎn)的數(shù)據(jù)域 int parent; / 結(jié)點(diǎn)的雙親游標(biāo) ;,4.2 樹與等價(jià)問題,用雙親表示法結(jié)構(gòu)表示，求解等價(jià)類問題的c+類meset可如下定

41、義：,/meset.h #ifndef h_meset_h #define h_meset_h #include #include ptnode.h using namespace std; class meset public: / 構(gòu)造函數(shù)：分配m個(gè)存儲(chǔ)單元的順序空間 meset(int n):m_len(0),m_size(n) m_nodes = new ptnoden; ,4.2 樹與等價(jià)問題,c+類meset定義（續(xù)）：,/析構(gòu)函數(shù)：釋放空間 meset() delete m_nodes; bool create( char , const int ,4.2 樹與等價(jià)問題,構(gòu)造函數(shù)

42、為存儲(chǔ)集合中的數(shù)據(jù)元素分配了m個(gè)（雙親表示法結(jié)點(diǎn)結(jié)構(gòu)）存儲(chǔ)單元的順序空間。,4.2 樹與等價(jià)問題,建立n個(gè)只含一個(gè)元素的等價(jià)類的過程（成員函數(shù)create）,/ 建立n個(gè)集合（初始時(shí)每一集合只有一個(gè)元素） bool meset:create( char ch, int const ,4.2 樹與等價(jià)問題,建立n個(gè)等價(jià)類實(shí)際上是建立了含有n棵子樹的森林，如下圖所示。,4.2 樹與等價(jià)問題,讀入偶對(x, y)如何判定某個(gè)元素所在的子集（子樹），又如何合并兩個(gè)互不相交的子集（子樹）？ 首先，分別查找元素x和y在數(shù)組中的位置（設(shè)x和y在數(shù)組中的位置分別是i和j）,/ 查找元素e在集合中的位置 int

43、 meset:locateelem(const char ,4.2 樹與等價(jià)問題,接著分別查找位序是i和j的數(shù)據(jù)元素所處子集（子樹）的根,/ 查找位序是i的元素所處集合的根 int meset:findroot(const int ,4.2 樹與等價(jià)問題,若元素x和y在集合中所處子集（子樹）的根不同（i != j），則合并之。,/ 合并根的位置是i和j的兩個(gè)集合 void meset:merge( const int ,4.2 樹與等價(jià)問題,如偶對(a,c)中的數(shù)據(jù)元素a所屬子集（子樹）為0，數(shù)據(jù)元素c所屬子集（子樹）為2，如下圖所示，則有：m_nodes0.parent=2。,4.2 樹與等

44、價(jià)問題,這種方法有可能出現(xiàn)單支樹的情形，使得查找某一數(shù)據(jù)元素所處子集（子樹）的根時(shí)，搜索長度達(dá)到最大如下圖所示。 假設(shè)n個(gè)集合s1,s2,sn, 每個(gè)子集只有一個(gè)元素si = i ，用n棵只有一個(gè)根節(jié)點(diǎn)的樹表示，則在做了n-1次并操作后，最后得到的集合（樹）深度平均為log n，最壞時(shí)為n。,4.2 樹與等價(jià)問題,為確保集合（樹）的深度任何情況下不超出log n，則需對合并方法進(jìn)行改良 。,/高效合并根的位置是i和j的兩個(gè)集合 void meset:effmerge(const int ,4.2 樹與等價(jià)問題,下圖是基于s= a, b, c, d, e, f ， r=(a,c),(b,d),(

45、a,f),(e,f)，經(jīng)高效合并后的結(jié)果示意圖,4.2 樹與等價(jià)問題,類meset中的其他成員函數(shù)如下。 演示等價(jià)類合并過程的主函數(shù),/ 顯示當(dāng)前集合的狀態(tài) void meset:display() cout 位置 data parent endl; for (int i = 0; i m_len; i+) cout i m_nodesi.data m_nodesi.parent endl; ,4.3 赫夫曼樹及赫夫曼編碼,結(jié)點(diǎn)的路徑長度 從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上分支的數(shù)目。 樹的路徑長度 樹根到每個(gè)結(jié)點(diǎn)的路徑長度之和。 結(jié)點(diǎn)的帶權(quán)路徑長度 從樹根到該結(jié)點(diǎn)之間的路徑長度與該結(jié)點(diǎn)上所帶權(quán)值的乘積

46、 樹的帶權(quán)路徑長度 樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和 設(shè)有n個(gè)權(quán)值w1,w2,wn，構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子的權(quán)值為wi，則其中帶權(quán)路徑長度wpl最小的二叉樹叫最優(yōu)二叉樹或者叫赫夫曼樹。,wpl計(jì)算例,4.3 赫夫曼樹及赫夫曼編碼,構(gòu)造赫夫曼樹的方法 根據(jù)給定的 n 個(gè)權(quán)值 w1, w2, , wn，構(gòu)造 n 棵二叉樹的集合 f = t1, t2, , tn，其中每棵二叉樹中均只含一個(gè)帶權(quán)值 為 wi 的根結(jié)點(diǎn)，其左、右子樹為空樹； 在 f 中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之

47、和； 從f中刪去這兩棵樹，同時(shí)加入剛生成的新樹； 重復(fù) 2 和3 兩步，直至 f 中只含一棵樹為止。,構(gòu)造赫夫曼樹過程例,a,7,b,5,c,2,d,4,a,7,b,5,c,2,d,4,6,a,7,b,5,c,2,d,4,6,11,a,7,b,5,c,2,d,4,6,11,18,第1步,第2步,第3步,第4步,赫夫曼樹存儲(chǔ),由于樹中的結(jié)點(diǎn)數(shù)是確定的 ，選擇靜態(tài)三叉樹表作為存儲(chǔ)結(jié)構(gòu)。 靜態(tài)三叉樹表結(jié)點(diǎn)結(jié)構(gòu),/ htnode.h / 赫夫曼樹節(jié)點(diǎn)結(jié)構(gòu) struct htnode char ch; int weight,parent,lchild,rchild; ;,赫夫曼樹存儲(chǔ),赫夫曼樹存儲(chǔ),4.3 赫夫曼樹及赫夫曼編碼,c+實(shí)現(xiàn)的huffmantree類定義,/ 赫夫曼樹類 class huffmantree / 將赫夫曼編碼類作為赫夫曼類的友元類（后面用到） friend class huffman