數(shù)據(jù)結(jié)構(gòu)：樹(shù)和森林

第6章 樹(shù)和森林非線性數(shù)據(jù)結(jié)構(gòu)實(shí)際中有許多樹(shù)型結(jié)構(gòu)的問(wèn)題，用樹(shù)型數(shù)據(jù)結(jié)構(gòu)來(lái)解決非常自然樹(shù)型結(jié)構(gòu)在計(jì)算機(jī)領(lǐng)域的應(yīng)用非常廣泛6.1樹(shù)和森林的概念樹(shù)的定義： 樹(shù)是由n(n>=0)個(gè)結(jié)點(diǎn)組成的有限集合。若n=0則稱為空樹(shù)， 否則： （1）有一個(gè)特定的稱之為根(root)的結(jié)點(diǎn)，它只有直接后繼， 但沒(méi)有直接前驅(qū)； （2）除根以外的其他結(jié)點(diǎn)可劃分為若干個(gè)互不相交的有限集合， 每個(gè)集合又是一棵樹(shù)，并且稱之為根的子樹(shù)(subTree)。每 棵子樹(shù)的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或多 個(gè)直接后繼。11/22/20221樹(shù)的示意圖：根結(jié)點(diǎn)根結(jié)點(diǎn)葉結(jié)點(diǎn)分支結(jié)點(diǎn)子樹(shù)子樹(shù)子樹(shù)Level0Level1Level2Level3結(jié)點(diǎn)的層次11/22/20222樹(shù)的基本術(shù)語(yǔ)結(jié)點(diǎn)的度(degree)：結(jié)點(diǎn)所擁有的子樹(shù)數(shù)目子女(child)結(jié)點(diǎn)：簡(jiǎn)稱子結(jié)點(diǎn)雙親(parent)結(jié)點(diǎn)：簡(jiǎn)稱父結(jié)點(diǎn)(father)兄弟(sibling)結(jié)點(diǎn)：具有同一個(gè)父結(jié)點(diǎn)的結(jié)點(diǎn)根(root)結(jié)點(diǎn)：分支(branch)結(jié)點(diǎn)：又稱非終端結(jié)點(diǎn)葉(leaf)結(jié)點(diǎn)：又稱終端結(jié)點(diǎn)結(jié)點(diǎn)的層次(level):根結(jié)點(diǎn)的層次為0，子結(jié)點(diǎn)的層次等于其父結(jié) 點(diǎn)的層次加一樹(shù)的高度(depth):等于樹(shù)中最大的結(jié)點(diǎn)層次數(shù)?？諛?shù)的高度為－1樹(shù)的度(degree):等于樹(shù)中最大的結(jié)點(diǎn)度數(shù)有序樹(shù)：樹(shù)中結(jié)點(diǎn)的各子樹(shù)之間的先后次序是有意義的，不能互換， 否則就成為另一棵樹(shù)了。無(wú)序樹(shù)：樹(shù)中結(jié)點(diǎn)的各子樹(shù)之間的先后次序無(wú)意義，可以互換森林(forest):若干棵樹(shù)的集合11/22/202236.2二叉樹(shù)(BinaryTree)二叉樹(shù)是樹(shù)的基礎(chǔ)，一般的樹(shù)可以轉(zhuǎn)化為二叉樹(shù)來(lái)處理。6.2.1二叉樹(shù)的定義 一棵二叉樹(shù)是一有限結(jié)點(diǎn)的集合，該集合或者為空（空二叉樹(shù)），或者是由一個(gè)根結(jié)點(diǎn)及其下的兩棵互不相交的子二叉樹(shù)構(gòu)成，其中左邊的稱為左子樹(shù)，右邊的稱為右子樹(shù)。 二叉樹(shù)是一棵度數(shù)<=2的有序樹(shù)。6.2.2二叉樹(shù)的性質(zhì)

（1）二叉樹(shù)的第i層的結(jié)點(diǎn)數(shù)<= （2）高度為k的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)＝(k>=-1)滿二叉樹(shù)(FullBinaryTree)：葉結(jié)點(diǎn)在同一層，非葉結(jié)點(diǎn)的度數(shù)均 為2的二叉樹(shù)（參見(jiàn)圖6.3a）完全二叉樹(shù)(CompleteBinaryTree)：

按從上到下、從左到右順序 編號(hào)一棵滿二叉樹(shù)，并按從大到小的順序連續(xù)刪除 該滿二叉樹(shù)的若干個(gè)結(jié)點(diǎn)后剩下的二叉樹(shù)稱為一棵 完全二叉樹(shù)（參見(jiàn)圖6.3b）2i2k+1-111/22/20224完全二叉樹(shù)的性質(zhì)和順序存儲(chǔ)結(jié)構(gòu)（1）具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度=log2(n+1)–1（2）若將一棵按前述原則編號(hào)的完全二叉樹(shù)，按其編號(hào)順序存入一 個(gè)一維數(shù)組中，則有：

結(jié)點(diǎn)i的左子結(jié)點(diǎn)下標(biāo)=2*i+1<n

結(jié)點(diǎn)i的右子結(jié)點(diǎn)下標(biāo)=2*i+2<n

結(jié)點(diǎn)i的父結(jié)點(diǎn)下標(biāo)=(i–1)/2的下取整值

另外注意：根結(jié)點(diǎn)（下標(biāo)為0）無(wú)父結(jié)點(diǎn) 由上可知，完全二叉樹(shù)的父——左子、父——右子之間的關(guān)系可以通過(guò)相應(yīng)結(jié)點(diǎn)的下標(biāo)之間的簡(jiǎn)單數(shù)學(xué)關(guān)系完全地表示 出來(lái)，因此可以采用順序存儲(chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)完全二叉樹(shù)。（參見(jiàn) 教材6.3.1數(shù)組表示） 順序存儲(chǔ)結(jié)構(gòu)用于動(dòng)態(tài)性較小的完全二叉樹(shù)的存儲(chǔ)不失為 一種簡(jiǎn)單有效的方法，但不通用。樹(shù)型數(shù)據(jù)結(jié)構(gòu)一般采用鏈?zhǔn)酱鎯?chǔ)方式來(lái)存儲(chǔ)。11/22/202256.3.2二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——二叉（三叉）鏈表結(jié)構(gòu)二叉鏈表結(jié)構(gòu)：左子指針數(shù)據(jù)元素右子指針三叉鏈表結(jié)構(gòu)：

