第5章二叉樹(1)

1、2022-4-11數據結構與算法數據結構與算法第第5 5章章 二叉樹二叉樹朱凌朱凌 2022-4-11二叉樹知識點二叉樹知識點1 1 2 2 3 4 1 2 5 1 2 3 4 6 7 8 線性結構、樹形結構、圖結構線性結構、樹形結構、圖結構復習n 數據的邏輯結構可以表示為和： K：。 R：K。 R是KK上的二元關系。：唯一前驅、唯一后繼，反映一種關系。：唯一前驅、多個后繼，反映一種關系。：不限制前驅的個數，也不限制后繼的個數，反映一種關系。樹與子樹樹與子樹n 一棵樹可以分成幾個大的分支（稱為），每個大分支再分成幾個小分支，小分支再分成更小的分支，。二叉樹二叉樹n 二叉樹是一種，特殊在于： 每

2、個結點最多(稱為)，也就是說每個結點的子女結點為0個、1個或2個； 兩個子女結點，即使只有1個子女結點，也要區(qū)分為是左子女結點還是右子女結點。1 1 二叉樹的概念二叉樹的概念n 通常用來描述中的一些概念。：若在樹中存在從結點k指向結點k的連線，則稱k是k的(parent，也稱，或簡稱為)，而k是k的(child，也稱，或簡稱為)。樹的：沒有父結點的結點稱為樹的(root)。：若有k指向k和k指向k，則稱k和k互為(sibling)。：父結點指向子女結點的連線，稱為(edge)。可以認為，由父結點指向子女結點。：若存在結點序列k0, k1, , ks，使得, , , 都是樹中的邊，則該結點序列稱

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

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

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

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

7、包括結點類和二叉樹類。：二叉樹的抽象數據類型：二叉樹的抽象數據類型提供：結點的數據域info。：豐富的構造函數、返回和設置左右子女結點指針、返回和設置結點的數據域、判斷結點是否為樹葉等。提供：二叉樹根結點root。：豐富的構造函數、析構函數、判斷二叉樹是否為空樹、返回二叉樹的根結點、獲取當前結點的父結點、獲取當前結點的左兄弟或右兄弟、豐富的遍歷函數等。二叉樹結點類二叉樹結點類BinaryTreeNodeBinaryTreeNode/聲明聲明BinaryTree類，因為在類，因為在BinaryTreeNode類中用到了標識符類中用到了標識符BinaryTreetemplate class Bin

8、aryTree;templateclass BinaryTreeNode/二叉樹結點的抽象數據類型二叉樹結點的抽象數據類型friend class BinaryTree;/聲明二叉樹類為結點類的友元類聲明二叉樹類為結點類的友元類,便于訪問私有數據成員便于訪問私有數據成員private:T info;/二叉樹結點數據域二叉樹結點數據域/實現時，可以補充結點的左子結點、右子結點指針作為數據成員實現時，可以補充結點的左子結點、右子結點指針作為數據成員public:BinaryTreeNode( );/缺省構造函數缺省構造函數BinaryTreeNode( const T& ele );/給定

9、數據的構造函數給定數據的構造函數/給定了結點值和左右子樹的構造函數給定了結點值和左右子樹的構造函數BinaryTreeNode( const T& ele, BinaryTreeNode *l, BinaryTreeNode *r );T value( ) const;/返回當前結點的數據返回當前結點的數據BinaryTreeNode* leftchild( ) const;/返回當前結點的左子樹指針返回當前結點的左子樹指針BinaryTreeNode* rightchild( ) const;/返回當前結點的右子樹指針返回當前結點的右子樹指針void setLeftchild( Bi

10、naryTreeNode* L );/設置當前結點的左子樹指針設置當前結點的左子樹指針void setRightchild( BinaryTreeNode* R );/設置當前結點的右子樹指針設置當前結點的右子樹指針void setValue( const T& val );/設置當前結點的數據域設置當前結點的數據域bool isLeaf( ) const;/判定當前結點是否為葉結點，若是則返回判定當前結點是否為葉結點，若是則返回trueBinaryTreeNode &operator=(const BinaryTreeNode & Node);二叉樹類二叉樹類Bina

11、ryTreeBinaryTreetemplateclass BinaryTree/二叉樹的抽象數據類型二叉樹的抽象數據類型protected:BinaryTreeNode* root;/二叉樹根結點二叉樹根結點public:BinaryTree( ) root = NULL; /缺省構造函數缺省構造函數BinaryTree( ) DeleteBinaryTree( root ); /析構函數析構函數bool isEmpty( ) ;/判定二叉樹是否為空樹判定二叉樹是否為空樹BinaryTreeNode* Root( ) return root; /返回二叉樹根結點返回二叉樹根結點/返回返回cu

