第6章樹和二叉樹

數(shù)據(jù)結(jié)構(gòu)—C++實現(xiàn)繆淮扣沈俊顧訓(xùn)穰上海大學(xué)計算機(jī)工程與科學(xué)學(xué)院2014年6月第6章樹和二叉樹樹的概念二叉樹二叉樹的存儲結(jié)構(gòu)遍歷二叉樹線索二叉樹二叉樹的應(yīng)用樹和森林的實現(xiàn)等價類及其表示6.1樹的概念樹（tree）T是一個包含n(n>=0)個數(shù)據(jù)元素的有限集合。并且有：（1）當(dāng)n=0時，T稱為空樹；（2）如果n>0，則樹有且僅有一個特定的被稱為根（root）的結(jié)點，樹的根結(jié)點只有后繼，沒有前驅(qū)；（3）當(dāng)n>1時,除根結(jié)點以外的其余結(jié)點可分為m(m>0)個互不相交的非空有限集T1、T2、...、Tm,其中每一個集合本身又是一棵非空樹,并且稱它們?yōu)楦Y(jié)點的子樹（subtree）。樹的概念樹的概念樹的術(shù)語1．結(jié)點2．結(jié)點的度3．終端結(jié)點4．非終端結(jié)點5．樹的度6．孩子和雙親7．兄弟樹的術(shù)語8．祖先9．子孫10．結(jié)點的層次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是有限個結(jié)點的集合。當(dāng)集合非空時，其中有一個結(jié)點稱為二叉樹的根結(jié)點，用BT表示，余下的結(jié)點（如果有的話）最多被組成兩棵分別被稱為BT的左子樹（leftsubtree）和右子樹（rightsubtree）、互不相交的二叉樹。二叉樹的五種形態(tài):性質(zhì)1：有n(n>0)個結(jié)點的二叉樹的分支數(shù)為n-1。證明：因為在二叉樹中，除根結(jié)點以外的其它每個結(jié)點有且僅有一個父結(jié)點。而子結(jié)點與父結(jié)點間有且只有一條分支，因此對于有n(n>0)個結(jié)點的二叉樹，其分支的數(shù)目為n-1。二叉樹的性質(zhì)性質(zhì)2：若二叉樹的高度為h（h≥0），則該二叉樹最少有h個結(jié)點，最多有2h-1個結(jié)點。證明：因為在二叉樹中，每一層至少要有1個結(jié)點，因此對于高度為h的二叉樹，其結(jié)點數(shù)至少為h個。在二叉樹中，第一層只有一個根結(jié)點；又因為每個結(jié)點最多有2個孩子結(jié)點，所以第i層的結(jié)點最多為2i-1個，所以高度為h（h≥0）的二叉樹結(jié)點總數(shù)最多為：20+21+…+2h-1=2h-1二叉樹的性質(zhì)性質(zhì)3：含有n個結(jié)點的二叉樹的高度最大值為n，最小值為log2(n+1)

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

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

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

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

由上述(2)和(3)可很容易證明(1)，證明如下：當(dāng)i＝0時，顯然該結(jié)點為根結(jié)點，所以它沒有雙親結(jié)點。當(dāng)i＞0時，設(shè)編號為i的結(jié)點的雙親結(jié)點的編號為f。如果i是其雙親結(jié)點的左孩子結(jié)點，根據(jù)性質(zhì)5的(2)有i＝2*f+1（i為奇數(shù)），即f＝(i-1)/2；如果結(jié)點i是其雙親結(jié)點的右孩子結(jié)點，根據(jù)性質(zhì)5的(3)有i＝2*f+2（i為偶數(shù)），即f＝i/2-1。綜合這兩種情況可以得到，當(dāng)i＞0時，其雙親結(jié)點的編號等于i/2-1。因此性質(zhì)5的(1)得證。二叉樹的性質(zhì)（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二叉樹的存儲結(jié)構(gòu)1、數(shù)組表示法2、二叉鏈表表示法

6.3二叉樹的存儲結(jié)構(gòu)3、三叉鏈表表示法