左子指針數(shù)據(jù)元素右子指針 父指針 leftChilddatarightChildleftChilddatafatherrightChild11/22/20226二叉鏈表結(jié)構(gòu)的二叉樹(shù)結(jié)點(diǎn)（簡(jiǎn)稱二叉樹(shù)結(jié)點(diǎn)）的類定義：template<classType>classBinaryTree;//二叉樹(shù)類聲明template<classType>classBinTreeNode//二叉樹(shù)結(jié)點(diǎn)類定義{

friendclassBinaryTree<Type>;//二叉樹(shù)類是二叉樹(shù)結(jié)點(diǎn)類的友元

public:

BinTreeNode():leftChild(NULL),rightChild(NULL){} //構(gòu)造函數(shù)

BinTreeNode(Typeitem,BinTreeNode<Type>*left=NULL,

BinTreeNode<Type>*right=NULL):data(item),

leftChild(left),rightChild(right){}//構(gòu)造函數(shù) …//其他成員函數(shù)

private:

BinTreeNode<Type>*leftChild,*rightChild; //左子指針、右子指針

Typedata;//數(shù)據(jù)元素}11/22/20227二叉鏈表結(jié)構(gòu)的二叉樹(shù)的類定義template<classType>classBinaryTree{ public:

BinaryTree():root(NULL){}//創(chuàng)建一棵空二叉樹(shù)

BinaryTree(Typevalue):RefValue(value),root(NULL){} virtual~BinaryTree(){destroy(root)}//刪除一棵二叉樹(shù)

virtualintIsEmpty(){returnroot==NULL;}//判樹(shù)空

virtualBinTreeNode<Type>*Parent(BinTreeNode<Type>*current){returnroot==NULL||root==current?NULL: Parent(root,current);}//求*current結(jié)點(diǎn)的父結(jié)點(diǎn)指針

virtualBinTreeNode<Type>*LeftChild(BinTreeNode<Type> *current){returncurrent!=NULL?Current->leftChild:NULL;} //求*current結(jié)點(diǎn)的左子結(jié)點(diǎn)指針

virtualBinTreeNode<Type>*RightChild(BinTreeNode<Type>*current){returncurrent!=NULL?Current->rightChild:NULL;} //求*current結(jié)點(diǎn)的右子結(jié)點(diǎn)指針11/22/20228

virtualintInsert(constType&item);//插入值為item的新結(jié)點(diǎn)

virtualintFind(constType&item)const;//查找值為item的結(jié)點(diǎn)

constBinTreeNode<Type>*GetRoot()const{returnroot;} //求根結(jié)點(diǎn)的指針

friendistream&operator>>(istream&in,BinTreeNode<Type>&Tree);

//重載操作：輸入數(shù)據(jù)元素并建立一棵二叉樹(shù)Tree friendostream&operator<<(ostream&out,BinTreeNode<Type>&Tree);

//重載操作：輸出一棵二叉樹(shù)TreePrivate:

BinTreeNode<Type>*root;//根結(jié)點(diǎn)指針

TypeRefValue;//數(shù)據(jù)輸入結(jié)束標(biāo)志，僅用于輸入

BinTreeNode<Type>*Parent(BinTreeNode<Type>*start,

BinTreeNode<Type>*current); //求start樹(shù)中*current結(jié)點(diǎn)的父結(jié)點(diǎn)指針

intInsert(BinTreeNode<Type>*¤t,constType&item); //在current樹(shù)中插入值為item的新結(jié)點(diǎn)

voidTraverse(BinTreeNode<Type>*current,ostream&out)const; //遍歷輸出current二叉樹(shù)

intFind(BinTreeNode<Type>*current,constType&item)const; //在current樹(shù)中查找值為item的結(jié)點(diǎn)

voiddestroy((BinTreeNode<Type>*current); //刪除current樹(shù)的所有結(jié)點(diǎn)}11/22/20229二叉樹(shù)的基本操作（1）初始化操作——一般由構(gòu)造函數(shù)實(shí)現(xiàn)（2）建立一棵二叉樹(shù)（3）撤銷一棵二叉樹(shù)——可以由析構(gòu)函數(shù)實(shí)現(xiàn)（4）插入一個(gè)新結(jié)點(diǎn)（5）刪除一個(gè)結(jié)點(diǎn)（6）查找（7）判樹(shù)空（8）讀取結(jié)點(diǎn)數(shù)據(jù)（9）修改結(jié)點(diǎn)數(shù)據(jù)（10）求二叉樹(shù)的某一或某些性能（如結(jié)點(diǎn)數(shù)、高度、平衡度等）（11）求根結(jié)點(diǎn)、父結(jié)點(diǎn)、左子結(jié)點(diǎn)、右子結(jié)點(diǎn)等結(jié)點(diǎn)的指針（12）調(diào)整一棵二叉樹(shù)，優(yōu)化某一或某些性能（13）二叉樹(shù)遍歷操作（14）其他操作11/22/202210根據(jù)所定義的操作不同，可以有不同性能的二叉樹(shù)（1）線索化二叉樹(shù)(ThreadedBinaryTree)：在二叉樹(shù)結(jié)點(diǎn)中增加前 驅(qū)指針和后繼指針，使得在二叉樹(shù)中查找當(dāng)前結(jié)點(diǎn)的在某種遍 歷方式下的前驅(qū)和后繼結(jié)點(diǎn)很方便（2）堆(Heap)：用來(lái)實(shí)現(xiàn)高效率的優(yōu)先級(jí)隊(duì)列的二叉樹(shù)，采用順序 存儲(chǔ)結(jié)構(gòu)。其特點(diǎn)是：樹(shù)中任一結(jié)點(diǎn)的關(guān)鍵碼均?。ù螅┯诨?等于它的左子結(jié)點(diǎn)和右子結(jié)點(diǎn)的關(guān)鍵碼，稱為最?。ù螅┒?。（3）霍夫曼樹(shù)(HuffmanTree)：帶權(quán)路徑長(zhǎng)度WPL最小的（擴(kuò)充） 二叉樹(shù)。WPL----WeightedPathLength（4）二叉排序樹(shù)(BinarySortingTree)

二叉搜索樹(shù)(BinarySearchTree)

中序遍歷為嚴(yán)格遞增的二叉樹(shù)。這種樹(shù)可以提高搜索（查找） 效率。（5）最優(yōu)二叉搜索樹(shù)：平均搜索長(zhǎng)度最小的二叉搜索樹(shù)。（6）AVL樹(shù)：高度平衡的二叉搜索樹(shù)，可以提高搜索效率，減小平 均搜索長(zhǎng)度（7）其他11/22/2022116.4二叉樹(shù)遍歷(BinaryTreeTraversal)操作遍歷：按照某種順序不重復(fù)地訪問(wèn)遍二叉樹(shù)中的所有結(jié)點(diǎn)。此處的 訪問(wèn)可以是輸出、修改等操作，根據(jù)實(shí)際需要而定。 遍歷操作可以從一種非線性結(jié)構(gòu)中得到相應(yīng)的線性序列。 有不同順序的遍歷操作，對(duì)于二叉樹(shù)有三種遍歷操作：先序遍歷（NLR）

中序遍歷（LNR）

后序遍歷（LRN）

訪問(wèn)根結(jié)點(diǎn) 中序遍歷左子樹(shù) 后序遍歷左子樹(shù) 先序遍歷左子樹(shù) 訪問(wèn)根結(jié)點(diǎn) 后序遍歷右子樹(shù) 先序遍歷右子樹(shù) 中序遍歷右子樹(shù) 訪問(wèn)根結(jié)點(diǎn) 可以看出，上述三種順序的二叉樹(shù)遍歷操作都是遞歸定義的， 因此用遞歸算法實(shí)現(xiàn)很容易。11/22/202212二叉樹(shù)的先序遍歷操作遞歸算法template<classType>voidBinaryTree<Type>::PreOrder()//公共函數(shù)：先序遍歷二叉樹(shù)，通過(guò)調(diào)用私有函數(shù)PreOrder實(shí)現(xiàn){

PreOrder(root);}template<classType>voidBinaryTree<Type>::

