第5章二叉樹(shù)(1)

1、2022-4-11數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法第第5 5章章 二叉樹(shù)二叉樹(shù)朱凌朱凌 2022-4-11二叉樹(shù)知識(shí)點(diǎn)二叉樹(shù)知識(shí)點(diǎn)1 1 2 2 3 4 1 2 5 1 2 3 4 6 7 8 線(xiàn)性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖結(jié)構(gòu)線(xiàn)性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖結(jié)構(gòu)復(fù)習(xí)n 數(shù)據(jù)的邏輯結(jié)構(gòu)可以表示為和： K：。 R：K。 R是KK上的二元關(guān)系。：唯一前驅(qū)、唯一后繼，反映一種關(guān)系。：唯一前驅(qū)、多個(gè)后繼，反映一種關(guān)系。：不限制前驅(qū)的個(gè)數(shù)，也不限制后繼的個(gè)數(shù)，反映一種關(guān)系。樹(shù)與子樹(shù)樹(shù)與子樹(shù)n 一棵樹(shù)可以分成幾個(gè)大的分支（稱(chēng)為），每個(gè)大分支再分成幾個(gè)小分支，小分支再分成更小的分支，。二叉樹(shù)二叉樹(shù)n 二叉樹(shù)是一種，特殊在于： 每

2、個(gè)結(jié)點(diǎn)最多(稱(chēng)為)，也就是說(shuō)每個(gè)結(jié)點(diǎn)的子女結(jié)點(diǎn)為0個(gè)、1個(gè)或2個(gè)； 兩個(gè)子女結(jié)點(diǎn)，即使只有1個(gè)子女結(jié)點(diǎn)，也要區(qū)分為是左子女結(jié)點(diǎn)還是右子女結(jié)點(diǎn)。1 1 二叉樹(shù)的概念二叉樹(shù)的概念n 通常用來(lái)描述中的一些概念。：若在樹(shù)中存在從結(jié)點(diǎn)k指向結(jié)點(diǎn)k的連線(xiàn)，則稱(chēng)k是k的(parent，也稱(chēng)，或簡(jiǎn)稱(chēng)為)，而k是k的(child，也稱(chēng)，或簡(jiǎn)稱(chēng)為)。樹(shù)的：沒(méi)有父結(jié)點(diǎn)的結(jié)點(diǎn)稱(chēng)為樹(shù)的(root)。：若有k指向k和k指向k，則稱(chēng)k和k互為(sibling)。：父結(jié)點(diǎn)指向子女結(jié)點(diǎn)的連線(xiàn)，稱(chēng)為(edge)?？梢哉J(rèn)為，由父結(jié)點(diǎn)指向子女結(jié)點(diǎn)。：若存在結(jié)點(diǎn)序列k0, k1, , ks，使得, , , 都是樹(shù)中的邊，則該結(jié)點(diǎn)序列稱(chēng)

3、為從結(jié)點(diǎn)k0到結(jié)點(diǎn)ks的(path)。注意，。：路徑中邊的數(shù)目稱(chēng)為路徑長(zhǎng)度。和：若存在一條從k到ks的路徑，則稱(chēng)k是ks的(ancestor)，ks是k的(descendant)。和：沒(méi)有子女結(jié)點(diǎn)的結(jié)點(diǎn)稱(chēng)為(leaf)或，而非終端結(jié)點(diǎn)的結(jié)點(diǎn)稱(chēng)為或(internal node)。：一個(gè)結(jié)點(diǎn)的子女結(jié)點(diǎn)個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的(degree)。：根結(jié)點(diǎn)的(level)為0，。：樹(shù)的(height)為樹(shù)的深度(即所有結(jié)點(diǎn)的最大層次)加1。（，層次和高度的關(guān)系類(lèi)似于數(shù)組中元素下標(biāo)和數(shù)組長(zhǎng)度的關(guān)系)。：所有結(jié)點(diǎn)的最大層次，稱(chēng)為樹(shù)的(depth)。1 1 二叉樹(shù)的定義及相關(guān)概念二叉樹(shù)的定義及相關(guān)概念n 二叉樹(shù)(bi

4、nary tree)的：二叉樹(shù)由結(jié)點(diǎn)的有限集合構(gòu)成，這個(gè)有限集合，、分別稱(chēng)為這個(gè)根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的。 這是一個(gè)的定義。n 二叉樹(shù)的：2 2 滿(mǎn)二叉樹(shù)、完全二叉樹(shù)和擴(kuò)充二叉樹(shù)滿(mǎn)二叉樹(shù)、完全二叉樹(shù)和擴(kuò)充二叉樹(shù)、是二叉樹(shù)的幾個(gè)特殊情形。n 注意： 極少數(shù)教材上。是本課件自己定義的概念(目前還沒(méi)有哪本教材定義了這個(gè)概念)，但有的教材將這種二叉樹(shù)定義為滿(mǎn)二叉樹(shù)。 總之，現(xiàn)有的教材對(duì)這3種特殊的二叉樹(shù)定義比較。本課件對(duì)這3種特殊二叉樹(shù)的，今后的討論以本課件中的概念和定義方式為準(zhǔn)。滿(mǎn)二叉樹(shù)滿(mǎn)二叉樹(shù)：滿(mǎn)足以下條件的二叉樹(shù)，稱(chēng)為滿(mǎn)二叉樹(shù)(full binary tree)。即。 或者：。完全二叉樹(shù)完全二叉

5、樹(shù)：滿(mǎn)足以下條件的二叉樹(shù)，稱(chēng)為完全二叉樹(shù)(complete binary tree)。 或者：。完全滿(mǎn)二叉樹(shù)完全滿(mǎn)二叉樹(shù)：滿(mǎn)足以下條件的二叉樹(shù)，稱(chēng)為完全滿(mǎn)二叉樹(shù)。 第i層有個(gè)結(jié)點(diǎn)。即。：。(見(jiàn)備注)擴(kuò)充二叉樹(shù)擴(kuò)充二叉樹(shù)：當(dāng)二叉樹(shù)里出現(xiàn)了空的子樹(shù)，就增加新的、特殊的結(jié)點(diǎn)；對(duì)于原來(lái)二叉樹(shù)度數(shù)為1的分支結(jié)點(diǎn)，在它下面增加一個(gè)空樹(shù)葉；對(duì)于原來(lái)二叉樹(shù)的樹(shù)葉，在它下面增加兩個(gè)空樹(shù)葉；經(jīng)過(guò)這樣的構(gòu)造得到的二叉樹(shù)稱(chēng)為。n 在下圖中，用表示空樹(shù)葉。n 8節(jié)介紹的就是一種擴(kuò)充二叉樹(shù)。，（即樹(shù)葉）。：從擴(kuò)充二叉樹(shù)的根到每個(gè)外部結(jié)點(diǎn)的路徑長(zhǎng)度之和。 在下圖中，E = 2 + 3 + 3 + 3 + 4 + 4 + 4