6.3二叉樹的存儲結(jié)構(gòu)template<classElemType>structBinTreeNode{ ElemTypedata; //數(shù)據(jù)域

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

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

BinTreeNode(constElemType&val

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

leftChild=lChild; //左孩子

rightChild=rChild; //右孩子}二叉鏈表中結(jié)點的類模板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為根的二叉樹中求結(jié)點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;}求結(jié)點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;}}插入右孩子

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

先序序列為：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)：若二叉樹為空，遍歷結(jié)束。否則，（1）中序遍歷根結(jié)點的左子樹；（2）訪問根結(jié)點；（3）中序遍歷根結(jié)點的右子樹。中序序列為：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)：若二叉樹為空，遍歷結(jié)束。否則，（1）后序遍歷根結(jié)點的左子樹；（2）后序遍歷根結(jié)點的右子樹；（3）訪問根結(jié)點。后序序列為：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)：是指從二叉樹的第一層(根結(jié)點)開始，自上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點逐個訪問。層序遍歷層次序列：A、B、C、D、E、F、G、H、I。在進(jìn)行層序遍歷時，需要設(shè)置一個隊列結(jié)構(gòu)，并按下述步驟層序遍歷二叉樹：(1)初始化隊列，并將根結(jié)點入隊。(2)當(dāng)隊列非空時，取出隊頭結(jié)點p，轉(zhuǎn)步驟3；如果隊列為空，則結(jié)束遍歷。(3)訪問結(jié)點p；如果該結(jié)點有左孩子，則將其左孩子入隊列；如果該結(jié)點有右孩子，則將其右孩子入隊列。(4)重復(fù)步驟(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);

}}層序遍歷

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

+NodeCount(r->rightChild)+1;}求以r為根的二叉樹的結(jié)點個數(shù)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為根的二叉樹的高已知二叉樹的前序序列和中序序列構(gòu)造二叉樹前序序列：ABCDEFGHI中序序列：DCBAGFHEI根據(jù)前序序列和中序序列構(gòu)造二叉樹template<classElemType>voidCreateBinaryTree(BinTreeNode<ElemType>*&r,ElemTypepre[],ElemTypein[],intpreLeft,intpreRight,intinLeft,intinRight){if(inLeft>inRight)

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

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

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); }}根據(jù)前序序列和中序序列構(gòu)造二叉樹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; //顯示結(jié)點

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

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

leftChild為左孩子指針當(dāng)leftTag=1時, leftChild為前驅(qū)線索當(dāng)rightTag=0時, rightChild為右孩子指針當(dāng)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);};線索二叉樹結(jié)點的類模板定義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;}}尋找中序序列中第一個結(jié)點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;}尋找指定結(jié)點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;}}中序線索二叉樹的中序遍歷在中序線索二叉樹上插入右孩子結(jié)點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結(jié)點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;}}在中序線索二叉樹上插入右孩子結(jié)點在中序線索二叉樹上刪除左子樹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二叉樹的應(yīng)用1、堆2、哈夫曼樹與哈夫曼編碼1．堆的定義設(shè)有n個數(shù)據(jù)元素的關(guān)鍵字為（k0、k1、…、kn-1），如果它們滿足以下的關(guān)系：ki<=k2i+1且ki<=k2i+2（或ki>=k2i+1且ki>=k2i+2）（i=0、1、…、(n-2)/2）則稱之為堆(Heap)。如果將此數(shù)據(jù)元素序列用一維數(shù)組存儲，并將此數(shù)組對應(yīng)一棵完全二叉樹，則堆的含義可以理解為：在完全二叉樹中任何非終端結(jié)點的關(guān)鍵字均不大于（或不小于）其左、右孩子結(jié)點的關(guān)鍵字。堆堆最小堆的類模板定義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;};構(gòu)造空堆template<classElemType>MinHeap<ElemType>::MinHeap(intmaxSize){

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

intparent,leftChild,rightChild; HuffmanTreeNode(); HuffmanTreeNode(WeightTypew,intp=-1,intlChild=-1,intrChild=-1);};哈夫曼樹的結(jié)點類模板的定義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