PreOrder(BinTreeNode<Type>*current)//私有函數(shù)：先序遍歷根結(jié)點(diǎn)指針為current的二叉樹(shù){ if(current!=NULL) {//若二叉樹(shù)不空，則先序遍歷之

Visit(current);//訪問(wèn)根結(jié)點(diǎn)*current

PreOrder(current->leftChild);//先序遍歷左子樹(shù)

PreOrder(current->rightChild);//先序遍歷右子樹(shù) }}11/22/202213二叉樹(shù)定義中部分成員函數(shù)的實(shí)現(xiàn)：template<classType>voidBinaryTree<Type>:: destroy(BinTreeNode<Type>*current)//私有函數(shù)：若指針current不空，則刪除根指針為current的子樹(shù){

if(current!=NULL) { destroy(current->leftChild);//刪除左子樹(shù)

destroy(current->rightChild);//刪除右子樹(shù)

deletecurrent;}}//刪除根結(jié)點(diǎn)*current。后序遍歷template<classType>BinTreeNode<Type>*BinaryTree<Type>:: Parent(BinTreeNode<Type>*start,BinTreeNode<Type>*current)//私有函數(shù)：在根結(jié)點(diǎn)為*start的二叉樹(shù)中查找結(jié)點(diǎn)*current的父結(jié)點(diǎn)，若存//在則返回其指針，否則返回NULL{ if(start==NULL)returnNULL;//空樹(shù)

if(start->leftChild==current||start->rightChild==current)returnstart; //根結(jié)點(diǎn)即為所找結(jié)點(diǎn)

BinTreeNode<Type>*p; if((p=Parent(start->leftChild,current))!=NULL)returnp; //遞歸搜索左子樹(shù),若找到則返回其指針

elsereturnParent(start->rightChild,current);} //否則遞歸搜索右子樹(shù)，若找到則返回其指針，否則返回NULL。11/22/202214template<classType>voidBinaryTree<Type>:: Traverse(BinTreeNode<Type>*current,ostream&out)const//私有函數(shù)：先序遍歷輸出根指針為current二叉樹(shù)的所有結(jié)點(diǎn)的值{

if(current!=NULL)//非空樹(shù)則遍歷輸出 { out<<current->data<<‘‘;//輸出根結(jié)點(diǎn)的值

Traverse(current->leftChild,out);//遍歷輸出左子樹(shù)

Traverse(current->rightChild,out);//遍歷輸出右子樹(shù) }}template<classType>ostream&operator<<(ostream&out,

BinaryTree<Type>&Tree)

//重載inserting操作符“<<”，用于直接輸出一棵二叉樹(shù){ out<<“Preordertraversalofbinarytree.\n”; Tree.Traverse(Tree.Root,out);//先序遍歷輸出

out<<endl; returnout;}11/22/202215template<classType>istream&operator>>(istream&in,

BinaryTree<Type>&Tree)//重載abstracting操作符“>>”，用于輸入數(shù)據(jù)元素并同時(shí)創(chuàng)建一棵//二叉樹(shù)Tree{ Typeitem;

cout<<“Constructbinarytree:\n”;

cout<<“inputdata(endwith”<<Tree.RefValue<<“):”; in>>item; while(item!=Tree.RefValue) { Tree.Insert(item);//將數(shù)據(jù)元素item插入到二叉樹(shù)Tree中

cout<<“Inputdata(endwith”<<Tree.RefValue<<“):”; in>>item; } returnin;}11/22/2022167.4二叉搜索樹(shù)(BinarySearchTree)P235定義：一棵二叉樹(shù)稱之為二叉搜索樹(shù)，如果它滿足以下條件： 它或者是空樹(shù)； 或者左子樹(shù)中結(jié)點(diǎn)的關(guān)鍵碼均小于根結(jié)點(diǎn)的關(guān)鍵碼， 并且右子樹(shù)中結(jié)點(diǎn)的關(guān)鍵碼均大于根結(jié)點(diǎn)的關(guān)鍵碼， 并且左子樹(shù)和右子樹(shù)均為二叉搜索樹(shù)。

顯然，二叉搜索樹(shù)的中序遍歷的輸出序列是一嚴(yán)格遞增的有序序列二叉搜索數(shù)的類定義：11/22/202217#include<iostream.h>template<classType>classBST;//二叉搜索樹(shù)類的前視聲明template<classType>classBstNode:publicBinTreeNode//二叉搜索樹(shù)結(jié)點(diǎn)類的定義。二叉搜索樹(shù)的結(jié)點(diǎn)類是一般二叉樹(shù)結(jié)點(diǎn)//類的公有繼承{