6、 + 4 + 4 + 4 = 35。：從擴(kuò)充二叉樹(shù)的根到每個(gè)內(nèi)部結(jié)點(diǎn)的路徑長(zhǎng)度之和。 在下圖中，I = 1 + 1 + 2 + 2 + 2 + 3 + 3 + 3 = 17。n 擴(kuò)充二叉樹(shù)的：。：，其中n為擴(kuò)充二叉樹(shù)內(nèi)部結(jié)點(diǎn)個(gè)數(shù)，也就是原二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)。2 2 二叉樹(shù)的主要性質(zhì)二叉樹(shù)的主要性質(zhì)) 1(log2n) 1(log2n3 3 二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型n 二叉樹(shù)的的。如： 初始化二叉樹(shù)； 把兩棵二叉樹(shù)的根結(jié)點(diǎn)作為一個(gè)新根結(jié)點(diǎn)的子結(jié)點(diǎn)來(lái)合并兩棵二叉樹(shù)。 等等。n 二叉樹(shù)的的。如： 訪(fǎng)問(wèn)某個(gè)結(jié)點(diǎn)的左子結(jié)點(diǎn)、右子結(jié)點(diǎn)、父結(jié)點(diǎn)，或者訪(fǎng)問(wèn)結(jié)點(diǎn)中存儲(chǔ)的數(shù)據(jù)。n 二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型

7、包括結(jié)點(diǎn)類(lèi)和二叉樹(shù)類(lèi)。：二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型：二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型提供：結(jié)點(diǎn)的數(shù)據(jù)域info。：豐富的構(gòu)造函數(shù)、返回和設(shè)置左右子女結(jié)點(diǎn)指針、返回和設(shè)置結(jié)點(diǎn)的數(shù)據(jù)域、判斷結(jié)點(diǎn)是否為樹(shù)葉等。提供：二叉樹(shù)根結(jié)點(diǎn)root。：豐富的構(gòu)造函數(shù)、析構(gòu)函數(shù)、判斷二叉樹(shù)是否為空樹(shù)、返回二叉樹(shù)的根結(jié)點(diǎn)、獲取當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)、獲取當(dāng)前結(jié)點(diǎn)的左兄弟或右兄弟、豐富的遍歷函數(shù)等。二叉樹(shù)結(jié)點(diǎn)類(lèi)二叉樹(shù)結(jié)點(diǎn)類(lèi)BinaryTreeNodeBinaryTreeNode/聲明聲明BinaryTree類(lèi)，因?yàn)樵陬?lèi)，因?yàn)樵贐inaryTreeNode類(lèi)中用到了標(biāo)識(shí)符類(lèi)中用到了標(biāo)識(shí)符BinaryTreetemplate class Bin

8、aryTree;templateclass BinaryTreeNode/二叉樹(shù)結(jié)點(diǎn)的抽象數(shù)據(jù)類(lèi)型二叉樹(shù)結(jié)點(diǎn)的抽象數(shù)據(jù)類(lèi)型friend class BinaryTree;/聲明二叉樹(shù)類(lèi)為結(jié)點(diǎn)類(lèi)的友元類(lèi)聲明二叉樹(shù)類(lèi)為結(jié)點(diǎn)類(lèi)的友元類(lèi),便于訪(fǎng)問(wèn)私有數(shù)據(jù)成員便于訪(fǎng)問(wèn)私有數(shù)據(jù)成員private:T info;/二叉樹(shù)結(jié)點(diǎn)數(shù)據(jù)域二叉樹(shù)結(jié)點(diǎn)數(shù)據(jù)域/實(shí)現(xiàn)時(shí)，可以補(bǔ)充結(jié)點(diǎn)的左子結(jié)點(diǎn)、右子結(jié)點(diǎn)指針作為數(shù)據(jù)成員實(shí)現(xiàn)時(shí)，可以補(bǔ)充結(jié)點(diǎn)的左子結(jié)點(diǎn)、右子結(jié)點(diǎn)指針作為數(shù)據(jù)成員public:BinaryTreeNode( );/缺省構(gòu)造函數(shù)缺省構(gòu)造函數(shù)BinaryTreeNode( const T& ele );/給定

9、數(shù)據(jù)的構(gòu)造函數(shù)給定數(shù)據(jù)的構(gòu)造函數(shù)/給定了結(jié)點(diǎn)值和左右子樹(shù)的構(gòu)造函數(shù)給定了結(jié)點(diǎn)值和左右子樹(shù)的構(gòu)造函數(shù)BinaryTreeNode( const T& ele, BinaryTreeNode *l, BinaryTreeNode *r );T value( ) const;/返回當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)返回當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)BinaryTreeNode* leftchild( ) const;/返回當(dāng)前結(jié)點(diǎn)的左子樹(shù)指針?lè)祷禺?dāng)前結(jié)點(diǎn)的左子樹(shù)指針BinaryTreeNode* rightchild( ) const;/返回當(dāng)前結(jié)點(diǎn)的右子樹(shù)指針?lè)祷禺?dāng)前結(jié)點(diǎn)的右子樹(shù)指針void setLeftchild( Bi

10、naryTreeNode* L );/設(shè)置當(dāng)前結(jié)點(diǎn)的左子樹(shù)指針設(shè)置當(dāng)前結(jié)點(diǎn)的左子樹(shù)指針void setRightchild( BinaryTreeNode* R );/設(shè)置當(dāng)前結(jié)點(diǎn)的右子樹(shù)指針設(shè)置當(dāng)前結(jié)點(diǎn)的右子樹(shù)指針void setValue( const T& val );/設(shè)置當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域設(shè)置當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域bool isLeaf( ) const;/判定當(dāng)前結(jié)點(diǎn)是否為葉結(jié)點(diǎn)，若是則返回判定當(dāng)前結(jié)點(diǎn)是否為葉結(jié)點(diǎn)，若是則返回trueBinaryTreeNode &operator=(const BinaryTreeNode & Node);二叉樹(shù)類(lèi)二叉樹(shù)類(lèi)Bina

11、ryTreeBinaryTreetemplateclass BinaryTree/二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型protected:BinaryTreeNode* root;/二叉樹(shù)根結(jié)點(diǎn)二叉樹(shù)根結(jié)點(diǎn)public:BinaryTree( ) root = NULL; /缺省構(gòu)造函數(shù)缺省構(gòu)造函數(shù)BinaryTree( ) DeleteBinaryTree( root ); /析構(gòu)函數(shù)析構(gòu)函數(shù)bool isEmpty( ) ;/判定二叉樹(shù)是否為空樹(shù)判定二叉樹(shù)是否為空樹(shù)BinaryTreeNode* Root( ) return root; /返回二叉樹(shù)根結(jié)點(diǎn)返回二叉樹(shù)根結(jié)點(diǎn)/返回返回cu

