數據結構（數據結構及其算法）

馮耀霖1.

Chap6

樹（二）

樹與森林

搜索二叉樹

哈夫曼樹

堆

2.§1樹與森林

▲樹的存儲結構▲樹的實現3.1.1樹的存儲結構

關于樹的存儲結構有許多種，這里介紹常用的兩種。■父結點數組表示法■左孩子右兄弟表示法4.1.

父結點數組表示法

這是一種順序結構與鏈結構相結合的樹存儲方法，它以一組連續的存儲單元（數組）來存放樹中的結點。每個結點有兩個域：data域，存放數據元素；parent域，存放其父結點在數組中的位置序號（下標），相當于父結點的指針，其數值為0（或-1），則表示該結點無父結點，即它是根結點。如圖6-1所示樹，圖6-2所示該樹的父結點數組表示法結構。樹中結點的存放順序一般不做特殊要求。如圖6-2中使用的是層次方法。5.ABCDEFGIHJdataparentA0B1C1D1E2F3G4H7I7J7下標12345678910

圖6.1樹

圖6.2樹的父結點表示法6.2.左孩子右兄弟表示法左孩子右兄弟表示法是目前已知的最節省存儲空間的樹的鏈式存儲結構方法，它是一種基于遞歸的定義方式。它的每一個結點由三個域組成：data、leftChild和rightSibling。leftChild域存放的是該結點最左（第一個）孩子的地址，rightSibling域存放的是該結點右兄弟的地址。

leftChilddatarightSibling7.在圖6-1中，樹的根結點是A，它沒有兄弟，所以它的rightSibling值為空。A有三個孩子，分別為B、C和D，因此它的leftChild值是其最左孩子——結點B的地址。B既有孩子又有兄弟，它的rightSibling指向的是右鄰兄弟C，而leftChild指向的是其孩子E。結點E是B的唯一孩子且為葉子，所以它的leftChild值和rightSibling值均為空。依照上述規則可以很方便地建立起樹形結構的存儲模式。理解該表示方法的關鍵在于理解它的遞歸本質。為了幫助理解為什么僅通過每個結點的3個域就能實現整棵樹的存儲，下面給出對以圖6-1中樹的基于先序的遍歷過程。8.→先訪問根結點A。A無兄弟有左孩子，所以A不入棧，并訪問A的左孩子B；→結點B既有孩子也有兄弟，于是B入棧，并訪問它的左孩子E；→結點E是葉子，且無兄弟，所以遍歷過程回退到結點B；→訪問B的右兄弟C，C既有兄弟又有孩子，所以C入棧，并訪問C的左孩子F；→結點F是葉子，且無兄弟，所以遍歷過程回退到結點C；→訪問C的右兄弟D，D無兄弟但有孩子，所以D不入棧，并訪問D的左孩子G；9.→結點G無兄弟有孩子，所以G不入棧，并訪問G的左孩子H；→結點H是葉子，但有兄弟，所以H不入棧，并訪問H的右兄弟I;→結點I是葉子，但有兄弟，所以I不入棧，并訪問I的右兄弟J；→結點J是葉子，也無兄弟，且此時棧為空，至此整個遍歷過程結束。

由此可見，盡管左孩子右兄弟表示法的每個結點單元僅有3個域，但它們對構建樹形結構的復雜模型已經足夠了。10.1.2樹的實現

以左孩子右兄弟樹為例。

