第6章樹和二叉樹

數據結構—C++實現繆淮扣沈俊顧訓穰上海大學計算機工程與科學學院2014年6月第6章樹和二叉樹樹的概念二叉樹二叉樹的存儲結構遍歷二叉樹線索二叉樹二叉樹的應用樹和森林的實現等價類及其表示6.1樹的概念樹（tree）T是一個包含n(n>=0)個數據元素的有限集合。并且有：（1）當n=0時，T稱為空樹；（2）如果n>0，則樹有且僅有一個特定的被稱為根（root）的結點，樹的根結點只有后繼，沒有前驅；（3）當n>1時,除根結點以外的其余結點可分為m(m>0)個互不相交的非空有限集T1、T2、...、Tm,其中每一個集合本身又是一棵非空樹,并且稱它們?yōu)楦Y點的子樹（subtree）。樹的概念樹的概念樹的術語1．結點2．結點的度3．終端結點4．非終端結點5．樹的度6．孩子和雙親7．兄弟樹的術語8．祖先9．子孫10．結點的層次11．樹的深度12．堂兄弟13．有序樹14．無序樹15．森林1、樹形表示法2、嵌套集合表示法3、凹入目錄表示法4、廣義表形式的表示法樹的表示形式樹的基本操作（1）Root()（2）CreateRoot(d)（3）Parent(x)（4）FirstChild(x)（5）NextSibling(x,y)（6）PreSibling(x,y)（7）Retrieve(x)（8）Assign(x，d)（9）InsertChild(x,d)（10）DeleteChild(x,i)（11）DeleteSubTree(x)（12）IsEmpty()（13）Travers（）6.2二叉樹二叉樹的定義:

二叉樹BT是有限個結點的集合。當集合非空時，其中有一個結點稱為二叉樹的根結點，用BT表示，余下的結點（如果有的話）最多被組成兩棵分別被稱為BT的左子樹（leftsubtree）和右子樹（rightsubtree）、互不相交的二叉樹。二叉樹的五種形態(tài):性質1：有n(n>0)個結點的二叉樹的分支數為n-1。證明：因為在二叉樹中，除根結點以外的其它每個結點有且僅有一個父結點。而子結點與父結點間有且只有一條分支，因此對于有n(n>0)個結點的二叉樹，其分支的數目為n-1。二叉樹的性質性質2：若二叉樹的高度為h（h≥0），則該二叉樹最少有h個結點，最多有2h-1個結點。證明：因為在二叉樹中，每一層至少要有1個結點，因此對于高度為h的二叉樹，其結點數至少為h個。在二叉樹中，第一層只有一個根結點；又因為每個結點最多有2個孩子結點，所以第i層的結點最多為2i-1個，所以高度為h（h≥0）的二叉樹結點總數最多為：20+21+…+2h-1=2h-1二叉樹的性質性質3：含有n個結點的二叉樹的高度最大值為n，最小值為log2(n+1)

。證明：因為在二叉樹中，每層至少有一個結點，因此對于含有n個結點的二叉樹，其高度不會超過n。根據性質2可以得知，高度為h的二叉樹最多有2h-1個結點，即n≤2h-1，因此h≥log2(n+1)。由于h是整數，所以h≥log2(n+1)。二叉樹的性質滿二叉樹的定義：若高度為h的二叉樹具有最大數目（2h-1個）的結點，則稱其為滿二叉樹（fullbinarytree）。完全二叉樹的定義：若高度為h的二叉樹，除第h層外，其它各層(1h-1)的結點數都達到最大個數，并且第h層的結點是自左向右連續(xù)分布的。則稱它為完全二叉樹（completebinarytree）。二叉樹的性質性質4：具有n個結點的完全二叉樹的高度為log2(n+1)

。證明：設完全二叉樹的高度為h，則由性質2得：2h-1-1＜n≤2h-12h-1＜n+1≤2h