12、rrent結(jié)點(diǎn)的父結(jié)點(diǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)BinaryTreeNode* Parent( BinaryTreeNode * current );/返回返回current結(jié)點(diǎn)的左兄弟結(jié)點(diǎn)的左兄弟BinaryTreeNode* LeftSibling( BinaryTreeNode * current );/返回返回current結(jié)點(diǎn)的右兄弟結(jié)點(diǎn)的右兄弟BinaryTreeNode* RightSibling( BinaryTreeNode * current );/以以val作為根結(jié)點(diǎn)，作為根結(jié)點(diǎn)，leftTree作為樹(shù)的左子樹(shù)，作為樹(shù)的左子樹(shù)，rightTree作為樹(shù)的右子樹(shù)作為樹(shù)的右子樹(shù)/構(gòu)造一棵新

13、的二叉樹(shù)構(gòu)造一棵新的二叉樹(shù)void CreateTree( const T& info, BinaryTree& leftTree,BinaryTree& rightTree );/以下是深度優(yōu)先遍歷二叉樹(shù)以下是深度優(yōu)先遍歷二叉樹(shù)void PreOrder( BinaryTreeNode * root );/前序遍歷二叉樹(shù)或其子樹(shù)前序遍歷二叉樹(shù)或其子樹(shù)void InOrder( BinaryTreeNode * root );/中序遍歷二叉樹(shù)或其子樹(shù)中序遍歷二叉樹(shù)或其子樹(shù)void PostOrder( BinaryTreeNode * root );/后序遍歷二叉樹(shù)或其

14、子樹(shù)后序遍歷二叉樹(shù)或其子樹(shù)/以下是按層次遍歷二叉樹(shù)或其子樹(shù)以下是按層次遍歷二叉樹(shù)或其子樹(shù)(即廣度優(yōu)先遍歷即廣度優(yōu)先遍歷)void LevelOrder( BinaryTreeNode * root );void DeleteBinaryTree( BinaryTreeNode * root );/刪除二叉樹(shù)或其子樹(shù)刪除二叉樹(shù)或其子樹(shù);4 4 二叉樹(shù)的遍歷二叉樹(shù)的遍歷(traversal)：也稱(chēng)為(search)，指按一定次序系統(tǒng)地訪(fǎng)問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)恰被訪(fǎng)問(wèn)一次。n 二叉樹(shù)是一種非線(xiàn)性的數(shù)據(jù)結(jié)構(gòu)。遍歷二叉樹(shù)的過(guò)程實(shí)際上就是，或者說(shuō)?？梢跃€(xiàn)性化為：D, B, G, E, H, A

15、, F, I, C(實(shí)際上是)。也可以線(xiàn)性化為其他順序的序列。兩種重要的遍歷方法兩種重要的遍歷方法： 本質(zhì)上是一種，可以采用遞歸方式實(shí)現(xiàn)；但也可以采用非遞歸方式實(shí)現(xiàn)。：是一種。1 1 深度優(yōu)先搜索二叉樹(shù)深度優(yōu)先搜索二叉樹(shù)n 二叉樹(shù)的基本結(jié)構(gòu)如下圖所示。一棵二叉樹(shù)(在此用 表示)、和三部分組成。n 如果。則按照根結(jié)點(diǎn)的訪(fǎng)問(wèn)順序可以將深度優(yōu)先遍歷分為以下3種方式：( )：訪(fǎng)問(wèn)三部分的順序?yàn)椤? )：訪(fǎng)問(wèn)順序?yàn)椤? )：訪(fǎng)問(wèn)順序?yàn)?。分別按前序、中序、后序遍歷右圖所示的二叉樹(shù)，將得到怎樣的結(jié)點(diǎn)序列？的為：訪(fǎng)問(wèn)根結(jié)點(diǎn)；按前序遍歷左子樹(shù)；按前序遍歷右子樹(shù)。的為：按中序遍歷左子樹(shù)；訪(fǎng)問(wèn)根結(jié)點(diǎn)；按中序遍歷右子

16、樹(shù)。的為：按后續(xù)遍歷左子樹(shù)；按后續(xù)遍歷右子樹(shù)；訪(fǎng)問(wèn)根結(jié)點(diǎn)。1 1 深度優(yōu)先搜索二叉樹(shù)的遞歸實(shí)現(xiàn)深度優(yōu)先搜索二叉樹(shù)的遞歸實(shí)現(xiàn)n 二叉樹(shù)的深度優(yōu)先搜索是的。n 以為例，要遍歷一棵二叉樹(shù)，首先訪(fǎng)問(wèn)根結(jié)點(diǎn)，然后進(jìn)入根結(jié)點(diǎn)的左子樹(shù)，在左子樹(shù)中又是先訪(fǎng)問(wèn)根，然后向左下降進(jìn)入左子樹(shù)；如此進(jìn)行下去，直到遇到樹(shù)葉，也就是說(shuō)。的為：訪(fǎng)問(wèn)根結(jié)點(diǎn)；按前序遍歷左子樹(shù)；按前序遍歷右子樹(shù)。深度優(yōu)先搜索深度優(yōu)先搜索n 要設(shè)計(jì)一個(gè)實(shí)現(xiàn)二叉樹(shù)深度優(yōu)先遍歷的算法，就必須設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)，以便當(dāng)遍歷完一個(gè)根的左子樹(shù)后能順利的轉(zhuǎn)移到這個(gè)根結(jié)點(diǎn)的右子樹(shù)繼續(xù)遍歷下去。n 這個(gè)數(shù)據(jù)結(jié)構(gòu)通常是一個(gè)。對(duì)(即)，系統(tǒng)為程序分配一個(gè)()；如果要采用

17、，則用戶(hù)需要。(以前序遍歷為例演示)的為：訪(fǎng)問(wèn)根結(jié)點(diǎn)；按前序遍歷左子樹(shù)；按前序遍歷右子樹(shù)。隱式和顯式另外一個(gè)實(shí)例隱式和顯式另外一個(gè)實(shí)例thisthis指針指針n 在類(lèi)的成員函數(shù)里有兩種方法：實(shí)際上也是通過(guò)this指針來(lái)訪(fǎng)問(wèn)的，地使用this指針。：地使用this指針。(P108)(P108)二叉樹(shù)類(lèi)二叉樹(shù)類(lèi)BinaryTreeBinaryTree實(shí)現(xiàn)：實(shí)現(xiàn)：template /遞歸前序遍歷二叉樹(shù)或其子樹(shù)遞歸前序遍歷二叉樹(shù)或其子樹(shù)void BinaryTree:PreOrder( BinaryTreeNode* root )if( root!=NULL )Visit(root-Value();/

18、訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)PreOrder( root-leftchild() ); /訪(fǎng)問(wèn)左子樹(shù)訪(fǎng)問(wèn)左子樹(shù)PreOrder( root-rightchild() );/訪(fǎng)問(wèn)右子樹(shù)訪(fǎng)問(wèn)右子樹(shù)template/遞歸中序遍歷二叉樹(shù)或其子樹(shù)遞歸中序遍歷二叉樹(shù)或其子樹(shù)void BinaryTree:InOrder( BinaryTreeNode* root )if( root!=NULL )InOrder( root-leftchild() );/訪(fǎng)問(wèn)左子樹(shù)訪(fǎng)問(wèn)左子樹(shù)Visit(root-Value(); /訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)InOrder( root-rightchild() ); /訪(fǎng)問(wèn)右子樹(shù)

