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

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

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

按從上到下、從左到右順序 編號(hào)一棵滿二叉樹，并按從大到小的順序連續(xù)刪除 該滿二叉樹的若干個(gè)結(jié)點(diǎn)后剩下的二叉樹稱為一棵 完全二叉樹（參見圖6.3b）2i2k+1-111/22/20224完全二叉樹的性質(zhì)和順序存儲(chǔ)結(jié)構(gòu)（1）具有n個(gè)結(jié)點(diǎn)的完全二叉樹的高度=log2(n+1)–1（2）若將一棵按前述原則編號(hào)的完全二叉樹，按其編號(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）無父結(jié)點(diǎn) 由上可知，完全二叉樹的父——左子、父——右子之間的關(guān)系可以通過相應(yīng)結(jié)點(diǎn)的下標(biāo)之間的簡單數(shù)學(xué)關(guān)系完全地表示 出來，因此可以采用順序存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)完全二叉樹。（參見 教材6.3.1數(shù)組表示） 順序存儲(chǔ)結(jié)構(gòu)用于動(dòng)態(tài)性較小的完全二叉樹的存儲(chǔ)不失為 一種簡單有效的方法，但不通用。樹型數(shù)據(jù)結(jié)構(gòu)一般采用鏈?zhǔn)酱鎯?chǔ)方式來存儲(chǔ)。11/22/202256.3.2二叉樹的鏈?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)的二叉樹結(jié)點(diǎn)（簡稱二叉樹結(jié)點(diǎn)）的類定義：template<classType>classBinaryTree;//二叉樹類聲明template<classType>classBinTreeNode//二叉樹結(jié)點(diǎn)類定義{

friendclassBinaryTree<Type>;//二叉樹類是二叉樹結(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)的二叉樹的類定義template<classType>classBinaryTree{ public:

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

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

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

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ù)元素并建立一棵二叉樹Tree friendostream&operator<<(ostream&out,BinTreeNode<Type>&Tree);

//重載操作：輸出一棵二叉樹TreePrivate:

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

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

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

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

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

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

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

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

二叉搜索樹(BinarySearchTree)

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

中序遍歷（LNR）

后序遍歷（LRN）

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

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

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

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

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

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

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

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

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

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; //遞歸搜索左子樹,若找到則返回其指針

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

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

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

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

BinaryTree<Type>&Tree)

//重載inserting操作符“<<”，用于直接輸出一棵二叉樹{ 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)建一棵//二叉樹Tree{ Typeitem;

cout<<“Constructbinarytree:\n”;

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

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

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

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

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

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

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)開始沿右鏈前進(jìn)一步

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

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

elsereturnNULL;//樹中不存在所找結(jié)點(diǎn)，搜索失敗，返回NULL }}11/22/202222在上述算法中有一個(gè)指針的引用fp:BstNode<Type>*&fp;通過指針的引用可以從函數(shù)中返回一個(gè)被函數(shù)改變了的指針。假定對上述算法作如下調(diào)用：Template<classType>intBST<Type>::Find(constType&x)const//{ returnFind(key,root,fatherptr)==NULL;}11/22/2022237.4.3二叉搜索樹的插入算法template<classType>voidBST<Type>:: Insert(constType&x,BstNode<Type>*&ptr)//私有函數(shù)，在以ptr為根指針的二叉搜索樹中插入關(guān)鍵碼為x的結(jié)點(diǎn)。若在//樹中已存在關(guān)鍵碼為x的結(jié)點(diǎn)，則不作插入。要求插入后仍然是一棵二叉//搜索樹。注意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)//若原樹為空樹，則把關(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); //若原樹不空且x小于根結(jié)點(diǎn)的關(guān)鍵碼，則遞歸插入左子樹中

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

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

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

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

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

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

elseif(ptr->leftChild!=NULL&&ptr->rightChild!=NULL) //x結(jié)點(diǎn)就是根結(jié)點(diǎn)，刪除根結(jié)點(diǎn)。若根的左右子樹均不空 { temp=Min(ptr->rightChild); //則從右子樹中查找最小結(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)的左右子樹不全 { temp=ptr; if(ptr->leftChild==NULL)ptr=ptr->rightChild; //若無左子樹，則直接將根指針指向右子結(jié)點(diǎn)以刪除 //根結(jié)點(diǎn)。若此時(shí)又無右子樹，則ptr變?yōu)榭罩羔?/p>

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

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

structAVLNode

//用struct

定義AVL樹的結(jié)點(diǎn)類。在struct中缺省的訪問級(jí)別 //是公有(public)的，而在class中缺省的訪問級(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

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

BC

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

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

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

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

A

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

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

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

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

子樹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)//對以Tree為根指針的二叉搜索樹作左單旋轉(zhuǎn)處理，使其成為一棵//AVL樹。處理后的AVL樹的根指針為NewTree{ NewTree=Tree->right;//升C，使C成為新的根結(jié)點(diǎn)

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

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

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

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

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

AVLNode<Type>*rightsub; switch(leftsub->balance) {case–1://新結(jié)點(diǎn)插入在D子樹中并使其高度增加，導(dǎo)致A樹的 //不平衡，需作右單旋轉(zhuǎ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樹的高度不增加，上一層無需再處理

break;

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

case1:

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

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

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

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

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

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

case1://新結(jié)點(diǎn)插入在G子樹中并使其高度增加， //將圖7.26(d)中G子樹的高度改為h，F(xiàn)子樹的高度 //改為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)（新樹的根結(jié)點(diǎn)）的平衡因子等于0

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

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

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

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

AVLNode<Type>*leftsub; switch(rightsub->balance) {case1://右子樹C的根結(jié)點(diǎn)的平衡因子等于1，則C的 //右子樹E高于其左子樹D，需作左單旋轉(zhuǎ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;//表示下一步無需再旋轉(zhuǎn)

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

case-1://E子樹低于D子樹的情況，參見圖7.27,P251

leftsub=rightsub->left;//leftsub

為D子樹的根指針

switch(leftsub->balance) {case

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

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

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

Tree->balance=0;rightsub->balance=0;break; case-1://G子樹低于F子樹情況，將圖7.27(d)中G子樹的 //高度改為h-1，F(xiàn)子樹的高度改為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);//先對圖7.27(b)中的 //C子樹進(jìn)行右單旋轉(zhuǎn)處理，處理后成為圖7.27(c)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

switch