1.樹結點template<typenameType>structTreeNode{Typedata;TreeNode*leftChild,*rightSibling;//左孩子右兄弟指針};11.2.樹類

template<typenameType>classTree{private:TreeNode<Type>*root,*current;//根指針與當前指針<基本操作的內部成員函數原型聲明>public:<基本操作的外部成員函數原型聲明>};

12.3.基本操作的算法

SetCurNodeParentElemLeftChildRightSiblingAddNewChildInsertLeftChildInsertSibling13.算法6.1SetCurNode

功能：設置當前結點boolSetCurNode(Typee){//將值為e的結點設置為當前結點returnCurNode(root,e);}

算法6.2CurNode

功能：設置當前結點14.boolCurNode(TreeNode*r,Typee){//在根為r的樹中查找值為e的結點，將其設置為當前結點if(r==NULL)returnFALSE;if(r->data==e){current=r;returnTRUE;}if(CurNode(r->leftChild,e)==TRUE)//遞歸遍歷r的左孩子returnTRUE;TreeNode*p=r->rightSibling;while(p!=NULL){//遞歸遍歷r的右兄弟if(CurNode(p,e)==TRUE)returnTRUE;p=r->rightSibling;}returnFALSE;}15.算法6.3ParentElem

功能：查找父結點并讀取其元素boolParentElem(Typev,Type&e){//查找v結點的父結點，并讀取其元素if(v==root->data)returnFALSE;if(CurNode(root,v)==FALSE)returnFALSE;if(Parent(root,current)==FALSE)returnFALSE;e=current->data;returnTRUE;}16.算法6.4Parent

功能：查找父結點boolParent(TreeNode*r,TreeNode*k){//在根為r的樹中查找結點k的父結點，使其成為當前結點if(r==NULL)returnFALSE;TreeNode*cp=r->leftChild,*sp=cp->rightSibling;if(cp==k){current=r;returnTRUE;}if(Parent(cp->leftChild,k)==TRUE)//左孩子遞歸查找returnTRUE;17.while(sp!=NULL){if(sp==k){current=r;returnTRUE;}

//右兄弟的孩子的遞歸查找if(Parent(sp->leftChild,k)==TRUE)returnTRUE;sp=sp->rightSibling;}returnFALSE;}18.算法6.5LeftChild

功能：查找左孩子boolLeftChild(){//查找當前結點的左孩子，使其成為當前結點if((current!=NULL&¤t->leftChild!=NULL){current=current->leftChild;returnTRUE;}returnFALSE;}19.算法6.6RightSibling

功能：查找右兄弟boolRightSibling(){//查找當前結點的右兄弟，使其成為當前結點if(current!=NULL&¤t->rightSibling!=NULL){current=current->rightSibling;returnTRUE;}returnFALSE;}20.算法6.7AddNewChild

功能：添加孩子

boolAddNewChild(Typev,Typee){//元素e添加為元素v的結點的孩子if(CurNode(root,v)==FALSE)returnFALSE;

//設置元素為v的結點為當前結點AddChild(current,e);returnTRUE;}21.算法6.8AddChild

功能：添加孩子22.voidAddChild(TreeNode*x,Typee){//為結點x添加元素為e的孩子TreeNode*p=newTreeNode,*t;p->data=e;p->leftChild=p->Sibling=NULL;if(x->leftChild==NULL)x->leftChild=p;else{t=x->leftChild;while(t->rightSibling!=NULL)t=t->rightSibling;t->rightSibling=p;}}23.算法6.9InsertLeftChild

功能：插入左孩子voidInsertLeftChild(TreeNode*x,Typee){//將元素為e的結點插入為結點x的左孩子TreeNode*p=newTreeNode,*t;p->data=e;p->leftChild=NULL;p->Sibling=x->leftChild;x->leftChild=p;}24.算法6.10AddRightSibling

功能：添加右兄弟boolAddRightSibling(Typev,Typee){//元素e添加為元素v的右兄弟TreeNode*p;if(CurNode(root,v)==FALSE)returnFALSE;InsertSibling(current,e);returnTRUE;}25.算法6.11InsertSibling

功能：插入右兄弟voidInsertSibling(TreeNode*x,Typee){//將元素為e的結點插入為結點x的右兄弟TreeNode*p=newTreeNode;p->data=e;p->leftChild=NULL;if(x->rightSibling!=NULL)p->rightSibling=x->rightSibling;x->rightSibling=p;}26.1.3樹與森林的遍歷

樹的遍歷方式有兩種：深度優先遍歷和廣度優先遍歷。森林的遍歷主要采用的是深度優先方式。27.1.樹的深度優先遍歷可以分為兩種具體的形式：先序遍歷和后序遍歷。先序遍歷的規則：如果樹非空，則訪問其根結點，然后從左到右先序遍歷根的每棵子樹。后序遍歷的規則：如果樹非空，則從左到右后序遍歷根的每棵子樹，然后訪問根結點。28.ACBDEFGIHJADCBGFEJIH圖6.3樹的深度優先遍歷

先序遍歷ABECFDGHIJ(b)后序遍歷EBFCHIJGDA

29.算法6.12PreTreeOrder

功能：樹的先序深度優先遍歷

voidPreTreeOrder(TreeNode<Type>*r,void(*Visit)(Type&))//private{if(r!=NULL){Visit(r->data);TreeNode*p=r->leftChild;PreTreeOrder(p,Visit);//遞歸遍歷左孩子while(p->rightSibling!=NULL){//遞歸遍歷右兄弟PreTreeOrder(p->rightSibling,Visit);p=p->rightSibling;}}}30.2.廣度優先遍歷遵循的是分層訪問原則。首先訪問樹中深度為0的那一層中的結點，然后訪問深度為1的那一層中的結點，……，在訪問每一層結點的時候，遵循的原則是從左向右，直到樹中所有的結點都被訪問過。31.3.森林的遍歷主要采用的是深度優先方式，同樣可分為先序遍歷和后序遍歷兩種。森林的先序遍歷規則是：當森林非空時，按從左向右原則訪問森林的第一棵樹（最左樹）的根結點，然后先序遍歷第一棵樹的子森林，再以先序次序遍歷其他樹組成的森林。如果森林為空，則執行空操作。32.ABCDEFGIHJ圖6.4森林的先序遍歷

33.1.4森林與二叉樹的轉換二叉樹是一種結構最簡單、運算最簡便的樹形結構。但對許多問題來講，其自然的描述形態是樹或森林。因此，研究樹、森林和二叉樹之間的關系是有意義的。樹的左孩子右兄弟表示法就是將一棵樹表示成二叉樹的形態，這樣就可以將二叉樹中的許多方法應用在樹的處理中。反之，將一棵二叉樹的左孩子看成是樹的第一個孩子，右孩子看成是樹的第一個孩子的兄弟，可以將一棵二叉樹還原成一棵普通的樹。34.1.樹轉化為二叉樹

從左孩子右兄弟表示法可知，樹中每個結點最多只有一個最左的孩子和一個右鄰的兄弟，這就是兩者轉化操作實現的原理所在。將一棵樹轉化為二叉樹的方法如下：(1)樹中所有兄弟之間加一條連線；(2)對樹中的每個結點，只保留它與第一個孩子之間的連線，刪去它與其他孩子結點之間的連線；(3)以樹的根結點為軸心，將整棵樹順時針轉動一定的角度（使每個弟弟都變成其哥哥的右孩子），以使其結構層次分明。35.ABCEDFGHIACBEDFGHIABCDEGGFHI圖6.5樹與二叉樹的轉換36.2.森林轉化為二叉樹森林是若干棵樹的集合，只要將森林中各棵樹的根視為兄弟，每棵樹又可以用二叉樹表示（左孩子右兄弟），這樣森林也可以用二叉樹表示。將森林轉化為二叉樹的方法如下：(1)將森林中的每棵樹轉化成相應的二叉樹；(2)第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結點作為前一棵二叉樹根結點的右孩子，當所有二叉樹連起來后，此時所得到的二叉樹就是由森林轉換得到的二叉樹。37.ACBDEFGHIJABCDEFGHIJ圖6.6(a)森林與二叉樹的轉換38.ABCDEFGHIJ圖6.6(b)森林與二叉樹的轉換39.

§2哈夫曼樹

▲哈夫曼樹的應用▲哈夫曼樹的基本概念▲哈夫曼樹的構造算法▲哈夫曼編碼▲哈夫曼樹的實現40.2.1哈夫曼樹的應用

在數據膨脹、信息爆炸的今天，數據壓縮的意義不言而喻。談到數據壓縮，就不能不提到哈夫曼／霍夫曼（Huffman）編碼。哈夫曼編碼是一種有關數據壓縮的算法，它也是首個實用的壓縮編碼方案，該算法由哈夫曼（D.A.Huffman）于1952年提出。當時，哈夫曼就讀于麻省理工學院，為了向老師證明自己可以不參加某門功課的期末考試，他設計了這個看似簡單卻影響深遠的編碼方法。哈夫曼編碼效率高，運算速度快，實現方式靈活。從20世紀60年代開始，哈夫曼編碼在數據壓縮領域得到了廣泛應用。而20世紀80年代初，哈夫曼編碼又出現在CP/M和DOS系統中，即使在當今的許多知名的壓縮工具和壓縮算法里，依然可以見到哈夫曼編碼的影子。41.文本處理是計算機的重要應用之一。文本由字符組成。在計算機中每個字符用一個由0，1組成的二進制串表示，稱之為編碼。大多數計算機采用ASCII編碼。ASCII編碼是一種等長的編碼，每個字符的編碼長度是相同的。為了提高文本存儲和處理的效率，在某些場合希望采用不等長的編碼，讓使用頻率較高的字符有較短的編碼，而使用頻率較低的字符有較長的編碼，總體來講，保存文本的空間總量會減少，傳送文本的速度也會提高。42.例如給出一段文本：ABCDEACBDBDBDBCB在該文本中出現的字符集合為｛A,B,C,D,E｝，其中B出現的次數最多，為6次；其它依次為D＝4次，C=3次，A=2次，E=1次。首先采用定長編碼方法。要給5個字符進行編碼，最少需要三位二進制碼?？梢越o每個字符賦一個等長的三位二進制的編碼為A:000B:001C:010D:011E:100，將原始文本進行編碼后所得結果如下：000001010011100000010001011001011001011001010001編碼長度為57(bit)43.另一種方案是采用非等長編碼，將出現頻率最高的B用最少的編碼來表示，D用次少的編碼來表示，依次類推。如上述5個字符的二進制編碼為B:0D:10C:110A:1110E:1111，將原始文本進行編碼后所得結果如下：11100110101111111011001001001001100編碼長度為41(bit)顯然，采用非等長編碼可以減少文本占用的存儲空間。但怎樣找出這種優化的編碼呢？44.哈夫曼提出可用一種特定的二叉樹來生成優化編碼，這種二叉樹被稱為哈夫曼樹，也稱最優二叉樹，由哈夫曼樹生成的編碼稱為哈夫曼編碼。哈夫曼編碼不僅可應用于文本編碼，也同樣可應用于圖象編碼等領域中。45.2.2哈夫曼樹的基本概念■路徑：從樹的一個結點到另一個結點的分支（邊）構成這兩個結點之間的路徑。對于哈夫曼樹特指從根結點到某結點的路徑?！雎窂介L度：路徑上的分支數目（邊數）。樹的路徑長度：從樹根到每一結點的路徑長度之和。■權：賦予某個事物的一個量，是對事物的某個（些）屬性的數值化描述。在數據結構中，包括結點權和邊權兩類，它們的具體意義由具體情況決定?！鼋Y點的帶權路徑長度：結點的路徑長度與結點上權的乘積。46.■樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長度（weightedpathlength）之和。記做WPL＝∑wili其中，wi是第i個葉子的權值，li是第i個葉子的路徑長度（i=1,2,…,n）?！龉蚵鼧洌涸O有結點集合K={k1,k2,…,kn}，并以k1,k2,…,kn為葉子結點構造二叉樹，如果它們的權值分別為w1,w2,…,wn，那么稱使得該二叉樹的WPL值最小的二叉樹為哈夫曼樹（最優二叉樹）。47.例如，有4個權值分別為1、6、8、9的結點A、B、C、D，可以構造出以它們為葉子結點的多個二叉樹，如圖6.7。對于這三棵二叉樹，它們的帶權路徑長度如下：(a)WPL=9×2＋8×2＋1×2＋6×2＝48(b)WPL=9×3＋8×3＋1×1＋6×2＝64(c)WPL=9×1＋8×2＋1×3＋6×3＝46

可見二叉樹(c)的WPL值最小，這正是一棵哈夫曼樹。48.918616896981ABCDDACBBACD圖6.7具有不同帶權路徑長度的二叉樹(a)WPL=48(b)WPL=64(c)WPL=4649.由此可見，由相同權值的一組葉子接點所構成的二叉樹有不同的形態和不同的帶權路徑長度WPL。那么，如何找到WPL最小的二叉樹（哈夫曼樹）呢？根據哈夫曼樹的定義，一棵二叉樹要使其WPL值最小，必須使權值越大的葉子接點越靠近根接點，而權值越小的葉子結點越遠離根結點。50.2.3哈夫曼樹的構造算法算法可描述如下：(1)根據給定的n個權值w1,w2,…,wn，構造由n棵二叉樹構成的森林F={T1,T2,…,Tn}，其中每棵二叉樹Ti

都是只含有一個帶權值為wi的根結點。(2)從森林f中選取兩棵權值最小的二叉樹Ti

和Tj，分別作為左右子樹構造一棵新的二叉樹，并置新二叉樹的根結點r的權值為wr=wi+wj

。(3)從森林F中刪去Ti和Tj

，而把新二叉樹r加入到F中。(4)重復步驟2和步驟3，直到F中只含一棵二叉樹為止。這棵二叉樹便是所要建立的哈夫曼樹。51.9816987169158716249158716圖6.8哈夫曼樹的構造過程

52.2.4哈夫曼編碼

哈夫曼樹是哈夫曼編碼的基礎，利用哈夫曼樹可以構造哈夫曼編碼。哈夫曼編碼的基本原理是：對頻繁使用的字符用較短的代碼代替，而對較少使用的字符用較長的代碼代替，這樣就可以使文件中的編碼數減少到最小。因此，哈夫曼編碼是一種非等長的并使文件的編碼總長為最短的編碼方案。53.利用構建哈夫曼樹的方法可以得到文件的哈夫曼編碼。下面給出哈夫曼編碼算法的基本思路：(1)對需要編碼的文件統計出它的字符集{C1,C2,…,Cn}，并統計出各個字符在文件中出現的次數或頻率，如為｛w1,w2,…,wn｝。(2)以C1,C2,…,Cn作為葉子結點，w1,w2,…,wn作為結點的權值，構造一棵哈夫曼樹。(3)規定哈夫曼樹中的左分支代表0，右分支代表1，則從根結點到每個葉子結點所經過的路徑分支組成的0和1的序列便為該葉子結點所對應字符的哈夫曼編碼。54.例如，某文本的字符集及各自的頻率為：A(1),B(9),C(6),D(8)，將它們構造成一棵哈夫曼樹，于是便可得到A、B、C、D的哈夫曼編碼，如圖6.9所示。55.8169249158716圖6.9哈夫曼編碼的生成過程

BDAC100011哈夫曼編碼

A:110B:0C:111D:1056.

在構建編碼的二叉樹時必須將字符結點作為葉子結點，否則會產生具有二義性的編碼。例如，有人為字符集合A(1),B(9),C(6),D(8)建立了如下圖所示的一棵二叉樹，從而得到的編碼是A:01B:010C:001D:10198657.在該方案中，字符A的編碼01是字符B的編碼010的前綴部分，這樣對于代碼串0101001，既是AAC的代碼，也是ABD和BDA的代碼，因此，這樣的編碼不能保證譯碼的唯一性，被稱之為具有二義性的編碼。然而，采用哈夫曼編碼則不會產生二義性問題。因為，在哈夫曼樹中每個字符結點都是葉子結點，它們不可能在根結點到其他字符結點的路徑上，所以一個字符的哈夫曼編碼不可能是另一個字符的哈夫曼編碼的前綴，從而保證了譯碼的非二義性。58.2.5哈夫曼樹類的實現

1.基本思路為了找出一組符號（字符、圖象符號等）的哈夫曼編碼，可以定義一個哈夫曼樹類。哈夫曼樹類的對象可以接受一組符號以及對應的權值，并返回每個符號的哈夫曼編碼。因此，哈夫曼樹類應該提供兩個public操作：MakeHfmTree和GetHfmCode。MakeHfmTree操作接受一組待編碼的符號以及相應的權值，構造一棵哈夫曼樹。GetHfmCode操作根據生成的哈夫曼樹為每個葉子結點生成并返回哈夫曼編碼。59.實現哈夫曼樹類的兩個重要問題是：■如何設計哈夫曼樹結點?■如何構造并保存哈夫曼樹?

下面給出解決上述問題的一種方案。(1)哈夫曼樹結點可包括：符號值、符號的權值、左孩子指針、右孩子指針及父結點指針。60.(2)在哈夫曼樹中，每個待編碼的符號對應的是一個葉子結點，其他結點都是度為2的結點。只要給定了待編碼的符號個數n，由n0=n2+1可知哈夫曼樹的規模為2n-1。鑒于這些特性，可以考慮用一個長度為2n-1的結點數組forest來構造哈夫曼樹。初始時，葉子結點依次存放在forest中的n到2n-1的數組元素中，它們的parent值均為0，表示所有的樹都只有根結點。第一次歸并在n到2n-1的數組元素中查找權值最小和次小的樹，歸并后的樹的根結點存放在數組元素forest[n-1]中，并設置父子關系。第二次歸并后的樹的根結點存放在數組元素forest[n-2]中……。最后一次歸并的結果存放在數組元素forest[1]中。至此，在forest中便生成了一棵哈夫曼樹，數組元素forest[1]是該哈夫曼樹的根結點。61.2.哈夫曼樹類的定義

template<typenameType>structHfmNode{//哈夫曼樹結點的類型Typedata;//符號值intweight;//符號的權值intparent,leftChild,rightChild;//父及左右孩子的下標值};template<typenameType>structHfmCode{//哈夫曼編碼的類型Typedata;//待編碼的符號stringcode;//對應的哈夫曼編碼};62.template<typenameType>classHfmTree{//哈夫曼樹類private:HfmNode*forest;//哈夫曼樹結點數組，用于構造并保存哈夫曼樹intsize;//待編碼的符號個數（葉子結點個數）HfmCode*hfm_code;//哈夫曼編碼數組intMinTree(intpos);//查找森林中的最小樹public:HfmTree(intn){//n為待編碼的符號個數size=n;forest=newHfmNode<Type>[size*2-1];//為森林分配空間hfm_code=newHfmCode<Type>[size];//為編碼數組分配空間}~HfmTree(){delete[]forest;}voidMakeHfmTree(Type*datas,int*w);//構造哈夫曼樹voidGetHfmCode(stringcode[]);//生成并返回哈夫曼編碼}63.3.構造哈夫曼樹的算法實現voidMakeHfmTree(Type*datas,int*w){//datas為待編碼的符號數組，w為權值數組intx,y;//最小樹、次最小樹的下標intk=size*2-1;//初始化森林for(inti=size;i<=k;i++){forest[i].weight=w[i-size+1];forest