19、訪(fǎng)問(wèn)右子樹(shù)template/遞歸后序遍歷二叉樹(shù)或其子樹(shù)遞歸后序遍歷二叉樹(shù)或其子樹(shù)void BinaryTree:PostOrder( BinaryTreeNode* root )if( root!=NULL )PostOrder( root-leftchild() );/訪(fǎng)問(wèn)左子樹(shù)訪(fǎng)問(wèn)左子樹(shù)PostOrder( root-rightchild() );/訪(fǎng)問(wèn)右子樹(shù)訪(fǎng)問(wèn)右子樹(shù)Visit(root-Value(); /訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)2 2 遍歷二叉樹(shù)遍歷二叉樹(shù)n 棧是實(shí)現(xiàn)遞歸的最常用的數(shù)據(jù)結(jié)構(gòu)，所以對(duì)于遞歸定義的二叉樹(shù)遍歷運(yùn)算，最自然的是，。n 使用棧的算法很簡(jiǎn)單。請(qǐng)用示意圖描述用非遞歸

20、方式對(duì)下圖所示的二叉樹(shù)進(jìn)行前序遍歷時(shí)棧的存儲(chǔ)情況及入棧、出棧操作序列。遇到一個(gè)結(jié)點(diǎn)，然后下降去遍歷它的左子樹(shù)；遍歷完它的左子樹(shù)后，繼續(xù)遍歷。演示：非遞歸前序遍歷時(shí)棧的使用演示：非遞歸前序遍歷時(shí)棧的使用遇到一個(gè)結(jié)點(diǎn)，遇到一個(gè)結(jié)點(diǎn)，然后下降去遍，然后下降去遍歷它的左子樹(shù)；遍歷完它的左子樹(shù)后，歷它的左子樹(shù)；遍歷完它的左子樹(shù)后，繼續(xù)遍歷。，繼續(xù)遍歷。(P109)(P109)二叉樹(shù)類(lèi)二叉樹(shù)類(lèi)BinaryTreeBinaryTree實(shí)現(xiàn)：實(shí)現(xiàn)：template/非遞歸前序遍歷二叉樹(shù)或其子樹(shù)非遞歸前序遍歷二叉樹(shù)或其子樹(shù)void BinaryTree:PreOrderWithoutRecusion( Bina

21、ryTreeNode* root )using std:stack;stack BinaryTreeNode* aStack; /棧中的結(jié)點(diǎn)為二叉樹(shù)結(jié)點(diǎn)指針棧中的結(jié)點(diǎn)為二叉樹(shù)結(jié)點(diǎn)指針BinaryTreeNode* pointer = root;/保存輸入?yún)?shù)保存輸入?yún)?shù)aStack.push(NULL);while( pointer )Visit(pointer-Value(); /訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)if( pointer-rightchild()!=NULL )aStack.push( pointer-rightchild() );/非空右孩子入棧非空右孩子入棧 if( pointer

22、-leftchild()!=NULL ) pointer=pointer-leftchild() );/左路下降左路下降else/左子樹(shù)訪(fǎng)問(wèn)完畢，轉(zhuǎn)向訪(fǎng)問(wèn)右子樹(shù)左子樹(shù)訪(fǎng)問(wèn)完畢，轉(zhuǎn)向訪(fǎng)問(wèn)右子樹(shù)pointer = aStack.top( );/棧頂元素退棧棧頂元素退棧aStack.pop( );/棧頂元素退棧棧頂元素退棧/end of if/end of while遇到一個(gè)結(jié)點(diǎn)，就，然后下降去遍歷它的左子樹(shù)；遍歷完它的左子樹(shù)后，以輸出結(jié)點(diǎn)的值作為訪(fǎng)問(wèn)結(jié)點(diǎn)的操作3 3 遍歷二叉樹(shù)遍歷二叉樹(shù)n 使用棧的算法也很簡(jiǎn)單。請(qǐng)用示意圖描述用非遞歸方式對(duì)下圖所示的二叉樹(shù)進(jìn)行中序遍歷時(shí)棧的存儲(chǔ)情況及入棧、出棧操作

23、序列。遇到一個(gè)結(jié)點(diǎn)，然后下降去遍歷它的左子樹(shù)；遍歷完它的左子樹(shù)后，然后按它的右指針指示的地址再去遍歷該結(jié)點(diǎn)的右子樹(shù)。(P109)(P109)二叉樹(shù)類(lèi)二叉樹(shù)類(lèi)BinaryTreeBinaryTree實(shí)現(xiàn)：實(shí)現(xiàn)：template/非遞歸中序遍歷二叉樹(shù)或其子樹(shù)非遞歸中序遍歷二叉樹(shù)或其子樹(shù)void BinaryTree:InOrderWithoutRecusion( BinaryTreeNode* root )using std:stack;stack BinaryTreeNode* aStack; /棧中的結(jié)點(diǎn)為二叉樹(shù)結(jié)點(diǎn)指針棧中的結(jié)點(diǎn)為二叉樹(shù)結(jié)點(diǎn)指針BinaryTreeNode* pointer

24、= root;/保存輸入?yún)?shù)保存輸入?yún)?shù)while( !aStack.empty( ) | pointer )if( pointer )aStack.push( pointer );/當(dāng)前結(jié)點(diǎn)地址入棧當(dāng)前結(jié)點(diǎn)地址入棧pointer = pointer-leftchild();/當(dāng)前鏈接結(jié)構(gòu)指向左孩子當(dāng)前鏈接結(jié)構(gòu)指向左孩子else/左子樹(shù)訪(fǎng)問(wèn)完畢，轉(zhuǎn)向訪(fǎng)問(wèn)右子樹(shù)左子樹(shù)訪(fǎng)問(wèn)完畢，轉(zhuǎn)向訪(fǎng)問(wèn)右子樹(shù)pointer = aStack.top( );aStack.pop();/棧頂元素退棧棧頂元素退棧Visit(pointer-value();/訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)pointer = pointer-r

