第6章樹(shù)和二叉樹(shù)

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

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

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

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

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

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

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

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

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

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

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

BinTreeNode(constElemType&val

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

leftChild=lChild; //左孩子

rightChild=rChild; //右孩子}二叉鏈表中結(jié)點(diǎn)的類(lèi)模板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;二叉鏈表類(lèi)模板定義intHeight(constBinTreeNode<ElemType>*r)const;

intNodeCount(constBinTreeNode<ElemType>*r)const;

BinTreeNode<ElemType>*Parent(BinTreeNode<ElemType>*r, constBinTreeNode<ElemType>*p)const;二叉鏈表類(lèi)模板定義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; 二叉鏈表類(lèi)模板定義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);};二叉鏈表類(lèi)模板定義template<classElemType>voidBinaryTree<ElemType>::Destroy(BinTreeNode<ElemType>*&r){

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

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

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

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為根的二叉樹(shù)中求結(jié)點(diǎn)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é)點(diǎn)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;}}插入右孩子

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

先序序列為：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為根的二叉樹(shù)voidBinaryTree<ElemType>::PreOrder(void(*Visit)(constElemType&))const{ PreOrder(root,Visit); }

先序遍歷二叉樹(shù)中序遍歷(InorderTraversal)：若二叉樹(shù)為空，遍歷結(jié)束。否則，（1）中序遍歷根結(jié)點(diǎn)的左子樹(shù)；（2）訪問(wèn)根結(jié)點(diǎn)；（3）中序遍歷根結(jié)點(diǎn)的右子樹(shù)。中序序列為：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為根的二叉樹(shù)voidBinaryTree<ElemType>::InOrder(void(*Visit)(constElemType&))const{ InOrder(root,Visit); }

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

}}層序遍歷

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

+NodeCount(r->rightChild)+1;}求以r為根的二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)template<classElemType>intBinaryTree<ElemType>::Height(constBinTreeNode<ElemType>*r)const

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

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

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

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

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

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)造二叉樹(shù)template<classElemType>voidDisplayBTWithTreeShape(BinTreeNode<ElemType>*r,intlevel){ if(r!=NULL) { //空樹(shù)不顯式，只顯式非空樹(shù)

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

cout<<endl;

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

cout<<r->data; //顯示結(jié)點(diǎn)

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

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

leftChild為左孩子指針當(dāng)leftTag=1時(shí), leftChild為前驅(qū)線索當(dāng)rightTag=0時(shí), rightChild為右孩子指針當(dāng)rightTag=1時(shí), rightChild為后繼指針6.5線索二叉樹(shù)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);};線索二叉樹(shù)結(jié)點(diǎn)的類(lèi)模板定義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;中序線索二叉樹(shù)的類(lèi)模板定義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);};中序線索二叉樹(shù)的類(lèi)模板定義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為根的二叉樹(shù)template<classElemType>voidInThreadBinTree<ElemType>::InThread(){ ThreadBinTreeNode<ElemType>*pre=NULL; InThreadHelp(root,pre); pre->rightTag=1;}建立中序線索二叉樹(shù)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;}}尋找中序序列中第一個(gè)結(jié)點(diǎn)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é)點(diǎn)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;}}中序線索二叉樹(shù)的中序遍歷在中序線索二叉樹(shù)上插入右孩子結(jié)點(diǎn)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é)點(diǎn)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;}}在中序線索二叉樹(shù)上插入右孩子結(jié)點(diǎn)在中序線索二叉樹(shù)上刪除左子樹(shù)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;}}在中序線索二叉樹(shù)上刪除左子樹(shù)6.6二叉樹(shù)的應(yīng)用1、堆2、哈夫曼樹(shù)與哈夫曼編碼1．堆的定義設(shè)有n個(gè)數(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ù)組存儲(chǔ)，并將此數(shù)組對(duì)應(yīng)一棵完全二叉樹(shù)，則堆的含義可以理解為：在完全二叉樹(shù)中任何非終端結(jié)點(diǎn)的關(guān)鍵字均不大于（或不小于）其左、右孩子結(jié)點(diǎn)的關(guān)鍵字。堆堆最小堆的類(lèi)模板定義template<classElemType>classMinHeap{private: ElemType*heapArr;

intCurrentSize;

intMaxSize;

voidFilterDown(intStart);

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

intparent,leftChild,rightChild; HuffmanTreeNode(); HuffmanTreeNode(WeightTypew,intp=-1,intlChild=-1,intrChild=-1);};哈夫曼樹(shù)的結(jié)點(diǎn)類(lèi)模板的定義template<classCharType,classWeightType>classHuffmanTree{protected:HuffmanTreeNode<WeightType>*nodes;CharType*LeafChars;String*LeafCharCodes;intnum;哈夫曼樹(shù)的類(lèi)模板的定義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