friendclassBST<Type>;//二叉搜索樹(shù)類是二叉搜索樹(shù)結(jié)點(diǎn)類的友元類

public:

BstNode(): leftChild(NULL),rightChild(NULL){}

BstNode(constTyped): data(d),leftChild(NULL),rightChild(NULL){}

BstNode(constTyped=0,BstNode*L=NULL,BstNode* R=NULL):data(d),leftChild(L),rightChild(R){} ~BstNode(){} protected: Typedata;

BstNode<Type>*leftChild,*rightChild;}11/22/202218Template<classType>classBST:BinaryTree//{ public: BST():root(NULL){} BST(Typevalue):RefValue(value),root(NULL){} ~BST(){MakeEmpty(root)；｝ constBST&operator=(constBST&Tree); voidMakeEmpty();

intFind(constType&x)const {returnFind(x,root)==NULL;} TypeMin(); TypeMax(); voidInsert(constType&x){Insert(x,root);} voidRemove(constType&x){Remove(x,root);}

BstNode<Type>*Split(Typei,BST<Type>&B, Type&x,BST<Type>&C);11/22/202219

private:

BstNode<Type>*root; TypeRefValue;

BstNode<Type>*lastfound; voidMakeEmpty(BstNode<Type>*&ptr); voidInsert(constType&x,BstNode<Type>*&ptr); voidRemove(constType&x,BstNode<Type>*&ptr);

BstNode<Type>*Find(constType&x, BstNode<Type>*ptr)const;

BstNode<Type>*Min(BstNode<Type>*ptr)const;

BstNode<Type>*Max(BstNode<Type>*ptr)const; friendclassBSTIterator<Type>;}11/22/2022207.4.2二叉搜索樹(shù)的搜索（查找）算法（1）二叉搜索樹(shù)的遞歸搜索算法template<classType>BstNode<Type>*BST<Type>:: Find(constType&x,BstNode<Type>*ptr)const//私有函數(shù)，在以ptr為根指針的二叉搜索樹(shù)中查找關(guān)鍵碼為x的結(jié)//點(diǎn)，若找到，則返回該結(jié)點(diǎn)的指針，否則返回空指針NULL{ if(ptr==NULL)returnNULL; //根指針為空（即空樹(shù)）返回空指針

elseif(x==ptr->data)returnptr; //根結(jié)點(diǎn)即為所查結(jié)點(diǎn)，查找成功，返回根結(jié)點(diǎn)指針

elseif(x<ptr->data)returnFind(x,ptr->leftChild); //關(guān)鍵碼小于根結(jié)點(diǎn)的關(guān)鍵碼，遞歸搜索左子數(shù)

elsereturnFind(x,ptr->rightChild); //關(guān)鍵碼大于根結(jié)點(diǎn)的關(guān)鍵碼，遞歸搜索右子數(shù)}11/22/202221（2）二叉搜索樹(shù)的非遞歸搜索算法（迭代搜索算法）template<classType>BstNode<Type>*BST<Type>:: Find(constType&x,BstNode<Type>*ptr,*&fp)const//私有函數(shù)，入口時(shí)fp=NULL,ptr為根指針。本算法在以ptr為根指針的二//叉搜索樹(shù)中查找關(guān)鍵碼為x的結(jié)點(diǎn)。若找到，則函數(shù)返回該結(jié)點(diǎn)的指針，//否則函數(shù)返回空指針NULL，一般情況下fp返回該結(jié)點(diǎn)的父結(jié)點(diǎn)的指針{ if(ptr==NULL)returnNULL;//空樹(shù)，返回NULL else//非空樹(shù)，繼續(xù)搜索 {

BstNode<Type>*temp=ptr;//從根結(jié)點(diǎn)開(kāi)始搜索

while((temp!=NULL)&&(temp->data!=x)) //若當(dāng)前結(jié)點(diǎn)存在且不是所找結(jié)點(diǎn)，則繼續(xù)搜索 {fp=temp;//父結(jié)點(diǎn)指針

if(temp->data<x)temp=temp->rightChild;//關(guān)鍵碼x大于當(dāng) //前結(jié)點(diǎn)的關(guān)鍵碼，則從當(dāng)前結(jié)點(diǎn)開(kāi)始沿右鏈前進(jìn)一步

elsetemp=temp->leftChild;//關(guān)鍵碼x小于當(dāng)前結(jié)點(diǎn)的關(guān)鍵 //碼，則從當(dāng)前結(jié)點(diǎn)開(kāi)始沿左鏈前進(jìn)一步 }

if(temp->data==x)returntemp;//搜索成功，返回結(jié)點(diǎn)指針

elsereturnNULL;//樹(shù)中不存在所找結(jié)點(diǎn)，搜索失敗，返回NULL }}11/22/202222在上述算法中有一個(gè)指針的引用fp:BstNode<Type>*&fp;通過(guò)指針的引用可以從函數(shù)中返回一個(gè)被函數(shù)改變了的指針。假定對(duì)上述算法作如下調(diào)用：Template<classType>intBST<Type>::Find(constType&x)const//{ returnFind(key,root,fatherptr)==NULL;}11/22/2022237.4.3二叉搜索樹(shù)的插入算法template<classType>voidBST<Type>:: Insert(constType&x,BstNode<Type>*&ptr)//私有函數(shù)，在以ptr為根指針的二叉搜索樹(shù)中插入關(guān)鍵碼為x的結(jié)點(diǎn)。若在//樹(shù)中已存在關(guān)鍵碼為x的結(jié)點(diǎn)，則不作插入。要求插入后仍然是一棵二叉//搜索樹(shù)。注意ptr是一個(gè)指針的引用參數(shù)，它可以自動(dòng)改變相應(yīng)的實(shí)參，實(shí)//現(xiàn)操作效果的返回。如本算法中可以自動(dòng)改變插入結(jié)點(diǎn)的父結(jié)點(diǎn)的左子指//針或右子指針或根結(jié)點(diǎn)指針{ if(ptr==NULL)//若原樹(shù)為空樹(shù)，則把關(guān)鍵碼為x的結(jié)點(diǎn)就作為根結(jié)點(diǎn) { ptr=newBstNode<Type>(x,NULL);//創(chuàng)建一新結(jié)點(diǎn)并作為根結(jié)點(diǎn)