25、ightchild();/當(dāng)前鏈接結(jié)構(gòu)指向右孩子當(dāng)前鏈接結(jié)構(gòu)指向右孩子/end of if/end of while遇到一個(gè)結(jié)點(diǎn)，然后下降去遍歷它的左子樹(shù)；遍歷完它的左子樹(shù)后，然后按它的右指針指示的地址再去遍歷該結(jié)點(diǎn)的右子樹(shù)。以輸出結(jié)點(diǎn)的值作為訪(fǎng)問(wèn)結(jié)點(diǎn)的操作4 4 遍歷二叉樹(shù)遍歷二叉樹(shù)n 后續(xù)遍歷二叉樹(shù)的非遞歸實(shí)現(xiàn)比中序遍歷和前序遍歷都更復(fù)雜。請(qǐng)用示意圖描述用非遞歸方式對(duì)下圖所示的二叉樹(shù)進(jìn)行后序遍歷時(shí)棧的存儲(chǔ)情況及入棧、出棧操作序列。遇到一個(gè)結(jié)點(diǎn)，去遍歷它的左子樹(shù)；，而是要再按照它的右子樹(shù)指針?biāo)甘镜牡刂啡ケ闅v該結(jié)點(diǎn)的右子樹(shù)；。后序遍歷二叉樹(shù)的非遞歸實(shí)現(xiàn)方法后序遍歷二叉樹(shù)的非遞歸實(shí)現(xiàn)方法n 在

26、實(shí)現(xiàn)時(shí)，需要給棧中的每個(gè)結(jié)點(diǎn)加上一個(gè)，以便當(dāng)從棧頂取出一個(gè)結(jié)點(diǎn)時(shí)（），（）。n 約定特征位為時(shí)，表示已進(jìn)入該結(jié)點(diǎn)的左子樹(shù)，將從左子樹(shù)回來(lái)；特征位為時(shí)，表示已進(jìn)入該結(jié)點(diǎn)的右子樹(shù)，將從右子樹(shù)回來(lái)。可以。enum Tags Left, Right ;/結(jié)點(diǎn)的標(biāo)志結(jié)點(diǎn)的標(biāo)志(枚舉類(lèi)型枚舉類(lèi)型)，Left為為0，Right為為1template class StackElement/棧中的結(jié)點(diǎn)棧中的結(jié)點(diǎn)(非遞歸后續(xù)遍歷中用到的非遞歸后續(xù)遍歷中用到的)public:BinaryTreeNode* pointer;Tags tag;(P110)(P110)二叉樹(shù)類(lèi)二叉樹(shù)類(lèi)BinaryTreeBinaryTr

27、ee實(shí)現(xiàn)：實(shí)現(xiàn)：template/非遞歸后序遍歷二叉樹(shù)或其子樹(shù)非遞歸后序遍歷二叉樹(shù)或其子樹(shù)void BinaryTree:PostOrderWithoutRecusion( BinaryTreeNode* root )using std:stack;StackElement element;stack StackElement aStack;BinaryTreeNode* pointer;if （root= NULL) return;/空樹(shù)即返回空樹(shù)即返回else pointer = root;遇到一個(gè)結(jié)點(diǎn)，去遍歷它的左子樹(shù)；，而是要再按照它的右子樹(shù)指針?biāo)甘镜牡刂啡ケ闅v該結(jié)點(diǎn)的右子樹(shù)；。wh

28、ile( !aStack.empty() | pointer )while( pointer!=NULL )/進(jìn)入左子樹(shù)，直到左子樹(shù)中最下方的樹(shù)葉進(jìn)入左子樹(shù)，直到左子樹(shù)中最下方的樹(shù)葉element.pointer = pointer;element.tag = Left;aStack.push( element );pointer = pointer-leftchild();element = aStack.top( );/取出棧頂元素取出棧頂元素aStack.pop( ); /彈出棧頂元素彈出棧頂元素pointer = element.pointer;if (element.tag= Lef

29、t) /如果從左子樹(shù)回來(lái)如果從左子樹(shù)回來(lái)element.tag=Right; /則現(xiàn)在進(jìn)入右子樹(shù)則現(xiàn)在進(jìn)入右子樹(shù)aStack.push( element );pointer = pointer-rightchild();else /如果從右子樹(shù)回來(lái)如果從右子樹(shù)回來(lái)Visit( pointer-value(); /訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)pointer=NULL;/end of while( true )遇到一個(gè)結(jié)點(diǎn)，去遍歷它的左子樹(shù)；，而是要再按照它的右子樹(shù)指針?biāo)甘镜牡刂啡ケ闅v該結(jié)點(diǎn)的右子樹(shù)；。以輸出結(jié)點(diǎn)的值作為訪(fǎng)問(wèn)結(jié)點(diǎn)的操作2 2 廣度優(yōu)先搜索二叉樹(shù)廣度優(yōu)先搜索二叉樹(shù)：從二叉樹(shù)的第0層(即

30、根結(jié)點(diǎn))開(kāi)始，自上而下逐層遍歷，在同一層中按從左到右的順序?qū)Y(jié)點(diǎn)逐一訪(fǎng)問(wèn)。因此廣度優(yōu)先遍歷也稱(chēng)為。n 在進(jìn)行廣度優(yōu)先遍歷時(shí)，對(duì)二叉樹(shù)一層結(jié)點(diǎn)訪(fǎng)問(wèn)完成之后，要按照它們的訪(fǎng)問(wèn)次序?qū)Ω鱾€(gè)結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)按順序進(jìn)行訪(fǎng)問(wèn)。因此在進(jìn)行廣度優(yōu)先遍歷時(shí)，。請(qǐng)用示意圖描述用BFS對(duì)下圖所示的二叉樹(shù)進(jìn)行遍歷時(shí)隊(duì)列的存儲(chǔ)情況及入隊(duì)列、出隊(duì)列操作序列。(P112)(P112)二叉樹(shù)類(lèi)二叉樹(shù)類(lèi)BinaryTreeBinaryTree實(shí)現(xiàn)：實(shí)現(xiàn)：template /按層次遍歷二叉樹(shù)或其子樹(shù)按層次遍歷二叉樹(shù)或其子樹(shù)(即廣度優(yōu)先遍歷即廣度優(yōu)先遍歷)void BinaryTree:LevelOrder( BinaryTre

31、eNode* root )using std:queue;queue BinaryTreeNode* aQueue;BinaryTreeNode* pointer = root;if( pointer )/非空樹(shù)非空樹(shù)aQueue.push( pointer );while( !aQueue.empty( ) )pointer = aQueue.front( );aQueue.pop( );Visit( pointer-value();/訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)if( pointer-leftchild()!=NULL )aQueue.push( pointer-leftchild() );i

32、f( pointer-rightchild()!=NULL )aQueue.push( pointer-rightchild() );二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)n 二叉樹(shù)是一種(指)。針對(duì)二叉樹(shù)的各種應(yīng)用，在存儲(chǔ)器中有多種不同的表示二叉樹(shù)的方法(指)，這些方法都是(順序、鏈?zhǔn)健⑺饕?、哈?的組合應(yīng)用。1 1 用指針實(shí)現(xiàn)二叉樹(shù)用指針實(shí)現(xiàn)二叉樹(shù)：每個(gè)結(jié)點(diǎn)中除存儲(chǔ)結(jié)點(diǎn)本身的數(shù)據(jù)外還有。：在二叉鏈表的基礎(chǔ)上，在每個(gè)結(jié)點(diǎn)中再增加一個(gè)。有了指向父結(jié)點(diǎn)的指針，就給了的能力。2 2 用數(shù)組實(shí)現(xiàn)完全二叉樹(shù)用數(shù)組實(shí)現(xiàn)完全二叉樹(shù)n 在完全二叉樹(shù)中，所有結(jié)點(diǎn)可以按圖(b)所示的蛇形方式排列。n 因此，可以按存儲(chǔ)