不等式中的各項取對數得：h-1＜log2(n+1)≤h。因為h為整數，所以h=log2(n+1)。二叉樹的性質性質5：如果將一棵有n個結點的完全二叉樹自頂向下，同一層自左向右連續(xù)給結點編號0、1、2、…、n-1。則有以下關系：（1）若i＝0，則i無雙親，若i＞0，則i的雙親為i/2-1；（2）若2*i+1<n，則i的左孩子為2*i+1；（3）若2*i+2<n，則i的右孩子為2*i+2；（4）若i為偶數，且i≥1，則i是其雙親的右孩子，且其有編號為i-1左兄弟；（5）若i為奇數，且i＜n-1，則i是其雙親的左孩子，且其有編號為i+1右兄弟。二叉樹的性質證明：此性質可以用歸納法證明，在此先證明其中的(2)和(3)。當i＝0時，由完全二叉樹的定義得知，如果2*i+1＝1<n，說明二叉樹中存在兩個或兩個以上的結點，所以結點i的左孩子存在且編號為1；反之，如果2*i+1＝1=n，說明二叉樹中只有一個結點i，結點i的左孩子結點不存在。同理，如果2i+2＝2<n，說明結點i的右孩子存在且編號為2；如果2*i+2＝2=n，說明二叉樹中不存在編號為2的結點，即結點i的右孩子不存在。二叉樹的性質