if(ptr==NULL)//檢查內(nèi)存分配是否成功 {cerr<<“Outofspace”<<endl;exit(1);} } elseif(x<ptr->data)Insert(x,ptr->leftChild); //若原樹(shù)不空且x小于根結(jié)點(diǎn)的關(guān)鍵碼，則遞歸插入左子樹(shù)中

elseif(x>ptr->data)Insert(x,ptr->rightChild); //若原樹(shù)不空且x大于根結(jié)點(diǎn)的關(guān)鍵碼，則遞歸插入右子樹(shù)中 //若x等于根結(jié)點(diǎn)的關(guān)鍵碼，則不作插入操作}11/22/202224建立二叉搜索樹(shù)的算法template<classType>BST<Type>::BST(Typevalue)//構(gòu)造函數(shù)，本算法通過(guò)輸入一元素插入一結(jié)點(diǎn)的方法，將一輸入的數(shù)據(jù)元//素序列（以value作為結(jié)束標(biāo)志）構(gòu)建成一棵二叉搜索樹(shù){ Typex; root=NULL;//置空樹(shù)

RefValue=value;//設(shè)置輸入結(jié)束標(biāo)志

cin>>x;//輸入一個(gè)數(shù)據(jù)元素

while(x!=RefValue)//若輸入的元素不是結(jié)束標(biāo)志則繼續(xù) { Insert(x,root); //將輸入的元素插入到根指針為root的二叉搜索樹(shù)中。在插入第一 //個(gè)元素前根指針root為空，插入后root指向第一個(gè)結(jié)點(diǎn)，root在 //Insert函數(shù)中被改變。這是因?yàn)閞oot所對(duì)應(yīng)的形參是一個(gè)非常態(tài) //的引用參數(shù)

cin>>x; }}通過(guò)本算法創(chuàng)建的二叉搜索樹(shù)可能會(huì)很不平衡，極端情況下將退化成為一單鏈表，從而失去了二叉搜索樹(shù)高搜索效率的優(yōu)點(diǎn)，因此需作調(diào)整。11/22/202225二叉搜索樹(shù)的刪除算法template<classType>voidBST<Type>:: Remove(constType&x,BstNode<Type>*&ptr)//私有函數(shù)，刪除根指針為ptr的二叉搜索樹(shù)中關(guān)鍵碼為x的結(jié)點(diǎn)。要求刪除//后仍然是一棵根指針為ptr的二叉搜索樹(shù)，并且不增加樹(shù)的高度{ BstNode<Type>*temp; if(ptr!=NULL) if(x<ptr->data)Remove(x,ptr->leftChild); //x結(jié)點(diǎn)在左子樹(shù)中，遞歸刪除左子樹(shù)中的x結(jié)點(diǎn)

elseif(x>ptr->data)Remove(x,ptr->rightChild); //x結(jié)點(diǎn)在右子樹(shù)中，遞歸刪除右子樹(shù)中的x結(jié)點(diǎn)

elseif(ptr->leftChild!=NULL&&ptr->rightChild!=NULL) //x結(jié)點(diǎn)就是根結(jié)點(diǎn)，刪除根結(jié)點(diǎn)。若根的左右子樹(shù)均不空 { temp=Min(ptr->rightChild); //則從右子樹(shù)中查找最小結(jié)點(diǎn)

ptr->data=temp->data; //并用該結(jié)點(diǎn)數(shù)據(jù)代替根結(jié)點(diǎn)的數(shù)據(jù)

Remove(ptr->data,ptr->rightChild);//最后將該結(jié)點(diǎn)刪除 } 11/22/202226

else//否則根結(jié)點(diǎn)的左右子樹(shù)不全 { temp=ptr; if(ptr->leftChild==NULL)ptr=ptr->rightChild; //若無(wú)左子樹(shù)，則直接將根指針指向右子結(jié)點(diǎn)以刪除 //根結(jié)點(diǎn)。若此時(shí)又無(wú)右子樹(shù)，則ptr變?yōu)榭罩羔?/p>

elseif(ptr->rightChild==NULL)ptr=ptr->leftChild; //若有左子樹(shù)但無(wú)右子樹(shù)，則直接將根指針指向左子 //結(jié)點(diǎn)以刪除根結(jié)點(diǎn)

deletetemp;//釋放被刪除的根結(jié)點(diǎn) }}template<classType>BstNode<Type>*BST<Type>:: Min(BstNode<Type>*ptr)const//私有函數(shù)，在以ptr為根指針的二叉搜索樹(shù)中查找關(guān)鍵碼最小的結(jié)點(diǎn)，并返//回該結(jié)點(diǎn)的指針{ //原理：從根結(jié)點(diǎn)開(kāi)始沿著左鏈往下查找，第一個(gè)左子樹(shù)為空的結(jié)點(diǎn)就是 //樹(shù)中的關(guān)鍵碼最小的結(jié)點(diǎn)}課堂作業(yè)：完成上述算法11/22/2022277.6AVL樹(shù)——高度平衡的二叉搜索樹(shù) 前述的二叉搜索樹(shù)的插入和建立（通過(guò)插入實(shí)現(xiàn)）算法不考慮樹(shù) 的平衡問(wèn)題，因此有可能產(chǎn)生高度不平衡的二叉搜索樹(shù)，極端情 況下將退化成一個(gè)單鏈表，失去了二叉搜索樹(shù)的優(yōu)點(diǎn)。因此在二叉搜索樹(shù)的插入過(guò)程中必須調(diào)整樹(shù)的結(jié)構(gòu)，使之平衡化。AVL樹(shù)的定義： 一棵AVL樹(shù)或者是空樹(shù)，或者是具有下列性質(zhì)的二叉搜索樹(shù)：它 的左子樹(shù)和右子樹(shù)的高度之差的絕對(duì)值不超過(guò)1。結(jié)點(diǎn)的平衡因子(balancefactor)： balance＝該結(jié)點(diǎn)的右子樹(shù)高度－該結(jié)點(diǎn)的左子樹(shù)高度對(duì)于AVL樹(shù)：|balance|<=1