33、完全二叉樹(shù)中的結(jié)點(diǎn)： ()將完全二叉樹(shù)中的每個(gè)結(jié)點(diǎn)按圖(b)所示的順序存儲(chǔ)在一片連續(xù)的存儲(chǔ)空間中。 ()根據(jù)結(jié)點(diǎn)序號(hào)推斷出父結(jié)點(diǎn)、左右子女結(jié)點(diǎn)、左右兄弟結(jié)點(diǎn)(見(jiàn)下頁(yè))。二叉搜索樹(shù)二叉搜索樹(shù)n 樹(shù)形結(jié)構(gòu)的一個(gè)重要應(yīng)用是用來(lái)(詳見(jiàn)后面的重要性質(zhì)2)，用適用于內(nèi)存儲(chǔ)器的一種重要的。(BST，Binary Search Tree)，也稱(chēng)“二叉排序樹(shù)”、“二叉查找樹(shù)”、“二叉檢索樹(shù)”等。其定義如下： 或者是一顆； 或者是具有下列性質(zhì)的二叉樹(shù)：對(duì)于任何一個(gè)結(jié)點(diǎn)，設(shè)其值為K，則；而且它的左右子樹(shù)也分別為二叉搜索樹(shù)。 說(shuō)明：此處的“小于”和“大于”可以。n 二叉搜索樹(shù)的定義是一種的定義。二叉搜索樹(shù)例子二叉搜索

34、樹(shù)例子n 設(shè)一棵二叉樹(shù)的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)關(guān)鍵碼，整棵二叉樹(shù)各結(jié)點(diǎn)對(duì)應(yīng)的關(guān)鍵碼組成一個(gè)。設(shè)一個(gè)關(guān)鍵碼集合K為： ，則下圖所示的二叉樹(shù)就是一棵二叉搜索樹(shù)。二叉搜索樹(shù)的重要性質(zhì)二叉搜索樹(shù)的重要性質(zhì)(1)(1)n 二叉搜索樹(shù)的：將各結(jié)點(diǎn)的值輸出來(lái)，將得到。將關(guān)鍵碼集合組織成二叉搜索樹(shù)，實(shí)際上起了，按中序遍歷二叉搜索樹(shù)就能得到排好的關(guān)鍵碼序列。n 例如，對(duì)下圖所示的BST進(jìn)行中序遍歷后得到的序列為：。二叉搜索樹(shù)的重要性質(zhì)二叉搜索樹(shù)的重要性質(zhì)(2)(2)n 二叉搜索樹(shù)的效率在于：從根結(jié)點(diǎn)開(kāi)始，在二叉搜索樹(shù)中檢索值K。 如果根結(jié)點(diǎn)儲(chǔ)存的值為K，則檢索結(jié)束。 如果K小于根結(jié)點(diǎn)的值，則。 如果K大于根結(jié)點(diǎn)的值，

35、就。n 這個(gè)過(guò)程一直持續(xù)到K被找到；或者在查找過(guò)程中，如果遇上樹(shù)葉仍沒(méi)有發(fā)現(xiàn)K，那么K就不在該二叉搜索樹(shù)中。n 設(shè)二叉搜索樹(shù)的，則其高度的數(shù)量級(jí)為，因此在BST中查找一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為；如果n為21010，則最多只需比較10次就能找到結(jié)點(diǎn)或者得出不存在的結(jié)論。而其他查找算法一般為。：二叉搜索樹(shù)抽象數(shù)據(jù)類(lèi)型：二叉搜索樹(shù)抽象數(shù)據(jù)類(lèi)型n 本題中設(shè)計(jì)的二叉搜索類(lèi)是，所以只需要為BST，主要是、和的操作。因?yàn)樾枰谥性L(fǎng)問(wèn)二叉樹(shù)結(jié)點(diǎn)類(lèi)的，所以需要在BinaryTreeNode類(lèi)中將BinarySearchTree類(lèi)，并在BinaryTreeNode類(lèi)提前申明BinarySearchTree類(lèi)。方法如下

36、：/提前聲明提前聲明BinaryTree類(lèi)和類(lèi)和BinarySearchTree類(lèi)類(lèi)template class BinaryTree;template class BinarySearchTree;templateclass BinaryTreeNode/二叉樹(shù)結(jié)點(diǎn)的抽象數(shù)據(jù)類(lèi)型二叉樹(shù)結(jié)點(diǎn)的抽象數(shù)據(jù)類(lèi)型friend class BinaryTree; /聲明二叉樹(shù)類(lèi)為結(jié)點(diǎn)類(lèi)的友元類(lèi)，便于訪(fǎng)問(wèn)私有數(shù)據(jù)聲明二叉樹(shù)類(lèi)為結(jié)點(diǎn)類(lèi)的友元類(lèi)，便于訪(fǎng)問(wèn)私有數(shù)據(jù)friend class BinarySearchTree;/聲明二叉搜索樹(shù)類(lèi)為結(jié)點(diǎn)類(lèi)的友元類(lèi)聲明二叉搜索樹(shù)類(lèi)為結(jié)點(diǎn)類(lèi)的友元類(lèi)(1) (1) 二叉搜索

37、樹(shù)的聲明二叉搜索樹(shù)的聲明#include .BinaryTreeBinaryTree.htemplate class BinarySearchTree : public BinaryTree public:BinarySearchTree( ) ;virtual BinarySearchTree( ) ;void InsertNode( BinaryTreeNode* root,/插入結(jié)點(diǎn)插入結(jié)點(diǎn)BinaryTreeNode* newpointer );void DeleteNode( BinaryTreeNode* pointer );/刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)void DeleteNodeEx(

38、BinaryTreeNode* pointer );/刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)(改進(jìn)改進(jìn))/查找結(jié)點(diǎn)值為查找結(jié)點(diǎn)值為t的結(jié)點(diǎn)，找到則返回其指針，否則返回的結(jié)點(diǎn)，找到則返回其指針，否則返回NULLBinaryTreeNode* Search( BinaryTreeNode* root, const T& t );(2) (2) 二叉搜索樹(shù)的實(shí)現(xiàn)二叉搜索樹(shù)的實(shí)現(xiàn)(1)(1)：插入結(jié)點(diǎn)：插入結(jié)點(diǎn)n 往二叉搜索樹(shù)里插入新結(jié)點(diǎn)，要保證插入后。將待插入結(jié)點(diǎn)的關(guān)鍵碼值與樹(shù)根的關(guān)鍵碼值比較，若待插入的關(guān)鍵碼值，則，；在子樹(shù)里又與子樹(shù)的根比較，如此進(jìn)行下去，直到把新結(jié)點(diǎn)插入到二叉樹(shù)里。二叉搜索樹(shù)的二叉搜索樹(shù)的n