12、rrent結點的父結點結點的父結點BinaryTreeNode* Parent( BinaryTreeNode * current );/返回返回current結點的左兄弟結點的左兄弟BinaryTreeNode* LeftSibling( BinaryTreeNode * current );/返回返回current結點的右兄弟結點的右兄弟BinaryTreeNode* RightSibling( BinaryTreeNode * current );/以以val作為根結點，作為根結點，leftTree作為樹的左子樹，作為樹的左子樹，rightTree作為樹的右子樹作為樹的右子樹/構造一棵新

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

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

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

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

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

18、訪問當前結點訪問當前結點PreOrder( root-leftchild() ); /訪問左子樹訪問左子樹PreOrder( root-rightchild() );/訪問右子樹訪問右子樹template/遞歸中序遍歷二叉樹或其子樹遞歸中序遍歷二叉樹或其子樹void BinaryTree:InOrder( BinaryTreeNode* root )if( root!=NULL )InOrder( root-leftchild() );/訪問左子樹訪問左子樹Visit(root-Value(); /訪問當前結點訪問當前結點InOrder( root-rightchild() ); /訪問右子樹

19、訪問右子樹template/遞歸后序遍歷二叉樹或其子樹遞歸后序遍歷二叉樹或其子樹void BinaryTree:PostOrder( BinaryTreeNode* root )if( root!=NULL )PostOrder( root-leftchild() );/訪問左子樹訪問左子樹PostOrder( root-rightchild() );/訪問右子樹訪問右子樹Visit(root-Value(); /訪問當前結點訪問當前結點2 2 遍歷二叉樹遍歷二叉樹n 棧是實現遞歸的最常用的數據結構，所以對于遞歸定義的二叉樹遍歷運算，最自然的是，。n 使用棧的算法很簡單。請用示意圖描述用非遞歸

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

21、ryTreeNode* root )using std:stack;stack BinaryTreeNode* aStack; /棧中的結點為二叉樹結點指針棧中的結點為二叉樹結點指針BinaryTreeNode* pointer = root;/保存輸入參數保存輸入參數aStack.push(NULL);while( pointer )Visit(pointer-Value(); /訪問當前結點訪問當前結點if( pointer-rightchild()!=NULL )aStack.push( pointer-rightchild() );/非空右孩子入棧非空右孩子入棧 if( pointer

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

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

24、= root;/保存輸入參數保存輸入參數while( !aStack.empty( ) | pointer )if( pointer )aStack.push( pointer );/當前結點地址入棧當前結點地址入棧pointer = pointer-leftchild();/當前鏈接結構指向左孩子當前鏈接結構指向左孩子else/左子樹訪問完畢，轉向訪問右子樹左子樹訪問完畢，轉向訪問右子樹pointer = aStack.top( );aStack.pop();/棧頂元素退棧棧頂元素退棧Visit(pointer-value();/訪問當前結點訪問當前結點pointer = pointer-r

25、ightchild();/當前鏈接結構指向右孩子當前鏈接結構指向右孩子/end of if/end of while遇到一個結點，然后下降去遍歷它的左子樹；遍歷完它的左子樹后，然后按它的右指針指示的地址再去遍歷該結點的右子樹。以輸出結點的值作為訪問結點的操作4 4 遍歷二叉樹遍歷二叉樹n 后續(xù)遍歷二叉樹的非遞歸實現比中序遍歷和前序遍歷都更復雜。請用示意圖描述用非遞歸方式對下圖所示的二叉樹進行后序遍歷時棧的存儲情況及入棧、出棧操作序列。遇到一個結點，去遍歷它的左子樹；，而是要再按照它的右子樹指針所指示的地址去遍歷該結點的右子樹；。后序遍歷二叉樹的非遞歸實現方法后序遍歷二叉樹的非遞歸實現方法n 在

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

27、ee實現：實現：template/非遞歸后序遍歷二叉樹或其子樹非遞歸后序遍歷二叉樹或其子樹void BinaryTree:PostOrderWithoutRecusion( BinaryTreeNode* root )using std:stack;StackElement element;stack StackElement aStack;BinaryTreeNode* pointer;if （root= NULL) return;/空樹即返回空樹即返回else pointer = root;遇到一個結點，去遍歷它的左子樹；，而是要再按照它的右子樹指針所指示的地址去遍歷該結點的右子樹；。wh

28、ile( !aStack.empty() | pointer )while( pointer!=NULL )/進入左子樹，直到左子樹中最下方的樹葉進入左子樹，直到左子樹中最下方的樹葉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) /如果從左子樹回來如果從左子樹回來element.tag=Right; /則現在進入右子樹則現在進入右子樹aStack.push( element );pointer = pointer-rightchild();else /如果從右子樹回來如果從右子樹回來Visit( pointer-value(); /訪問當前結點訪問當前結點pointer=NULL;/end of while( true )遇到一個結點，去遍歷它的左子樹；，而是要再按照它的右子樹指針所指示的地址去遍歷該結點的右子樹；。以輸出結點的值作為訪問結點的操作2 2 廣度優(yōu)先搜索二叉樹廣度優(yōu)先搜索二叉樹：從二叉樹的第0層(即

30、根結點)開始，自上而下逐層遍歷，在同一層中按從左到右的順序對結點逐一訪問。因此廣度優(yōu)先遍歷也稱為。n 在進行廣度優(yōu)先遍歷時，對二叉樹一層結點訪問完成之后，要按照它們的訪問次序對各個結點的左子樹和右子樹按順序進行訪問。因此在進行廣度優(yōu)先遍歷時，。請用示意圖描述用BFS對下圖所示的二叉樹進行遍歷時隊列的存儲情況及入隊列、出隊列操作序列。(P112)(P112)二叉樹類二叉樹類BinaryTreeBinaryTree實現：實現：template /按層次遍歷二叉樹或其子樹按層次遍歷二叉樹或其子樹(即廣度優(yōu)先遍歷即廣度優(yōu)先遍歷)void BinaryTree:LevelOrder( BinaryTre

31、eNode* root )using std:queue;queue BinaryTreeNode* aQueue;BinaryTreeNode* pointer = root;if( pointer )/非空樹非空樹aQueue.push( pointer );while( !aQueue.empty( ) )pointer = aQueue.front( );aQueue.pop( );Visit( pointer-value();/訪問當前結點訪問當前結點if( pointer-leftchild()!=NULL )aQueue.push( pointer-leftchild() );i

32、f( pointer-rightchild()!=NULL )aQueue.push( pointer-rightchild() );二叉樹的存儲結構二叉樹的存儲結構n 二叉樹是一種(指)。針對二叉樹的各種應用，在存儲器中有多種不同的表示二叉樹的方法(指)，這些方法都是(順序、鏈式、索引、哈希)的組合應用。1 1 用指針實現二叉樹用指針實現二叉樹：每個結點中除存儲結點本身的數據外還有。：在二叉鏈表的基礎上，在每個結點中再增加一個。有了指向父結點的指針，就給了的能力。2 2 用數組實現完全二叉樹用數組實現完全二叉樹n 在完全二叉樹中，所有結點可以按圖(b)所示的蛇形方式排列。n 因此，可以按存儲

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

34、樹例子n 設一棵二叉樹的每個結點對應一個關鍵碼，整棵二叉樹各結點對應的關鍵碼組成一個。設一個關鍵碼集合K為： ，則下圖所示的二叉樹就是一棵二叉搜索樹。二叉搜索樹的重要性質二叉搜索樹的重要性質(1)(1)n 二叉搜索樹的：將各結點的值輸出來，將得到。將關鍵碼集合組織成二叉搜索樹，實際上起了，按中序遍歷二叉搜索樹就能得到排好的關鍵碼序列。n 例如，對下圖所示的BST進行中序遍歷后得到的序列為：。二叉搜索樹的重要性質二叉搜索樹的重要性質(2)(2)n 二叉搜索樹的效率在于：從根結點開始，在二叉搜索樹中檢索值K。 如果根結點儲存的值為K，則檢索結束。 如果K小于根結點的值，則。 如果K大于根結點的值，

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

36、：/提前聲明提前聲明BinaryTree類和類和BinarySearchTree類類template class BinaryTree;template class BinarySearchTree;templateclass BinaryTreeNode/二叉樹結點的抽象數據類型二叉樹結點的抽象數據類型friend class BinaryTree; /聲明二叉樹類為結點類的友元類，便于訪問私有數據聲明二叉樹類為結點類的友元類，便于訪問私有數據friend class BinarySearchTree;/聲明二叉搜索樹類為結點類的友元類聲明二叉搜索樹類為結點類的友元類(1) (1) 二叉搜索

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

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

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

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

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

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

43、LL;/保存要替換上來的結點的父結點保存要替換上來的結點的父結點/保存要刪除結點的父結點保存要刪除結點的父結點BinaryTreeNode * parent = Parent( pointer );/如果待刪除結點的左子樹為空如果待刪除結點的左子樹為空,就將它的右子樹代替它即可就將它的右子樹代替它即可if( pointer-leftchild() = NULL )temppointer=pointer-rightchild();else /當待刪除結點左子樹不為空當待刪除結點左子樹不為空,就在左子樹中尋找最大結點替換待刪除結點就在左子樹中尋找最大結點替換待刪除結點temppointer=poi

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

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

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

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

48、因此以這樣的 為根的子樹都，然后從 的結點 開始，逐步把以 為根的子樹排成堆，直到以為 根的樹排成堆，就完成了建堆的過程。12niiK12niiKiK,322212nnnKKK0K考慮將以為根的子樹排成堆時，以、為根的子樹已經是堆，所以這時如果有和，則不必改變任何結點的位置，以為根的子樹就已經是堆；否則要適當調整子樹中的結點的位置以滿足堆的定義。由于的左、右子樹都已經是堆，根結點是堆中最小的結點，所以調整后的值必定是原來和中較小的一個。不妨假定較小，將與交換位置，這樣調整后和，并且以為根的子樹原來已經是堆，不必再做任何調整，只有以為根的子樹由于的值發(fā)生變化(與交換了)，所以有可能不滿足堆的定義

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

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