即balance只能?。?，0，1三者之一平衡化方法——平衡化旋轉(zhuǎn)方法： 單旋轉(zhuǎn)：左單旋轉(zhuǎn)（左旋）RotateLeft

右單旋轉(zhuǎn)（右旋）RotateRight

雙旋轉(zhuǎn)：先左后右雙旋轉(zhuǎn)（左平衡LeftBalance）

先右后左雙旋轉(zhuǎn)（右平衡RightBalance）11/22/202228AVL樹(shù)的類定義：template<classType>classAVLTree{ public:

structAVLNode

//用struct

定義AVL樹(shù)的結(jié)點(diǎn)類。在struct中缺省的訪問(wèn)級(jí)別 //是公有(public)的，而在class中缺省的訪問(wèn)級(jí)別是私有 //(private)的，除此之外struct和class是等價(jià)的 {Typedata;

AVLNode<Type>*left,*right;

intbalance;

AVLNode():left(NULL),right(NULL),balance(0){}

AVLNode(Typed,AVLNode<Type>*l=NULL,

AVLNode<Type>*r=NULL): data(d),left(l),right(r),balance(0){} };11/22/202229protected: TypeRefValue;//結(jié)束標(biāo)志，用于輸入數(shù)據(jù)元素序列

AVLNode<Type>*root;

intInsert(AVLNode<Type>*&tree,Typex,int&taller); voidRotateLeft(AVLNode<Type>*Tree,AVLNode<Type>*&NewTree); voidRotateRight(AVLNode<Type>*Tree,AVLNode<Type>*&NewTree); voidLeftBalance(AVLNode<Type>*&Tree,int&taller); voidRightBalance(AVLNode<Type>*&Tree,int&taller);

intDepth(AVLNode<Type>*t)const;public:

AVLTree():root(NULL){}

AVLTree(TypeRef):RefValue(Ref),root(NULL){}

intInsert(Typex){inttaller;returnInsert(root,x,taller);} friendistream&operator>>(istream&in,AVLTree<Type>&Tree); friendostream&operator<<(ostream&out,constAVLTree<Type>&Tree);

intDepth()const;}11/22/2022307.6.2平衡化旋轉(zhuǎn)處理

A

原樹(shù)為AVL樹(shù)，在右子樹(shù)中插入結(jié)點(diǎn)（1）若向子樹(shù)E中插入一個(gè)結(jié)點(diǎn)導(dǎo)致

BC

子樹(shù)E的高度增加1—此時(shí)需要作左單旋轉(zhuǎn)處理（右右增1）

DE（2）若向子樹(shù)D中插入一個(gè)結(jié)點(diǎn)導(dǎo)致

子樹(shù)D的高度增加1—此時(shí)需要

作先右后左雙旋轉(zhuǎn)處理（右左增1）

A

原樹(shù)為AVL樹(shù)，在左子樹(shù)中插入結(jié)點(diǎn)

（1）若向子樹(shù)E中插入一個(gè)結(jié)點(diǎn)導(dǎo)致

BC子樹(shù)E的高度增加1—此時(shí)需要作右單旋轉(zhuǎn)處理（左左增1）

DE（2）若向子樹(shù)D中插入一個(gè)結(jié)點(diǎn)導(dǎo)致

子樹(shù)D的高度增加1—此時(shí)需要

作先左后右雙旋轉(zhuǎn)處理（左右增1）11/22/202231左右單旋轉(zhuǎn)處理：（升C移D降A(chǔ)）（升B移E降A(chǔ)）ABCDECABDEACBEDBDAEC左單旋轉(zhuǎn)處理右單旋轉(zhuǎn)處理11/22/202232template<classType>voidAVLTree<Type>::

RotateLeft(AVLNode*Tree,AVLNode*&NewTree)//對(duì)以Tree為根指針的二叉搜索樹(shù)作左單旋轉(zhuǎn)處理，使其成為一棵//AVL樹(shù)。處理后的AVL樹(shù)的根指針為NewTree{ NewTree=Tree->right;//升C，使C成為新的根結(jié)點(diǎn)

Tree->right=NewTree->left;//移D，使D子樹(shù)成為A的右子樹(shù)

NewTree->left=Tree;//降A(chǔ)，使A子樹(shù)成為C的左子樹(shù)}template<classType>voidAVLTree<Type>:: RotateRight(AVLNode*Tree,AVLNode*&NewTree)//對(duì)以Tree為根指針的二叉搜索樹(shù)作右單旋轉(zhuǎn)處理，使其成為一棵//AVL樹(shù)。處理后的AVL樹(shù)的根指針為NewTree{ NewTree=Tree->left;//升C，使C成為新的根結(jié)點(diǎn)

Tree->left=NewTree->right;//移D，使D子樹(shù)成為A的右子樹(shù)

NewTree->right=Tree;//降A(chǔ)，使A子樹(shù)成為C的左子樹(shù)}11/22/202233先左后右雙旋轉(zhuǎn)處理ABCDEGFACBEDFG升E降B移F（對(duì)B子樹(shù)作左單旋轉(zhuǎn)處理）EACGBDF升E降A(chǔ)移G（對(duì)A樹(shù)作右單旋轉(zhuǎn)處理）11/22/202234template<classType>voidAVLTree<Type>::

LeftBalance(AVLNode*&Tree,int&taller)//左平衡處理函數(shù)，當(dāng)在左子樹(shù)中插入一個(gè)結(jié)點(diǎn)后導(dǎo)致不平衡時(shí)調(diào)用該函數(shù)//輸入時(shí)Tree為左子樹(shù)太高的非AVL樹(shù)的根指針，//輸入時(shí)taller應(yīng)為1,表示插入操作導(dǎo)致樹(shù)的高度增加//輸出時(shí)Tree為平衡處理后的AVL樹(shù)的根指針//輸出時(shí)taller為0表示處理后的新樹(shù)的高度與插入前的高度一致。{ if(Tree->balance<-1)//左子樹(shù)太高導(dǎo)致的不平衡 {AVLNode<Type>*leftsub=Tree->left;//定義左子樹(shù)B的指針