39、 對(duì)于給定的關(guān)鍵碼集合，為建立二叉搜索樹(shù)，可以。template /插入結(jié)點(diǎn)插入結(jié)點(diǎn)(root為為BST的根結(jié)點(diǎn)的根結(jié)點(diǎn))void BinarySearchTree:InsertNode( BinaryTreeNode* root,BinaryTreeNode* newpointer )BinaryTreeNode* pointer = NULL;/初始化初始化if(root = NULL )/空樹(shù)空樹(shù)/用指針用指針newpointer初始化二叉搜索樹(shù)樹(shù)根，賦值實(shí)現(xiàn)初始化二叉搜索樹(shù)樹(shù)根，賦值實(shí)現(xiàn)Initialize( newpointer ); return;else pointer = ro

40、ot;while( 1 )if( newpointer-value=pointer-value )return;/相等則不用插入相等則不用插入else if( newpointer-valuevalue )/作為左子樹(shù)作為左子樹(shù)if( pointer-left=NULL )pointer-left = newpointer; return;else pointer = pointer-left;else/作為右子樹(shù)作為右子樹(shù)if( pointer-right=NULL )pointer-right = newpointer; return;else pointer = pointer-righ

41、t;將待插入結(jié)點(diǎn)的關(guān)鍵碼值與樹(shù)根的關(guān)鍵碼值比較，若待插入的關(guān)鍵碼值，則，；在子樹(shù)里又與子樹(shù)的根比較，如此進(jìn)行下去，直到把新結(jié)點(diǎn)插入到二叉樹(shù)里。二叉搜索樹(shù)的實(shí)現(xiàn)二叉搜索樹(shù)的實(shí)現(xiàn)(2) (2) ：刪除結(jié)點(diǎn)：刪除結(jié)點(diǎn)n 從二叉搜索樹(shù)里刪除一個(gè)結(jié)點(diǎn)時(shí)，不能把以這個(gè)結(jié)點(diǎn)為根的子樹(shù)都刪除掉，并且還要。設(shè)p、p1、r是指針變量，則刪除可以按如下規(guī)定進(jìn)行：，則；，則在左子樹(shù)里找按，然后。(即把p的右子樹(shù)下降為r的右子樹(shù))BSTBST刪除算法存在的刪除算法存在的n 在前面的算法中，有可能。(1) 若結(jié)點(diǎn)p沒(méi)有左子樹(shù)，則用右子樹(shù)的根代替被刪除的結(jié)點(diǎn)p；(2) 若結(jié)點(diǎn)p有左子樹(shù)，則在左子樹(shù)里找按中序遍歷的最后一個(gè)結(jié)

42、點(diǎn)r，并將其刪除,由于此結(jié)點(diǎn)r沒(méi)有右子樹(shù),因此刪除此結(jié)點(diǎn)r只需用其左子樹(shù)替代之, 然后。二叉樹(shù)刪除結(jié)點(diǎn)二叉樹(shù)刪除結(jié)點(diǎn)的實(shí)現(xiàn)的實(shí)現(xiàn)template /二叉搜索樹(shù)刪除結(jié)點(diǎn)的算法二叉搜索樹(shù)刪除結(jié)點(diǎn)的算法(改進(jìn)改進(jìn))void BinarySearchTree:DeleteNodeEx( BinaryTreeNode* pointer )/如果帶刪除結(jié)點(diǎn)不存在如果帶刪除結(jié)點(diǎn)不存在,返回返回if( pointer = NULL )return;BinaryTreeNode * temppointer;/保存要替換上來(lái)的結(jié)點(diǎn)保存要替換上來(lái)的結(jié)點(diǎn)BinaryTreeNode * tempparent = NU

43、LL;/保存要替換上來(lái)的結(jié)點(diǎn)的父結(jié)點(diǎn)保存要替換上來(lái)的結(jié)點(diǎn)的父結(jié)點(diǎn)/保存要?jiǎng)h除結(jié)點(diǎn)的父結(jié)點(diǎn)保存要?jiǎng)h除結(jié)點(diǎn)的父結(jié)點(diǎn)BinaryTreeNode * parent = Parent( pointer );/如果待刪除結(jié)點(diǎn)的左子樹(shù)為空如果待刪除結(jié)點(diǎn)的左子樹(shù)為空,就將它的右子樹(shù)代替它即可就將它的右子樹(shù)代替它即可if( pointer-leftchild() = NULL )temppointer=pointer-rightchild();else /當(dāng)待刪除結(jié)點(diǎn)左子樹(shù)不為空當(dāng)待刪除結(jié)點(diǎn)左子樹(shù)不為空,就在左子樹(shù)中尋找最大結(jié)點(diǎn)替換待刪除結(jié)點(diǎn)就在左子樹(shù)中尋找最大結(jié)點(diǎn)替換待刪除結(jié)點(diǎn)temppointer=poi

44、nter-leftchild(); while (temppointer-rightchild()!=NULL) tempparent=temppointer; temppointer=temppointer-rightchild();(1)若結(jié)點(diǎn)若結(jié)點(diǎn)p沒(méi)有左子樹(shù)，則用右子樹(shù)沒(méi)有左子樹(shù)，則用右子樹(shù)的根代替被刪除的結(jié)點(diǎn)的根代替被刪除的結(jié)點(diǎn)p(2)若結(jié)點(diǎn)若結(jié)點(diǎn)p有左子樹(shù)，則在左子樹(shù)里有左子樹(shù)，則在左子樹(shù)里找按中序遍歷的最后一個(gè)結(jié)點(diǎn)找按中序遍歷的最后一個(gè)結(jié)點(diǎn)r，并將其刪除并將其刪除,由于此結(jié)點(diǎn)由于此結(jié)點(diǎn)r沒(méi)有右子沒(méi)有右子樹(shù)樹(shù),因此刪除此結(jié)點(diǎn)因此刪除此結(jié)點(diǎn)r只需用其左子只需用其左子樹(shù)替代之樹(shù)替代之,