假設對于編號為j(0＜j＜i）的結點，(2)和(3)成立。當i＝j+1時，根據完全二叉樹的定義，若其左孩子結點存在則其左孩子結點的編號等于編號為j的結點的右孩子的編號加1，即其左孩子結點的編號等于2*j+2+1＝2*i+1；同樣，當i＝j+1時，根據完全二叉樹的定義，若其右孩子結點存在，則其右孩子結點的編號等于其左孩子結點的編號加1，即其右孩子結點的編號等于2i+1+1=2*i+2，因此性質5的(2)，(3)得證。二叉樹的性質

由上述(2)和(3)可很容易證明(1)，證明如下：當i＝0時，顯然該結點為根結點，所以它沒有雙親結點。當i＞0時，設編號為i的結點的雙親結點的編號為f。如果i是其雙親結點的左孩子結點，根據性質5的(2)有i＝2*f+1（i為奇數），即f＝(i-1)/2；如果結點i是其雙親結點的右孩子結點，根據性質5的(3)有i＝2*f+2（i為偶數），即f＝i/2-1。綜合這兩種情況可以得到，當i＞0時，其雙親結點的編號等于i/2-1。因此性質5的(1)得證。二叉樹的性質（1）IsEmpty()（2）Root()（3）CreateRoot(d)（4）Parent(p)（5）LeftChild(p)（6）RightChild(p)（7）LeftSibling(p)（8）RightSibling(p)（9）Retrieve(p)二叉樹的基本操作（10）Assign(p，d)（11）InsertLeftChild(p,d)（12）InsertRightChild(p,d)（13）DeleteLeftChild(p)（14）DeleteRightChild(p)（15）PreOrderTravers（）（16）InOrderTravers（）（17）PostOrderTravers（）（18）LevelOrderTravers（）6.3二叉樹的存儲結構1、數組表示法2、二叉鏈表表示法

6.3二叉樹的存儲結構3、三叉鏈表表示法

6.3二叉樹的存儲結構template<classElemType>structBinTreeNode{ ElemTypedata; //數據域

BinTreeNode<ElemType>*leftChild; //左孩子指針域

BinTreeNode<ElemType>*rightChild; //右孩子指針域 BinTreeNode(); //無參數的構造函數

BinTreeNode(constElemType&val

BinTreeNode<ElemType>*lChild=NULL, BinTreeNode<ElemType>*rChild=NULL);};二叉鏈表中結點的類模板template<classElemType>BinTreeNode<ElemType>::BinTreeNode(){ leftChild=rightChild=NULL; }二叉鏈表中結點的類模板template<classElemType>BinTreeNode<ElemType>::BinTreeNode(constElemType&val, BinTreeNode<ElemType>*lChild,BinTreeNode<ElemType>*rChild){ data=val; //數據元素值

leftChild=lChild; //左孩子

rightChild=rChild; //右孩子}二叉鏈表中結點的類模板template<classElemType>classBinaryTree{protected:BinTreeNode<ElemType>*root;BinTreeNode<ElemType>*CopyTree(BinTreeNode<ElemType>*t);

voidDestroy(BinTreeNode<ElemType>*&r);voidPreOrder(BinTreeNode<ElemType>*r,

void(*Visit)(constElemType&))const;

voidInOrder(BinTreeNode<ElemType>*r,

void(*Visit)(constElemType&))const;

voidPostOrder(BinTreeNode<ElemType>*r,

void(*Visit)(constElemType&))const;二叉鏈表類模板定義intHeight(constBinTreeNode<ElemType>*r)const;

intNodeCount(constBinTreeNode<ElemType>*r)const;

BinTreeNode<ElemType>*Parent(BinTreeNode<ElemType>*r, constBinTreeNode<ElemType>*p)const;二叉鏈表類模板定義public:BinaryTree(); virtual~BinaryTree();BinTreeNode<ElemType>*GetRoot()const;boolIsEmpty()const;StatusGetElem(BinTreeNode<ElemType>*p,ElemType&e)const;StatusSetElem(BinTreeNode<ElemType>*p,constElemType&e);voidInOrder(void(*Visit)(constElemType&))const;

voidPreOrder(void(*Visit)(constElemType&))const;voidPostOrder(void(*Visit)(constElemType&))const;voidLevelOrder(void(*Visit)(constElemType&))const;intNodeCount()const; 二叉鏈表類模板定義BinTreeNode<ElemType>*LeftChild(constBinTreeNode<ElemType>*p)const;BinTreeNode<ElemType>*RightChild(constBinTreeNode<ElemType>*p)const;BinTreeNode<ElemType>*Parent(constBinTreeNode<ElemType>*p)const;BinTreeNode<ElemType>*Parent(constBinTreeNode<ElemType>*p)const;

voidInsertLeftChild(BinTreeNode<ElemType>*p,constElemType&e);voidInsertRightChild(BinTreeNode<ElemType>*p,constElemType&e);voidDeleteLeftChild(BinTreeNode<ElemType>*p);voidDeleteRightChild(BinTreeNode<ElemType>*p);

int

Height()const; BinaryTree(constBinaryTree<ElemType>&t);BinaryTree(BinTreeNode<ElemType>*r); BinaryTree<ElemType>&operator=(constBinaryTree<ElemType>&t);};二叉鏈表類模板定義template<classElemType>voidBinaryTree<ElemType>::Destroy(BinTreeNode<ElemType>*&r){

if(r!=NULL) { Destroy(r->leftChild); Destroy(r->rightChild);

deleter; r=NULL; }}刪除以r為根的二叉樹Template<classElemType>BinTreeNode<ElemType>*BinaryTree<ElemType>::Parent(BinTreeNode<ElemType>*r,

constBinTreeNode<ElemType>*p)const{if(r==NULL)returnNULL; //空二叉樹

else

if(r->leftChild==p||r->rightChild==p)returnr; else{BinTreeNode<ElemType>*tmp; tmp=Parent(r->leftChild,p);

if(tmp!=NULL)returntmp; tmp=Parent(r->rightChild,p);

if(tmp!=NULL)returntmp;

else

returnNULL; }}在以r為根的二叉樹中求結點p的雙親template<classElemType>BinTreeNode<ElemType>*BinaryTree<ElemType>::LeftSibling(constBinTreeNode<ElemType>*p)const{BinTreeNode<ElemType>*r=Parent(root,p);

if(r==NULL)

returnNULL;

else

if(r->rightChild==p)

returnr->leftChild;

else

returnNULL;}求結點p的左兄弟template<classElemType>voidBinaryTree<ElemType>::InsertRightChild(BinTreeNode<ElemType>*p,constElemType&e){

if(p==NULL)return;

else {BinTreeNode<ElemType>*child=newBinTreeNode<ElemType>(e);

if(p->rightChild!=NULL) child->rightChild=p->rightChild;p->rightChild=child;

return;}}插入右孩子

二叉樹的遍歷是指按照某種順序訪問二叉樹中的每個結點，并使每個結點被訪問一次且只被訪問一次。6.4遍歷二叉樹先序遍歷(PreorderTraversal）：若二叉樹為空，遍歷結束。否則，（1）訪問根結點；（2）前序遍歷根結點的左子樹；（3）前序遍歷根結點的右子樹。

先序序列為：A、B、D、E、G、H、C、F、I。

先序遍歷template<classElemType>voidBinaryTree<ElemType>::PreOrder(BinTreeNode<ElemType>*r,

void(*Visit)(constElemType&))const{if(r!=NULL) { (*Visit)(r->data); PreOrder(r->leftChild,Visit); PreOrder(r->rightChild,Visit);}}先序遍歷以r為根的二叉樹voidBinaryTree<ElemType>::PreOrder(void(*Visit)(constElemType&))const{ PreOrder(root,Visit); }

先序遍歷二叉樹中序遍歷(InorderTraversal)：若二叉樹為空，遍歷結束。否則，（1）中序遍歷根結點的左子樹；（2）訪問根結點；（3）中序遍歷根結點的右子樹。中序序列為：D、B、G、E、H、A、C、F、I。中序遍歷template<classElemType>voidBinaryTree<ElemType>::InOrder(BinTreeNode<ElemType>*r,void(*Visit)(constElemType&))const{ if(r!=NULL) { InOrder(r->leftChild,Visit); (*Visit)(r->data); InOrder(r->rightChild,Visit); }}中序遍歷以r為根的二叉樹voidBinaryTree<ElemType>::InOrder(void(*Visit)(constElemType&))const{ InOrder(root,Visit); }

中序遍歷二叉樹后序遍歷(PostorderTraversal)：若二叉樹為空，遍歷結束。否則，（1）后序遍歷根結點的左子樹；（2）后序遍歷根結點的右子樹；（3）訪問根結點。后序序列為：D、G、H、E、B、I、F、C、A。后序遍歷template<classElemType>voidBinaryTree<ElemType>::PostOrder(BinTreeNode<ElemType>*r, void(*Visit)(constElemType&))const{

if(r!=NULL) { PostOrder(r->leftChild,Visit); PostOrder(r->rightChild,Visit); (*Visit)(r->data); }}后序遍歷以r為根的二叉樹voidBinaryTree<ElemType>::PostOrder(void(*Visit)(constElemType&))const{ PostOrder(root,Visit); } 后序遍歷二叉樹層序遍歷(LevelorderTraversal)：是指從二叉樹的第一層(根結點)開始，自上至下逐層遍歷，在同一層中，則按從左到右的順序對結點逐個訪問。層序遍歷層次序列：A、B、C、D、E、F、G、H、I。在進行層序遍歷時，需要設置一個隊列結構，并按下述步驟層序遍歷二叉樹：(1)初始化隊列，并將根結點入隊。(2)當隊列非空時，取出隊頭結點p，轉步驟3；如果隊列為空，則結束遍歷。(3)訪問結點p；如果該結點有左孩子，則將其左孩子入隊列；如果該結點有右孩子，則將其右孩子入隊列。(4)重復步驟(2)、(3)，直到隊列為空。層序遍歷template<classElemType>voidBinaryTree<ElemType>::LevelOrder(void(*Visit)(constElemType&))const{ LinkQueue<BinTreeNode<ElemType>*>q;

BinTreeNode<ElemType>*p;

if(root!=NULL)q.EnQueue(root);

while(!q.IsEmpty()) {

q.DelQueue(p);(*Visit)(p->data); if(p->leftChild!=NULL)q.EnQueue(p->leftChild);

if(p->rightChild!=NULL)q.EnQueue(p->rightChild);

}}層序遍歷

在遍歷二叉樹時，無論采用前面所講的哪一種方式進行遍歷，其基本操作都是訪問結點。所以，對具有n個結點的二叉樹，遍歷操作的時間復雜度均為O(n)。在前序、中序和后序遍歷的過程中，遞歸時棧所需要的空間最多等于樹的深度h乘以每個棧元素所需空間，在最壞的情況下，二叉樹的深度等于結點數目，所以空間復雜度為O(n)。在層序遍歷時，所設置隊列的大小顯然小于二叉樹中結點的個數，所以空間復雜度也為O(n)。利用二叉樹的遍歷可以實現許多關于二叉樹的運算，例如計算二叉樹的結點數目、計算二叉樹的高度、二叉樹的復制等。遍歷二叉樹template<classElemType>intBinaryTree<ElemType>::NodeCount(constBinTreeNode<ElemType>*r)const{ if(r==NULL)return0; elsereturnNodeCount(r->leftChild)

+NodeCount(r->rightChild)+1;}求以r為根的二叉樹的結點個數template<classElemType>intBinaryTree<ElemType>::Height(constBinTreeNode<ElemType>*r)const

{ if(r==NULL) //空二叉樹高為0 return0; else { intlHeight,rHeight; lHeight=Height(r->leftChild); //左子樹的高

rHeight=Height(r->rightChild); //右子樹的高

return(lHeight>rHeight?lHeight:rHeight)+1; }}求以r為根的二叉樹的高已知二叉樹的前序序列和中序序列構造二叉樹前序序列：ABCDEFGHI中序序列：DCBAGFHEI根據前序序列和中序序列構造二叉樹template<classElemType>voidCreateBinaryTree(BinTreeNode<ElemType>*&r,ElemTypepre[],ElemTypein[],intpreLeft,intpreRight,intinLeft,intinRight){if(inLeft>inRight)

r=NULL;else{ //二叉樹有結點,非空二叉樹

r=newBinTreeNode<ElemType>(pre[preLeft]);//生成根結點

intmid=inLeft;while(in[mid]!=pre[preLeft])

mid++;CreateBinaryTree(r->leftChild,pre,in,preLeft+1,preLeft+mid-inLeft,inLeft,mid-1);

CreateBinaryTree(r->rightChild,pre,in,preLeft+mid-inLeft+1,preRight,mid+1, inRight); }}根據前序序列和中序序列構造二叉樹template<classElemType>voidDisplayBTWithTreeShape(BinTreeNode<ElemType>*r,intlevel){ if(r!=NULL) { //空樹不顯式，只顯式非空樹

DisplayBTWithTreeShape<ElemType>(r->rightChild,level+1);

cout<<endl;

for(inti=0;i<level-1;i++) cout<<“”;

cout<<r->data; //顯示結點

DisplayBTWithTreeShape<ElemType>(r->leftChild,level+1); }}顯示以r為根的二叉樹template<classElemType>voidDisplayBTWithTreeShape(BinaryTree<ElemType>&bt){ DisplayBTWithTreeShape<ElemType>(bt.GetRoot(),1);

cout<<endl;}樹狀形式顯示二叉樹表達式：(3*(a+b)+c-1/d)/5表達式的二叉樹表示前綴表達式：/-+*3+abc/1d5中綴表達式：3*a+b+c-1/d/5后綴表達式：3ab+*c+1d/-5/6.5線索二叉樹中序序列：DBGEACF先序序列：ABDEGCF后序序列：DGEBFCA在每個結點中增設兩個標志位leftTag和rightTag，令：當leftTag=0時,

leftChild為左孩子指針當leftTag=1時, leftChild為前驅線索當rightTag=0時, rightChild為右孩子指針當rightTag=1時, rightChild為后繼指針6.5線索二叉樹template<classElemType>structThreadBinTreeNode{ ElemTypedata; ThreadBinTreeNode<ElemType>*leftChild; ThreadBinTreeNode<ElemType>*rightChild;

intleftTag,rightTag; ThreadBinTreeNode(); ThreadBinTreeNode(constElemType&d, ThreadBinTreeNode<ElemType>*lChild=NULL, ThreadBinTreeNode<ElemType>*rChild=NULL,

intleftTag=0, intrightTag=0);};線索二叉樹結點的類模板定義template<classElemType>classInThreadBinTree{protected:ThreadBinTreeNode<ElemType>*root;voidInThreadHelp(ThreadBinTreeNode<ElemType>*p,ThreadBinTreeNode<ElemType>*&pre);ThreadBinTreeNode<ElemType>*TransformHelp(BinTreeNode<ElemType>*r);ThreadBinTreeNode<ElemType>*CopyTreeHelp( ThreadBinTreeNode<ElemType>*t); voidDestroyHelp(ThreadBinTreeNode<ElemType>*&r);public:InThreadBinTree(constBinaryTree<ElemType>&bt);virtual~InThreadBinTree();ThreadBinTreeNode<ElemType>*GetRoot()const;中序線索二叉樹的類模板定義void

InThread();ThreadBinTreeNode<ElemType>*GetFirst()const;ThreadBinTreeNode<ElemType>*GetLast()const;ThreadBinTreeNode<ElemType>*GetNext(ThreadBinTreeNode<ElemType>*p);voidInsertRightChild(ThreadBinTreeNode<ElemType>*p,

constElemType&e);voidDeleteLeftChild(ThreadBinTreeNode<ElemType>*p);voidInOrder(void(*Visit)(constElemType&))const;InThreadBinTree(constInThreadBinTree<ElemType>&t);InThreadBinTree<ElemType>&operator=(constInThreadBinTree<ElemType>&t);};中序線索二叉樹的類模板定義template<classElemType>voidInThreadBinTree<ElemType>::InThreadHelp(ThreadBinTreeNode<ElemType>*p,ThreadBinTreeNode<ElemType>*&pre){if(p!=NULL) { InThreadHelp(p->leftChild,pre);

if(p->leftChild==NULL) { p->leftChild=pre; p->leftTag=1; }

else p->leftTag=0;

if(pre!=NULL&&pre->rightChild==NULL) { pre->rightChild=p;pre->rightTag=1; }

else

if(pre!=NULL)pre->rightTag=0; pre=p; InThreadHelp(p->rightChild,pre); }}中序線索化以p為根的二叉樹template<classElemType>voidInThreadBinTree<ElemType>::InThread(){ ThreadBinTreeNode<ElemType>*pre=NULL; InThreadHelp(root,pre); pre->rightTag=1;}建立中序線索二叉樹template<classElemType>ThreadBinTreeNode<ElemType>*InThreadBinTree<ElemType>::GetFirst()const{if(root==NULL)

returnNULL;

else{ThreadBinTreeNode<ElemType>*p=root;

while(p->leftTag==0) p=p->leftChild;

returnp;}}尋找中序序列中第一個結點template<classElemType>ThreadBinTreeNode<ElemType>*InThreadBinTree<ElemType>::GetNext(ThreadBinTreeNode<ElemType>*p)const{if(p->rightTag==1)p=p->rightChild;

else{ p=p->rightChild;

while(p->leftTag==0) p=p->leftChild;}

returnp;}尋找指定結點p的后繼template<classElemType>voidInThreadBinTree<ElemType>::InOrder(void(*Visit)(constElemType&))const{ThreadBinTreeNode<ElemType>*p;for(p=GetFirst();p!=NULL;p=GetNext(p)) { (*Visit)(p->data);

if(p->leftTag==1)cout<<"其左指針為線索指針，指向";

else

cout<<"其左指針為孩子指針，指向";

if(p->leftChild!=NULL)cout<<p->leftChild->data;

else

cout<<"NULL";

if(p->rightTag==1)cout<<"；其右指針為線索指針，指向";

else

cout<<"；其右指針為孩子指針，指向";

if(p->rightChild!=NULL)cout<<p->rightChild->data<<endl;

else

cout<<"NULL"<<endl;}}中序線索二叉樹的中序遍歷在中序線索二叉樹上插入右孩子結點template<classElemType>voidInThreadBinTree<ElemType>::InsertRightChild(ThreadBinTreeNode<ElemType>*p,constElemType&e){ThreadBinTreeNode<ElemType>*x,*q;

if(p==NULL) return;

else{x=newThreadBinTreeNode<ElemType>(e,p,p->rightChild,1,p->rightTag);//生成元素值為e結點x

if(p->rightTag==0) {q=p->rightChild;

while(q->leftTag==0)q=q->leftChild;q->leftChild=x;}p->rightChild=x;p->rightTag=0;

return;}}在中序線索二叉樹上插入右孩子結點在中序線索二叉樹上刪除左子樹template<classElemType>voidInThreadBinTree<ElemType>::DeleteLeftChild(ThreadBinTreeNode<ElemType>*p){ThreadBinTreeNode<ElemType>*x,*q;

if(p==NULL||p->leftTag!=0) return;else { q=p->leftChild;

while(q->leftTag==0)q=q->leftChild;q=q->leftChild;DestroyHelp(p->leftChild);p->leftChild=q;p->leftTag=1;

return;}}在中序線索二叉樹上刪除左子樹6.6二叉樹的應用1、堆2、哈夫曼樹與哈夫曼編碼1．堆的定義設有n個數據元素的關鍵字為（k0、k1、…、kn-1），如果它們滿足以下的關系：ki<=k2i+1且ki<=k2i+2（或ki>=k2i+1且ki>=k2i+2）（i=0、1、…、(n-2)/2）則稱之為堆(Heap)。如果將此數據元素序列用一維數組存儲，并將此數組對應一棵完全二叉樹，則堆的含義可以理解為：在完全二叉樹中任何非終端結點的關鍵字均不大于（或不小于）其左、右孩子結點的關鍵字。堆堆最小堆的類模板定義template<classElemType>classMinHeap{private: ElemType*heapArr;

intCurrentSize;

intMaxSize;

voidFilterDown(intStart);

voidFilterUp(intEnd);最小堆的類模板定義public: MinHeap(intmaxSize); MinHeap(ElemTypea[],intmaxsize,intn); ~MinHeap(){delete[]heapArr;} StatusInsert(constElemType&e); StatusDeleteTop(ElemType&e); StatusGetTop(ElemType&e)const;

boolIsEmpty()const{returnCurrentSize==0;}

boolIsFull()const{returnCurrentSize==MaxSize;}

intSizeOfHeap()const{returnCurrentSize;}

voidSetEmpty(){CurrentSize=0;}

voidTraverse(void(*Visit)(constElemType&))const;};構造空堆template<classElemType>MinHeap<ElemType>::MinHeap(intmaxSize){

if(maxSize<=0) { cerr<<"堆的大小不能小于1"<<endl; exit(1); } MaxSize=maxSize; heapArr=newElemType[MaxSize]; CurrentSize=0;}向下調整算法向下調整算法template<classElemType>voidMinHeap<ElemType>::FilterDown(const

intStart){

inti=Start,j;ElemTypetemp=heapArr[i];j=2*i+1; while(j<=CurrentSize-1){

if(j<CurrentSize-1&&heapArr[j]>heapArr[j+1]) j++;

if(temp<=heapArr[j])break;

else{ heapArr[i]=heapArr[j];i=j;j=2*j+1; }}heapArr[i]=temp;}根據數組元素構造堆根據數組元素構造堆template<classElemType>MinHeap<ElemType>::MinHeap(ElemTypea[],intmaxSize,intn){if(n<=0) { cerr<<"堆的大小不能小于1"<<endl;exit(1);}MaxSize=maxSize;heapArr=newElemType[MaxSize];

for(inti=0;i<n;i++)heapArr[i]=a[i];CurrentSize=n; inti=(CurrentSize-2)/2;while (i>=0) { FilterDown(i); i--; Traverse(Write<ElemType>); cout<<endl;}}在堆中插入元素在堆中插入元素template<classElemType>StatusMinHeap<ElemType>::Insert(constElemType&e){

if (IsFull())

returnOVER_FLOW; heapArr[CurrentSize]=e; FilterUp(CurrentSize); CurrentSize++;

returnSUCCESS;}向上調整算法template<classElemType>voidMinHeap<ElemType>::FilterUp(intEnd){intj=End,i;ElemTypetemp=heapArr[j];i=(j-1)/2;while(j>0) {

if(heapArr[i]<=temp)break;

else{ heapArr[j]=heapArr[i]; j=i; i=(j-1)/2; } heapArr[j]=temp;}}在堆中刪除元素在堆中刪除元素template<classElemType>StatusMinHeap<ElemType>::DeleteTop(ElemType&e){

if(IsEmpty())

returnUNDER_FLOW; e=heapArr[0]; heapArr[0]=heapArr[CurrentSize-1]; CurrentSize--; FilterDown(0);

returnSUCCESS;}1．哈夫曼樹的基本概念在一棵二叉樹中由根結點到某個結點所經過的分支序列叫做由根結點到這個結點的路徑，由根結點到某個結點所經過的分支數稱為由根結點到該結點的路徑長度。由根結點到所有葉結點的路徑長度之和稱為該二叉樹的路徑長度。如果二叉樹中每一個葉結點都帶有某一確定值，就可以將二叉樹的路徑長度的概念加以推廣。設一棵具有n個帶權值葉結點的二叉樹，那么從根結點到各個葉結點的路徑長度與對應葉結點權值的乘積之和叫做二叉樹的帶權路徑長度，記作：其中Wk為第k個葉結點的權值，Lk為第K個葉結點的路徑長度。哈夫曼樹例如，給定4個葉子結點，其權值分別為（3、5、9、12）。它們的帶權路徑長度為分別為58、54和76。哈夫曼樹由此可見，對于一組確定權值的葉結點，所構造出的不同形態(tài)二叉樹的帶權路徑長度并不相同。在此把其中具有最小帶權路徑長度的二叉樹稱為最優(yōu)二叉樹，最優(yōu)二叉樹也稱為哈夫曼樹，（1）由給定的n個權值{W1、W2、…、Wn}構造n棵只有一個根結點（亦為葉結點）的二叉樹，從而得到一個森林F={T1、T2、…、Tn}；（2）在F中選取兩棵根結點的權值最小的二叉樹Ti、Tj，以Ti和Tj作為左、右子樹構造一棵新的二叉樹Tk。置新的二叉樹Tk的根結點的權值為其左、右子樹（Ti、Tj）上根結點的權值之和；（3）在F中刪去二叉樹Ti、Tj；并把新的二叉樹Tk加入F；（4）重復（2）和（3）步驟,直到F中僅剩下一棵樹為止。構造哈夫曼樹的步驟構造哈夫曼樹的步驟在數據通信中，經常需要將傳送的電文轉換成由二進制數字0、1組成的串，一般稱之為編碼。例如，假設要傳送的電文為AADDBCAAABDDCADAAADD，電文中只有A、B、C、D四種字符；若這四種字符的編碼分別為：A(00)、B(01)、C(10)、D(11)，則電文的代碼為：0000111101100000000111111000110000001111，電文代碼的長度為40。在這種編碼方案中，四種字符的編碼長度均為2，這是一種等長編碼。哈夫曼樹在編碼問題中的應用如果這四種字符的編碼分別為：A(0)、B(1)、C(10)、D(01)，則用此編碼方案對上述電文進行編碼得到的電文代碼為：00010111000010101100010000101，此電文代碼的長度只有29。前綴碼要求任一字符的編碼均非其他字符編碼的前綴。哈夫曼樹在編碼問題中的應用哈夫曼樹在編碼問題中的應用對于一段電文：AADDBCAAABDDCADAAADDCDDBAACCA。其字符集合為：{A、B、C、D}，各個字符出現的頻率(次數)是W＝{12、3、5、9}。若給每個字符以等長編碼：A(00)、B(10)、C(01)、D(11)。則電文代碼的長度為：(12+3+5+9)*2=58。因各字符出現的頻率為{12/29、3/29、5/29、9/29}，化成整數為{12、3、5、9}，以它們?yōu)楦魅~結點上的權值，建立哈夫曼樹，如圖6-23所示，得哈夫曼編碼為：A(0)、B(100)、C(101)、D(11)。它的總代碼長度：12*1+(3+5)*2+9*3=54。哈夫曼樹在編碼問題中的應用template<classWeightType>structHuffmanTreeNode{ WeightTypeweight;

intparent,leftChild,rightChild; HuffmanTreeNode(); HuffmanTreeNode(WeightTypew,intp=-1,intlChild=-1,intrChild=-1);};哈夫曼樹的結點類模板的定義template<classCharType,classWeightType>classHuffmanTree{protected:HuffmanTreeNode<WeightType>*nodes;CharType*LeafChars;String*LeafCharCodes;intnum;哈夫曼樹的類模板的定義voidSelect(intn,int&r1,int&r2);voidCreatHuffmanTree(CharTypech[],WeightTypew[],intn);public:HuffmanTree(CharTypech[],WeightTypew[],intn); virtual~HuffmanTree();StringEncode(CharTypech);LinkList<CharType>Decode(StringstrCode);HuffmanTree(constHuffma