AVLNode<Type>*rightsub; switch(leftsub->balance) {case–1://新結(jié)點(diǎn)插入在D子樹(shù)中并使其高度增加，導(dǎo)致A樹(shù)的 //不平衡，需作右單旋轉(zhuǎn)處理（參見(jiàn)圖7.25,P250） Tree->balance=0;//處理后A結(jié)點(diǎn)的平衡因子＝0

leftsub->balance=0;//處理后B結(jié)點(diǎn)的平衡因子＝0

RotateRight(Tree,Tree);//作右單旋轉(zhuǎn)處理

taller=0;//處理后A樹(shù)的高度不增加，上一層無(wú)需再處理

break;

case0:break;//B結(jié)點(diǎn)的平衡因子等于0并使其高度增加，說(shuō)明新插//入的結(jié)點(diǎn)就是B結(jié)點(diǎn)，但插入B結(jié)點(diǎn)不會(huì)使A樹(shù)不平衡（因插入前A樹(shù)是平//衡的），因此這種情況不可能發(fā)生，因此不用理會(huì)它11/22/202235

case1:

//新結(jié)點(diǎn)插入在E子樹(shù)中并使E子樹(shù)和B子樹(shù)的高度增加， //導(dǎo)致A樹(shù)的不平衡，需作先左后右雙旋轉(zhuǎn)平衡處理， //參見(jiàn)圖7.26,P250

rightsub=leftsub->right;//rightsub為E子樹(shù)的根指針

switch(rightsub->balance) {case–1://新結(jié)點(diǎn)插入在F子樹(shù)中并使其高度增加， //參見(jiàn)圖7.26(d) Tree->balance=1;//平衡處理后A結(jié)點(diǎn)的平衡因子

leftsub->balance=0;//平衡處理后B結(jié)點(diǎn)的平衡因子

break; case0://F子樹(shù)與G子樹(shù)等高的情況，將圖7.26(d)中G子樹(shù) //的高度改為h后計(jì)算A結(jié)點(diǎn)和B結(jié)點(diǎn)的平衡因子

Tree->balance=0;leftsub->balance=0;break; //E結(jié)點(diǎn)的平衡因子為0，并且E子樹(shù)高度又增加，這只有一種情況， //即插入的新結(jié)點(diǎn)就是E結(jié)點(diǎn)，F(xiàn)和G都是空樹(shù)，并且D和C也是空樹(shù)

case1://新結(jié)點(diǎn)插入在G子樹(shù)中并使其高度增加， //將圖7.26(d)中G子樹(shù)的高度改為h，F(xiàn)子樹(shù)的高度 //改為h-1后計(jì)算A結(jié)點(diǎn)和B結(jié)點(diǎn)的平衡因子

Tree->balance=0;leftsub->balance=-1;break; } 11/22/202236

rightsub->balance=0;//平衡處理后E結(jié)點(diǎn)（新樹(shù)的根結(jié)點(diǎn)）的平衡因子等于0

RotateLeft(leftsub,Tree->left);//先對(duì)圖7.26(b)中的B子樹(shù)進(jìn)行左單旋轉(zhuǎn)處理，處理后成為圖7.26(c)

RotateRight(Tree,Tree);//后對(duì)圖7.26(c)中的A樹(shù)進(jìn)行右單旋轉(zhuǎn)處理，處理后成為圖7.26(d) taller=0;//平衡處理完后，新樹(shù)的高度與原樹(shù)一樣 }}11/22/202237先右后左雙旋轉(zhuǎn)處理ABCDEFGABDCEGFDACBFGE升D降C移GC子樹(shù)右單旋轉(zhuǎn)升D降A(chǔ)移FA樹(shù)左單旋轉(zhuǎn)11/22/202238template<classType>voidAVLTree<Type>::

RightBalance(AVLNode*&Tree,int&taller)//右平衡處理函數(shù)，當(dāng)在右子樹(shù)中插入一個(gè)結(jié)點(diǎn)后導(dǎo)致不平衡時(shí)調(diào)用該函數(shù)//輸入時(shí)Tree為右子樹(shù)太高的非AVL樹(shù)的根指針//輸出時(shí)Tree為平衡處理后的AVL樹(shù)的根指針//Taller置為0表示下一步無(wú)需再旋轉(zhuǎn)。{ if(Tree->balance>1)//右子樹(shù)太高導(dǎo)致的不平衡

AVLNode<Type>*rightsub=Tree->right;//定義右子樹(shù)C的指針

AVLNode<Type>*leftsub; switch(rightsub->balance) {case1://右子樹(shù)C的根結(jié)點(diǎn)的平衡因子等于1，則C的 //右子樹(shù)E高于其左子樹(shù)D，需作左單旋轉(zhuǎn)處理 //（參見(jiàn)圖7.24,P249） Tree->balance=0;//處理后A結(jié)點(diǎn)的平衡因子＝0

rightsub->balance=0;//處理后C結(jié)點(diǎn)的平衡因子＝0

RotateLeft(Tree,Tree);//作左單旋轉(zhuǎn)處理

taller=0;//表示下一步無(wú)需再旋轉(zhuǎn)

break; case0:break;//在每插入一個(gè)結(jié)點(diǎn)后都進(jìn)行平衡處理的話， //此情況不可能發(fā)生11/22/202239

case-1://E子樹(shù)低于D子樹(shù)的情況，參見(jiàn)圖7.27,P251

leftsub=rightsub->left;//leftsub

為D子樹(shù)的根指針

switch(leftsub->balance) {case

1://G子樹(shù)高于F子樹(shù)的情況，參見(jiàn)圖7.27(d) Tree->balance=-1;//平衡處理后A結(jié)點(diǎn)的平衡因子

rightsub->balance=0;//平衡處理后C結(jié)點(diǎn)的平衡因子

break; case0://F子樹(shù)與G子樹(shù)等高的情況，將圖7.27(d)中F子樹(shù) //的高度改為h后計(jì)算A結(jié)點(diǎn)和C結(jié)點(diǎn)的平衡因子

Tree->balance=0;rightsub->balance=0;break; case-1://G子樹(shù)低于F子樹(shù)情況，將圖7.27(d)中G子樹(shù)的 //高度改為h-1，F(xiàn)子樹(shù)的高度改為h后計(jì)算A結(jié)點(diǎn) //和C結(jié)點(diǎn)的平衡因子

Tree->balance=0;rightsub->balance=1;break; } leftsub->balance=0;//平衡處理后D結(jié)點(diǎn)的平衡因子

RotateRight(rightsub,Tree->right);//先對(duì)圖7.27(b)中的 //C子樹(shù)進(jìn)行右單旋轉(zhuǎn)處理，處理后成為圖7.27(c)

RotateLeft(Tree,Tree);//后對(duì)圖7.27(c)中的A樹(shù)進(jìn)行左單 //旋轉(zhuǎn)處理，處理后成為圖7.27(d) taller=0;}} 11/22/2022407.6.3AVL樹(shù)的插入操作算法template<classType>intAVLTree<Type>:: Insert(AVLNode*&tree,Typex,int&taller)//在以tree為根指針的AVL樹(shù)中插入值為x的新結(jié)點(diǎn)//輸入時(shí)taller=0//如果插入成功，則函數(shù)返回1，否則函數(shù)返回0//若tree樹(shù)中已存在值為x的結(jié)點(diǎn)或者內(nèi)存分配失敗，則插入操作失敗//如果插入后tree樹(shù)的高度增加，則taller返回1，否則taller返回0//要求成功插入后仍然是一棵AVL樹(shù)（因此可能需作平衡處理）//成功插入后的新樹(shù)的根指針仍為tree{ intsuccess; if(tree==NULL)//tree樹(shù)為空樹(shù)，則創(chuàng)建新結(jié)點(diǎn)并作為根結(jié)點(diǎn)即可 { tree=newAVLNode(x); success=tree!=NULL?1:0; if(success)//內(nèi)存分配成功 {taller=1;//tree樹(shù)高度增加

tree->balance=0;//tree樹(shù)的平衡因子等于0 } }11/22/202241

elseif(x<tree->data)//tree樹(shù)不空且x小于根結(jié)點(diǎn)的關(guān)鍵碼 {success=Insert(tree->left,x,taller);//遞歸插入左子樹(shù)中

if(success&&taller)//插入成功并且左子樹(shù)的高度增加了

switch(tree->balance) {case–1://tree樹(shù)根結(jié)點(diǎn)的平衡因子原為－1，其左子樹(shù) //的高度增1后，使得插入后tree樹(shù)根結(jié)點(diǎn)的平衡 //因子等于－2，因此對(duì)tree樹(shù)需作左平衡處理

LeftBalance(tree,taller);break; case0://tree樹(shù)根結(jié)點(diǎn)的平衡因子原為0，其左子樹(shù)的 //高度增1后，使得插入后的tree樹(shù)根結(jié)點(diǎn)的平 //衡因子等于－1，因此tree樹(shù)仍是一棵AVL樹(shù)， //無(wú)需作平衡處理，但tree樹(shù)的高度增加了

tree->balance=-1;break; case1://tree樹(shù)根結(jié)點(diǎn)的平衡因子原為1，其左子樹(shù)的 //高度增1后，使得插入后的tree樹(shù)根結(jié)點(diǎn)的平衡 //因子等于0，因此對(duì)tree樹(shù)仍是一棵AVL樹(shù)， //無(wú)需作平衡處理，并且tree樹(shù)的高度未增加

tree->balance=0;taller=0;break; } }11/22/202242

elseif(x>tree->data)//tree樹(shù)不空且x大于根結(jié)點(diǎn)的關(guān)鍵碼 {success=Insert(tree->right,x,taller);//遞歸插入右子樹(shù)中

if(success&&taller)//插入成功并且右子樹(shù)的高度增加了

switch(tree->balance) {case1://tree樹(shù)根結(jié)點(diǎn)的平衡因子原為1，其右子樹(shù) //的高度增1后，使得插入后tree樹(shù)根結(jié)點(diǎn)的平衡 //因子等于2，因此對(duì)tree樹(shù)需作右平衡處理

RightBalance(tree,taller);break; case0://tree樹(shù)根結(jié)點(diǎn)的平衡因子原為0，其右子樹(shù)的 //高度增1后，使得插入后的tree樹(shù)根結(jié)點(diǎn)的平 //衡因子等于1，因此tree樹(shù)仍是一棵AVL樹(shù)， //無(wú)需作平衡處理，但tree樹(shù)的高度增加了

tree->balance=1;break; case-1://tree樹(shù)根的平衡因子原為-1，其右子樹(shù)的 //高度增1后，使得插入后的tree樹(shù)根結(jié)點(diǎn)的平衡 //因子等于0，因此tree樹(shù)仍是一棵AVL樹(shù)， //無(wú)需作平衡處理，并且tree樹(shù)的高度未增加

tree->balance=0;taller=0;break; } }11/22/202243