45、 然后然后。/刪除替換結(jié)點(diǎn)刪除替換結(jié)點(diǎn)if( tempparent=NULL ) pointer-left = temppointer-leftchild();else tempparent-right = temppointer-leftchild();temppointer-left=pointer-leftchild();temppointer-right=pointer-rightchild();/用替換結(jié)點(diǎn)去替代真正的刪除結(jié)點(diǎn)用替換結(jié)點(diǎn)去替代真正的刪除結(jié)點(diǎn)if( parent=NULL ) root = temppointer;else if( parent-leftchild()

46、= pointer ) parent-left = temppointer;else parent-right = temppointer;delete pointer; pointer = NULL;return;(1)若結(jié)點(diǎn)若結(jié)點(diǎn)p沒(méi)有左子樹(shù)，則用右子樹(shù)沒(méi)有左子樹(shù)，則用右子樹(shù)的根代替被刪除的結(jié)點(diǎn)的根代替被刪除的結(jié)點(diǎn)p(2)若結(jié)點(diǎn)若結(jié)點(diǎn)p有左子樹(shù)，則在左子樹(shù)里有左子樹(shù)，則在左子樹(shù)里找按中序遍歷的最后一個(gè)結(jié)點(diǎn)找按中序遍歷的最后一個(gè)結(jié)點(diǎn)r，并將其刪除并將其刪除,由于此結(jié)點(diǎn)由于此結(jié)點(diǎn)r沒(méi)有右子沒(méi)有右子樹(shù)樹(shù),因此刪除此結(jié)點(diǎn)因此刪除此結(jié)點(diǎn)r只需用其左子只需用其左子樹(shù)替代之樹(shù)替代之, 然后然后。7 7

47、堆與優(yōu)先隊(duì)列堆與優(yōu)先隊(duì)列：是一種。：是一種，可以用堆來(lái)實(shí)現(xiàn)。1 1 最大堆和最小堆最大堆和最小堆(MinHeap)的定義：最小值堆是一個(gè) ，它具有如下性質(zhì)：12, 1 , 02212niKKKKiiiin 堆實(shí)質(zhì)上，此完全二叉樹(shù)的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)，根結(jié)點(diǎn)對(duì)應(yīng)關(guān)鍵碼。的特性在此完全二叉樹(shù)里解釋為：。n 根結(jié)點(diǎn)是完全二叉樹(shù)中關(guān)鍵碼值最小的結(jié)點(diǎn)，也就是堆中的最小元素。12, 1 , 02212niKKKKiiii堆的創(chuàng)建堆的創(chuàng)建( (如何建堆如何建堆) )篩選法篩選法(Floyd, 1964)(Floyd, 1964)n 首先(此時(shí)的完全二叉樹(shù)并不具備堆的特性)。顯然，所有 的結(jié)點(diǎn) 都沒(méi)有子女結(jié)點(diǎn)，

48、因此以這樣的 為根的子樹(shù)都，然后從 的結(jié)點(diǎn) 開(kāi)始，逐步把以 為根的子樹(shù)排成堆，直到以為 根的樹(shù)排成堆，就完成了建堆的過(guò)程。12niiK12niiKiK,322212nnnKKK0K考慮將以為根的子樹(shù)排成堆時(shí)，以、為根的子樹(shù)已經(jīng)是堆，所以這時(shí)如果有和，則不必改變?nèi)魏谓Y(jié)點(diǎn)的位置，以為根的子樹(shù)就已經(jīng)是堆；否則要適當(dāng)調(diào)整子樹(shù)中的結(jié)點(diǎn)的位置以滿(mǎn)足堆的定義。由于的左、右子樹(shù)都已經(jīng)是堆，根結(jié)點(diǎn)是堆中最小的結(jié)點(diǎn)，所以調(diào)整后的值必定是原來(lái)和中較小的一個(gè)。不妨假定較小，將與交換位置，這樣調(diào)整后和，并且以為根的子樹(shù)原來(lái)已經(jīng)是堆，不必再做任何調(diào)整，只有以為根的子樹(shù)由于的值發(fā)生變化(與交換了)，所以有可能不滿(mǎn)足堆的定義

49、(但的左右子樹(shù)都已經(jīng)是堆)。這時(shí)可重復(fù)上述過(guò)程，考慮將以為根的子樹(shù)排成堆。如此一層層遞推下去，最多可能進(jìn)行到樹(shù)葉。注意：由于每步保證將子樹(shù)最小的結(jié)點(diǎn)交換到子樹(shù)的根結(jié)點(diǎn)，所以。它就像一樣，把最小的關(guān)鍵碼一層層地選擇出來(lái)，因此這種構(gòu)造最小堆的方法稱(chēng)為。此前的連續(xù)4幅圖說(shuō)明了對(duì)于關(guān)鍵碼集合：用篩選法建堆的過(guò)程，其中n = 8， = 3，所以從K3 = 23開(kāi)始。12n堆的操作堆的操作操作是。n 插入和刪除操作都必須滿(mǎn)足一個(gè)：，即插入結(jié)點(diǎn)或刪除結(jié)點(diǎn)后，仍然滿(mǎn)足堆的性質(zhì)。n 堆的：將被插入的結(jié)點(diǎn)放在堆在最后位置，然后調(diào)整。堆的操作堆的操作n 從堆中刪除一個(gè)結(jié)點(diǎn)，往往是刪除根結(jié)點(diǎn)。(或)的為：用堆中最后一

50、個(gè)結(jié)點(diǎn)代替根結(jié)點(diǎn)(或其他被刪除的結(jié)點(diǎn))，然后調(diào)整。2 2 優(yōu)先隊(duì)列優(yōu)先隊(duì)列n 優(yōu)先隊(duì)列是這樣一種數(shù)據(jù)結(jié)構(gòu)。STLSTL中的優(yōu)先隊(duì)列中的優(yōu)先隊(duì)列n 包含：#include n 使用：using namespace std;的方法：priority_queue q1; /優(yōu)先隊(duì)列中的結(jié)點(diǎn)為整型數(shù)據(jù); /優(yōu)先隊(duì)列中的結(jié)點(diǎn)為自定義類(lèi)node對(duì)象：優(yōu)先隊(duì)列和隊(duì)列的使用方法基本一致。但要注意，因?yàn)閮?yōu)先隊(duì)列需要，因此，如果優(yōu)先隊(duì)列中的結(jié)點(diǎn)是自定義類(lèi)對(duì)象，則在該類(lèi)中，以實(shí)現(xiàn)結(jié)點(diǎn)的大小比較運(yùn)算。8 Huffman8 Huffman編碼樹(shù)編碼樹(shù)n 電影風(fēng)聲中的鏡頭(1:47:00開(kāi)始)摩爾斯編碼。編碼與摩爾斯編碼編碼與摩爾斯編碼：將電報(bào)中的字符表示成通信系統(tǒng)可以識(shí)別的信號(hào)。：采用變長(zhǎng)的來(lái)代表字符。n 影視劇中發(fā)電報(bào)：劃（ ）和點(diǎn)（ ），或分別叫嗒（Dah）和滴（Dit），或長(zhǎng)和短。加權(quán)平均編碼長(zhǎng)度最短的編碼方案。：對(duì)，為8位。n 現(xiàn)已知在英語(yǔ)語(yǔ)言中26個(gè)字母(不區(qū)分大小寫(xiě))出現(xiàn)的如下表所示