elsesuccess=0;//x==tree->data,即值為x的結(jié)點(diǎn)已存在， //無(wú)需插入操作，認(rèn)為插入操作失敗

returnsuccess;}11/22/2022447.6.4AVL樹(shù)的刪除操作算法template<classType>intAVLTree<Type>:: Remove(AVLNode*&tree,Typex,int&taller)//在以tree為根指針的AVL樹(shù)中刪除值為x的新結(jié)點(diǎn)//輸入時(shí)taller=0//如果刪除成功，則函數(shù)返回1，否則函數(shù)返回0//若tree樹(shù)中不存在值為x的結(jié)點(diǎn)，則刪除操作失敗//如果刪除后tree樹(shù)的高度降低，則taller返回1，否則taller返回0//要求成功刪除后仍然是一棵AVL樹(shù)（因此可能需作平衡處理）//成功刪除后的新樹(shù)的根指針仍為tree{ intsuccess; if(tree==NULL)success=0; //tree樹(shù)為空樹(shù)，則刪除失敗（樹(shù)中不存在所找結(jié)點(diǎn)）

elseif(x==tree->data)success=RootRemove(tree,taller); //所找結(jié)點(diǎn)即為根結(jié)點(diǎn)，則刪除根結(jié)點(diǎn)。刪除后的新樹(shù)的根指針仍為tree//如果刪除后tree樹(shù)的高度降低，則taller返回1，否則taller返回0 //要求成功刪除后仍然是一棵AVL樹(shù)（因此可能需作平衡處理）11/22/202245

elseif(x<tree->data)//tree樹(shù)不空且x小于根結(jié)點(diǎn)的關(guān)鍵碼 {success=Remove(tree->left,x,taller);//遞歸刪除左子樹(shù)中的x

if(success&&taller)//刪除成功并且左子樹(shù)的高度降低了

switch