第5章樹引言樹形結構是元素之間具有分層關系的結構，它類似于自然界中的樹，應用廣泛，是一類很重要的非線性數據結構。在計算機應用中，常出現嵌套的數據，樹結構提供了對該類數據的自然表示；利用樹結構，可以有效地解決一些算法問題。由于結構特征，樹形結構常采用遞歸方式定義。被稱為遞歸數據結構。有關樹的許多算法是遞歸的。數據結構DATASTRUCTURE南京郵電大學計算機學院內容提要1、樹的基本概念；給出樹的定義，關于樹中的一些術語；2、二叉樹的定義、性質及其規范；3、二叉樹的遍歷等算法的實現；4、樹和森林的表示、存儲和遍歷；5、二叉樹的應用實例——哈夫曼樹和哈夫曼編碼。南京郵電大學計算機學院層次結構的數據在現實自然界中大量存在。國家、省、市、縣和區。書的章節、回目。上級和下級。整體和部分。祖先和后裔。5.1樹的基本概念5.1.1樹的定義課堂提要第5章樹5.1樹的基本概念5.2二叉樹5.3二叉樹的遍歷5.5樹和森林5.7哈夫曼樹和哈夫曼編碼南京郵電大學計算機學院圖5-1西歐語言譜系圖原始印歐語古意大利語日耳曼語西日耳曼語拉丁語西班牙語法語意大利語希臘語北日耳曼語冰島語瑞典語挪威語英語荷蘭語德語古希臘語南京郵電大學計算機學院樹形結構操作系統的目錄結構南京郵電大學計算機學院1.樹的定義定義5.1有根數或樹的定義

樹是包括n（n1）個元素的有限非空集合D，R是D中元素的序偶的集合，R滿足以下特性：（1）有且僅有一個結點r∈D，不存在任何結點v∈D，v≠r，使得<v,r>∈R，稱r為樹的根。（2）除根r以外的所有結點u∈D，都有且僅有一個結點v∈D，v≠u，使得<v,u>∈R。這樣定義的樹也稱有根樹，簡稱樹。樹不為空集合，樹中至少有一個根結點，根結點沒有前驅，其余結點都有唯一的前驅結點。因此樹形成層次結構。南京郵電大學計算機學院2.樹的遞歸定義定義5.2

樹是包括n個結點的有限非空集合T，其中一個特定的結點r稱為根，其余結點（T-{r}）劃分成m（m≥0）個互不相交的子集T1，T2，...Tm，其中，每個子集都是樹，被稱為樹根r的子樹。定義5.2是遞歸的，用子樹來定義樹，也就是說，在樹的定義中引用了樹概念本身，所以，樹被稱為遞歸數據結構。EAFGBCDLJMN南京郵電大學計算機學院結點(node)：樹中的元素。

E、A、F、B、G、C、D、L、J、M、N均為結點。5.1.2基本術語EAFGBCDLJMN路徑(path)：從某個結點沿樹中的邊可到達另一個結點，則稱這兩個結點之間存在一條路徑。E和N之間存在一條路徑。根結點和它的子樹根（如果存在）之間形成一條邊。路徑(path)：從某個結點沿樹中的邊可到達另一個結點，則稱這兩個結點之間存在一條路徑。E和N之間存在一條路徑。EAFGBCDLJMN路徑(path)：從某個結點沿樹中的邊可到達另一個結點，則稱這兩個結點之間存在一條路徑。E和N之間存在一條路徑。南京郵電大學計算機學院雙親(parent)：若一個結點有子樹，那么該結點稱為子樹根的雙親。A、F、B的雙親是E。C、D的雙親是F。孩子(child)：某結點子樹的根是該結點的孩子。E有三個孩子：A、F、B。D有一個孩子：J。兄弟(sibling)：有相同雙親的結點互為兄弟。A、F、B互為兄弟，C和D互為兄弟。結點G和C互為兄弟否？EAFGBCDLJMN南京郵電大學計算機學院后裔(decendent)：一個結點的所有子樹上的任何結點都是該結點的后裔。結點C的后裔為：L、M、N。EAFGBCDLJMN祖先(ancestor)：從根結點到某個結點的路徑上的所有結點都是該結點的祖先。結點L的祖先為：E、F、C。南京郵電大學計算機學院結點的度(degree)：結點擁有的子樹數。結點E的度為3，結點F的度為2，結點A的度為1，結點G的度為0。葉子(leaf)：度為零的結點。B、G、J、M、N均為葉子結點。EAFGBCDLJMN分支結點(branch)：度不為零的結點。E、A、F、C等為分支結點。樹的度：樹中結點的最大的度。該樹的度為3。南京郵電大學計算機學院結點的層次：根結點的層次為1，其余結點的層次等于其雙親結點的層次加1。結點E的層次為1。結點M的層次為5。樹的高度：樹中結點的最大層次。∵樹中結點的最大層次為5。∴樹的高度為5。12345EAFGBCDLJMN南京郵電大學計算機學院AG無序樹：如果樹中結點的各子樹之間的次序是不重要的，可以交換位置。下列是同一棵無序樹：將左邊樹中所有結點的子樹互換次序就是右邊的樹。EAFGBCDLJMNEFBCDLJNM南京郵電大學計算機學院有序樹：如果樹中結點的各棵子樹看成是從左到右有次序的，則稱該樹為有序樹。有序樹的各子樹從左到右為第一棵子樹、第二棵，…如果下列是有序樹，則二者是二棵不同的樹AGEAFGBCDLJMNEFBCDLJNM南京郵電大學計算機學院森林：是樹的集合。0個或多個不相交的樹組成森林。果園或有序森林：有序樹的有序集合。森林與樹只有很小的差別，若將樹中的根去掉，則得到根的子樹組成的森林。BEAGFCDLJMNE若增加一個結點，將森林中各樹的根作為新增結點的孩子，則森林即成為樹。南京郵電大學計算機學院遞歸1.遞歸的定義函數直接（間接）調用自已，稱為函數的遞歸調用。2.簡單實例以下是一個最簡單的遞歸函數。voidfunc(){func();}

修改為：voidfunc(intn){if(n<=0)return;func(n--);}南京郵電大學計算機學院3.遞推關系可以把要解決的問題轉化為一個新問題，而這個新的問題的解決方法仍與原來的解決方法相同，只是所處理對象的規模有規律地遞增或遞減，即要找到對象之間的遞推關系。

方法相同，規模變化4.遞歸的結束條件要有一個明確的結束遞歸的條件，一定要能夠在適當的地方結束遞歸調用，不然可能導致系統崩潰南京郵電大學計算機學院intfunc(intn){if(n==1)return1;returnfunc(n-1)*n;}例如：采用遞歸計算N！正整數N！＝N*(N-1)*(N-2)*…*2*1，

階乘序列可轉換為N！＝N*(N-1)!，而(N-1)!以可轉換為(N-1)!=(N-1)*(N-2)!(N-2)!=(N-2)*(N-3)!，……2!=2*1!1!=1遞推關系：N！＝N*(N-1)!結束條件：N等于1南京郵電大學計算機學院intfunc(intn){if(n==1)return1;returnfunc(n-1)*n;}n=3{if(n==1)…….func(n-1)*n}n=2{if(n==1)…….func(n-1)*n}n=1{if(n==1)return1}1func(n-1)func(n-1)n=2n=12執行過程：南京郵電大學計算機學院設計遞歸算法，求有n個元素的整數數組A中的最大值。

a0a1…ai…

an-2an-101…i…n-2n-1a(n-1)Max(n)Max(n-1)

a0a1…ai…

an-3an-2an-101…i…n-2n-1a(n-2)Max(n-1)Max(n-2)南京郵電大學計算機學院設計遞歸算法，求整數數組A[n]中的最大值。

a0a1…ai…

an-3an-2an-101…i…n-2n-1a(1)Max(2)Max(1)遞推關系：max(n)等于max(n-1)與a[n-1]之間的大者結束條件：n等于1時，Max(1)的值即為a0，所以不再向下遞推南京郵電大學計算機學院intMax(inta[],intn){inttemp;if(n==1)returna[0];else{temp=Max(a,n-1);if(temp<a[n-1])returna[n-1];elsereturntemp;}}遞推關系：max(n)等于max(n-1)與a[n-1]之間的大者結束條件：n等于1時，Max(1)的值即為a0，所以不再向下遞推南京郵電大學計算機學院intMax(inta[],intn){inttemp;if(n==1)returna[0];else{temp=Max(a,n-1);if(temp<a[n-1])returna[n-1];elsereturntemp;}}

8

9

10012n=3{if(n==1)…….Max(a,2)<a[2]}n=2{if(n==1)…….Max(a,1)<a[1]}n=1{if(n==1)returna[0]}89南京郵電大學計算機學院二叉樹是非常重要的樹形數據結構。很多從實際問題中抽象出來的數據是二叉樹形的；以后我們將看到任意樹或森林可方便地轉換成二叉樹，從而為一般樹和森林的存儲和處理提供了有效方法。5.2二叉樹課堂提要第5章樹5.1樹的基本概念5.2二叉樹5.3二叉樹的遍歷5.5樹和森林5.7哈夫曼樹和哈夫曼編碼南京郵電大學計算機學院方法二：改進結構，組織成樹形結構。比較次數不會超過樹高，提高了效率。先看一個二叉樹應用例子。設有序表為（21，25，28，33，36，45），現在要在表中查找元素33。282136253345方法一：順序搜索。效率低，平均比較一半的元素。（21，25，28，33，36，45）比較了4次！比較了3次！3333南京郵電大學計算機學院定義5.3

二叉樹(binarytree)是結點的有限集合，該集合或者為空集，或者是由一個根和兩個互不相交的、稱為該根的左子樹和右子樹的二叉樹組成。上述定義表明二叉樹可以為空集，因此，二叉樹有5種基本形態。5.2.1二叉樹的定義(a)(b)(c)(d)(e)圖5-4二叉樹的五種基本形態南京郵電大學計算機學院樹與二叉樹的區別：⑴樹不能是空樹，即至少有一個根結點。而二叉樹可以是空樹。⑵一般樹的子樹之間是無序的。而二叉樹中結點的子樹要區分左、右子樹，即使只有一棵子樹。⑶樹中每個節點可有0棵或若干子樹。而二叉樹的每個節點最多只能有2棵子樹。EFEF南京郵電大學計算機學院性質5.1二叉樹的第i(i1)層上至多有2i-1個結點。可用歸納法證明之。當i=1時，二叉樹至多只有一個結點，結論成立。設當i=k時結論成立，即二叉樹上至多有2k-1個結點，當i=k+1時，∵每個結點最多只有兩個孩子，∴第k+1層上至多有2*2k–1=2k個結點，性質成立。5.2.2二叉樹的性質南京郵電大學計算機學院性質1、2的圖形解釋性質5.1二叉樹的第i(i1)層上至多有2i-1個結點。南京郵電大學計算機學院性質5.2高度為h的二叉樹上至多有2h–1個結點。當h=0時，二叉樹為空二叉樹。當h>0時，利用性質1，高度為h的二叉樹中結點的總數最多為：南京郵電大學計算機學院性質1、2的圖形解釋南京郵電大學計算機學院性質5.3包含n個元素的二叉樹的高度至少為

log2

(n+1)

根據性質2，高度為h的二叉樹最多有2h–1個結點（性質2），因而n2h–1,則有hlog2(n+1)。由于h是整數，所以h

log2

(n+1)。南京郵電大學計算機學院性質5.4任意一棵二叉樹中，若葉結點的個數為n0，度為2的結點的個數為n2，則必有n0=n2+1。設二叉樹的度為1的結點數為n1，樹中結點總數為n，則n=n0+n1+n2……①（∵二叉樹中只有度為0、1、2三種類型的結點）設分支數為B，n個結點的二叉樹，除了根結點外，每個結點都有一個分支進入，則B=n-1；分支是由度為1或者度為2的射出的，又有B=2n2+n1；則有：n-1=2n2+n1n=2n2+n1+1……②由①②可得到：n0+n1+n2=2n2+n1+1n0+n2=2n2+1 即n2=n0-1。南京郵電大學計算機學院定義5.4高度為h的二叉樹恰好有2h–1個結點時稱為滿二叉樹。01234567891011121314(a)滿二叉樹圖5.6幾種特殊的二叉樹性質5.2高度為h的二叉樹上至多有2h–1個結點。南京郵電大學計算機學院0123456789(b)完全二叉樹圖5.6幾種特殊的二叉樹9定義5.5一棵二叉樹中，只有最下面兩層結點的度可以小于2，并且最下一層的葉結點集中在靠左的若干位置上。這樣的二叉樹稱為完全二叉樹。南京郵電大學計算機學院定義5.6擴充二叉樹也稱2-樹，其中除葉子結點外，其余結點都必須有兩個孩子。532330111213173589南京郵電大學計算機學院完全二叉樹的性質性質5.5具有n個結點的完全二叉樹的高度為log2

(n+1)。證明：根據性質2高度為h-1的完全二叉樹結點個數最多為2h-1-1高度為h的完全二叉樹結點個數最多為2h-1高度為h的完全二叉樹結點個數取值范圍[2h-1,2h)2h-1-1＜n≤2h–1log2(n+1)≤h＜log2(n+1)+1h=log2

(n+1)結論：⑴n個結點的二叉樹中完全二叉樹最矮，高度為log2(n+1)。⑵n個結點的完全二叉樹和二叉判定樹的高度是一樣的2h-1≤n＜2hh-1≤log2n＜h∵h是整數∴h=①①②②性質2高度為h的二叉樹上至多有2h–1個結點。南京郵電大學計算機學院性質5.6假定對一棵有n個結點的完全二叉樹中的結點，按從上到下、從左到右的順序，從0到n-1編號（見圖5.6(c)），設樹中一個結點的序號為i，0i＜n，則有以下關系成立：（1）當i=0時，該結點為二叉樹的根。（2）若i>0，則該結點的雙親的序號為(i-1)/2（3）若2i+1＜n，則該結點的左孩子的序號為2i+1，否則該結點無左孩子。（4）若2i+2＜n，則該結點的右孩子的序號為2i+2，否則該結點無右孩子。0123456789(b)完全二叉樹南京郵電大學計算機學院ADTBinaryTree{Data:二叉樹是結點的有限集合，該集合或者為空集，或者是由一個根和兩個互不相交的稱為該根的左子樹和右子樹的二叉樹組成。

Operations:Create()：創建一棵空二叉樹。Destroy():撤銷一棵二叉樹。IsEmpty()：若二叉樹空，則返回true，否則返回false。Clear():移去所有結點，成為空二叉樹。Root(x)：取x為根結點；若操作成功，則返回true，否則返回falseMakeTree(x,left，right)：創建一棵二叉樹，x為根結點，left為左子樹，right為右子樹。BreakTree(x,left,right)：拆分二叉樹為三部分，x為根的值，left和right分別為原樹的左右子樹PreOrder：使用函數Visit訪問結點，先序遍歷二叉樹。InOrder：使用函數Visit訪問結點，中序遍歷二叉樹。PostOrder：使用函數Visit訪問結點，后序遍歷二叉樹。}

5.2.3二叉樹ADT南京郵電大學計算機學院1.完全二叉樹的順序表示完全二叉樹中的結點可以按層次順序存儲在一片連續的存儲單元中。根結點保存在編號為0的位置上。注意：一般的二叉樹不適合用這種存儲結構。01234567890123456789圖6.5圖6.4(b)完全二叉樹的順序表示0123456789圖6.4(b)完全二叉樹5.2.4二叉樹的存儲表示南京郵電大學計算機學院element2.二叉樹的鏈接表示ABCDEFAB^C^D^^E^^F^(a)二叉樹 (b)二叉樹的鏈接表示圖6-6二叉樹的鏈接表示lChildrChild二叉樹的二叉鏈表結構有利于從雙親到孩子方向的訪問。采取從根開始，遍歷整個二叉樹。root南京郵電大學計算機學院如果應用程序需要經常執行從孩子到雙親訪問，可在二叉鏈表結點中增加一個parent域，令它指向該結點的雙親結點。這就實現了從孩子到雙親，以及從雙親到孩子的雙向鏈接結構，形成多重鏈表。南京郵電大學計算機學院template<classT>structBTNode//樹結點{BTNode(){lChild=rChild=NULL;}BTNode(constT&x){element=x;lChild=rChild=NULL;}BTNode(constT&x,BTNode<T>*l,BTNode<T>*r){element=x;lChild=l;rChild=r;}Telement;BTNode<T>*lChild,*rChild;};5.2.5二叉樹類南京郵電大學計算機學院template<classT>classBinaryTree{public:BinaryTree(){root=NULL;}

~BinaryTree(){Clear();}boolIsEmpty()const;voidClear();boolRoot(T&x)const;voidMakeTree(constT&e,BinaryTree<T>&left,BinaryTree<T>&right);voidBreakTree(T&e,BinaryTree<T>&left,BinaryTree<T>&right);voidPreOrder(void(*Visit)(T&x));//公有函數，用戶接口voidInOrder(void(*Visit)(T&x));voidPostOrder(void(*Visit)(T&x));

protected:BTNode<T>*

;//指向根結點

private:intSize(BTNode<T>*t);voidClear(BTNode<T>*t);voidPreOrder(void(*Visit)(T&x),BTNode<T>*t);//私有函數，實現遍歷voidInOrder(void(*Visit)(T&x),BTNode<T>*t);voidPostOrder(void(*Visit)(T&x),BTNode<T>*t);};程序5.2二叉樹類root南京郵電大學計算機學院本小節中，我們主要實現MakeTree、BreakTree和Root運算，而將二叉樹遍歷算法留待下一小節專門討論。Clear()函數釋放二叉鏈表中的所有結點，它需要通過遍歷二叉樹來實現。5.2.6實現二叉樹基本運算南京郵電大學計算機學院程序5.3部分二叉樹運算template<classT>boolBinaryTree<T>::Root(T&x)const//取根結點的數據值{if(root){x=root->element;returntrue;}elsereturnfalse;}ABCDEFroot南京郵電大學計算機學院template<classT>voidBinaryTree<T>::MakeTree(constT&x, BinaryTree<T>&left,BinaryTree<T>&right){if(root||&left==&right)return;root=newBTNode<T>(x,left.root,right.root);left.root=right.root=NULL;}DCEFBTNode(constT&x,BTNode<T>*l,BTNode<T>*r){element=x;lChild=l;rChild=r;}XleftrightnewBTNode<T>(x,left.root,right.root);函數功能：以x為根，left,right為左右子樹構建一棵新二叉樹南京郵電大學計算機學院template<classT>voidBinaryTree<T>::BreakTree(T&x, BinaryTree<T>&left,BinaryTree<T>&right){if(!root||&left==&root||left.root||right.root)return;x=root->element;left.root=root->lChild;right.root=root->rChild;deleteroot;root=NULL;}DCEFAleft.root→←right.rootroot=∧root函數功能：將二叉樹左右子樹拆分成二棵新的二叉樹，根結點刪除南京郵電大學計算機學院intmain(void){BinaryTree<char>a,b,x,y,z;chare;y.MakeTree('E',a,b);z.MakeTree('F',a,b);x.MakeTree('C',y,z);y.MakeTree('D',a,b);z.MakeTree('B',y,x);z.BreakTree(e,y,x);return0;}程序5.4main函數——一個測試程序abxyzEyCxFzDyBz南京郵電大學計算機學院ABDCEF5.3二叉樹的遍歷遍歷（traverse）一個有限結點的集合，意味著對該集合中的每個結點訪問且僅訪問一次。二叉樹遍歷算法:

(I)先左后右：VLR，LVR，LRV(II)先右后左：VRL，RVL，RLV-逆課堂提要第5章樹5.1樹的基本概念5.2二叉樹5.3二叉樹的遍歷5.5樹和森林5.7哈夫曼樹和哈夫曼編碼南京郵電大學計算機學院⑴先序遍歷（VLR）若二叉樹為空，則空操作；否則訪問根結點；

先序遍歷左子樹；

先序遍歷右子樹。ABDCEF5.3.1二叉樹遍歷算法先序遍歷序列：ABDCEF

南京郵電大學計算機學院先序遍歷序列：ABDGHECF

t→t→t→t→t→t→t=∧t=∧t=∧t=∧t→t→t=∧t=∧t=∧ABCDEFGH任意一個先序遍歷序列中，根結點的位置在哪里？若二叉樹為空，則空操作；否則訪問根結點；

先序遍歷左子樹；

先序遍歷右子樹。南京郵電大學計算機學院⑵中序遍歷（LVR）若二叉樹為空，則空操作；否則中序遍歷左子樹；訪問根結點；中序遍歷右子樹。

ABDCEF中序遍歷序列：BDAECF

南京郵電大學計算機學院中序遍歷ABCDEFGHIJK南京郵電大學計算機學院⑶后序遍歷（LRV）若二叉樹為空，則空操作；

否則

后序遍歷左子樹；

后序遍歷右子樹；

訪問根結點。ABDCEF后序遍歷序列：DBEFCA

南京郵電大學計算機學院后序遍歷ABCDEFGHIJK南京郵電大學計算機學院層次遍歷ABCDEFGHIJK南京郵電大學計算機學院對于遍歷運算，設計了一個面向用戶的公有成員函數和一個具體實現遍歷操作的遞歸私有成員函數，兩者共同完成遍歷運算的功能。公有成員函數：非遞歸函數，作為與用戶的接口。它調用私有的遞歸函數。私有成員函數：遞歸函數，具體實現遍歷操作。被公有成員函數調用。5.3.2二叉樹遍歷的遞歸算法南京郵電大學計算機學院函數指針格式：函數返回類型(*函數指針名)(參數1，參數2…)#include<iostream.h>intmax(intx,inty){returnx>y?x:y;}intmin(intx,inty){returnx<y?x:y;}intadd(intx,inty){returnx+y;}voidprocess(intx,inty,int(*fun)(int,int)){intresult;result=fun(x,y);cout<<result<<endl;}intmain(void){intx=1,y=2;process(1,2,min);process(1,2,max);process(1,2,add);return0;}程序運行結果：123指向函數的指針保存一個函數的入口地址。函數返回類型(*函數指針名)(參數1,參數2)int(*fun)(int,int)南京郵電大學計算機學院程序5.5訪問元素函數template<classT>voidVisit(T&x){cout<<x<<"\t";}程序5.6先序遍歷template<classT>voidBinaryTree<T>::PreOrder(void(*Visit)(T&x))//非遞歸函數，作為與用戶的接口，調用遞歸函數{PreOrder(Visit,root);}template<classT>voidBinaryTree<T>::PreOrder(void(*Visit)(T&x),BTNode<T>*t){if(t)//遞歸函數，實現遍歷{Visit(t->element);PreOrder(Visit,t->lChild);PreOrder(Visit,t->rChild);}}注：1.函數名相同，但參數不同，不是同一個函數。2.使用函數指針(*Visit)(T&x)，只是為了增加程序的靈活性

南京郵電大學計算機學院template<classT>voidBinaryTree<T>::PreOrder(BTNode<T>*t){if(t){cout<<t->element;PreOrder(t->lChild);PreOrder(t->rChild);}}template<classT>voidBinaryTree<T>::PreOrder(void(*Visit)(T&x),BTNode<T>*t){if(t)//遞歸函數，實現遍歷{Visit(t->element);PreOrder(Visit,t->lChild);PreOrder(Visit,t->rChild);}}除去函數指針，以上遞歸的PreOrder函數可以簡化為：南京郵電大學計算機學院CEFt->c{if(t){cout<<c

PreOrder(t->lChild);PreOrder(t->rChild);}}t->E{if(t){cout<<E

PreOrder(t->lChild);PreOrder(t->rChild);}}t->^{if(t){cout…PreOrder(t->lChild);PreOrder(t->rChild);}}t->^{if(t){cout…PreOrder(t->lChild);PreOrder(t->rChild);}}t->F{if(t){cout<<F

PreOrder(t->lChild);PreOrder(t->rChild);}}t->^{if(t){cout…PreOrder(t->lChild);PreOrder(t->rChild);}}南京郵電大學計算機學院補充：中序遍歷template<classT>voidBinaryTree<T>::InOrder(void(*Visit)(T&x)){InOrder(Visit,root);}template<classT>voidBinaryTree<T>::InOrder(void(*Visit)(T&x),BTNode<T>*t){if(t){InOrder(Visit,t->lChild);

Visit(t->element);InOrder(Visit,t->rChild);}}南京郵電大學計算機學院補充：后序遍歷template<classT>voidBinaryTree<T>::PostOrder(void(*Visit)(T&x)){PostOrder(Visit,root);}template<classT>voidBinaryTree<T>::PostOrder(void(*Visit)(T&x),BTNode<T>*t){if(t){PostOrder(Visit,t->lChild);PostOrder(Visit,t->rChild);

Visit(t->element);}}南京郵電大學計算機學院顯然，二叉樹遍歷算法基本操作是訪問結點，不論按何種次序遍歷，對含有n個結點的二叉樹，其時間復雜度均為O(n)。南京郵電大學計算機學院關于三種遍歷算法：1.給定一棵二叉樹，能寫出它的三種遍歷序列。2.給出二叉樹的先序遍歷序列和中序遍歷序列可以唯一確定一棵二叉樹。3.給出二叉樹的后序遍歷序列和中序遍歷序列可以唯一確定一棵二叉樹。4.當n>1時，給出二叉樹的先序遍歷序列和后序遍歷序列不可以唯一確定一棵二叉樹。例如：先序序列：AB，后序序列：BA注意n>1的條件！例如：先序序列：A，后序序列：AAABAB南京郵電大學計算機學院例已知結點的先序序列和中序序列分別為：前序序列ABCDEFG中序序列CBEDAFG則可按上述分解求得整棵二叉樹。其構造過程如下圖所示。首先由前序序列得知二叉樹的根為A，則其左子樹的中序序列為（CBED），又右子樹的中序序列為（FG）。反過來得知其左子樹的前序序列必為（BCDE），右子樹的前序序列為（FG）。類似地，可由左子樹的前序序列和中序序列構造A的左子樹，由右子樹的前序序列和中序序列構造得A的右子樹。南京郵電大學計算機學院1.計算二叉樹的結點數程序5.7求二叉樹的結點數template<classT>intBinaryTree<T>::Size(){returnSize(root);}template<classT>intBinaryTree<T>::Size(BTNode<T>*t){if(!t)return0;returnSize(t->lChild)+Size(t->rChild)+1;}利用二叉樹遍歷思想可以解決許多二叉樹的應用問題。ABDCEF5.3.3二叉樹遍歷的應用實例南京郵電大學計算機學院2.二叉樹復制程序5.8二叉樹復制template<classT>BTNode<T>*BinaryTree<T>::Copy(BTNode<T>*t){if(!root)returnNULL;BTNode<T>*q=newBTNode<T>(t->element);q->lChild=Copy(t->lChild);q->rChild=Copy(t->rChild);returnq;}ABDCEFtABDCEFq==>南京郵電大學計算機學院3.補充：Clear函數template<classT>voidBinaryTree<T>::Clear(BTNode<T>*t){if(t){Clear(t->lChild);Clear(t->rChild);cout<<"delete"<<t->element<<"..."<<endl;deletet;}}南京郵電大學計算機學院二叉樹在很多領域都有著廣泛的應用——編譯原理中的表達式樹專家系統中的決策樹猜謎游戲的決策樹南京郵電大學計算機學院先序遍歷前綴表達式中序遍歷中綴表達式后序遍歷后綴表達式編譯原理中的表達式樹編譯原理中還用了語法樹(d)a*(b+c*d)/e/*+eb*ab*(c)a*(b+c)*aceb(b)a*b+c+*bca(a)a/b/ab南京郵電大學計算機學院5.4二叉樹遍歷的非遞歸算法南京郵電大學計算機學院

前兩幾節中，我們已介紹了樹和森林的定義和概念，并對二叉樹作了詳細介紹，現在再回過頭來討論森林和二叉樹的轉換、樹或森林的存儲表示及其遍歷算法。5.5樹和森林課堂提要第5章樹5.1樹的基本概念5.2二叉樹5.3二叉樹的遍歷5.5樹和森林5.7哈夫曼樹和哈夫曼編碼南京郵電大學計算機學院為什么要將森林轉換為二叉樹

如果樹和森林能夠用二叉樹表示，則前面對二叉樹的討論成果可應用于一般樹和森林。注意：樹和二叉樹的區別—二叉樹有左右孩子之分，而樹沒有左右孩子之分。5.5.1森林與二叉樹的轉換南京郵電大學計算機學院2.森林(Forest)轉換成二叉樹(BTree)可以將任何森林唯一地表示成一棵二叉樹。方法如下：(1)若F為空，則B為空二叉樹(2)若F非空，則B的根是F中第一棵子樹T1的根R1，B的左子樹是R1的子樹森林（T11，T12，…，T1m），B的右子樹是森林（T2，…，Tn）所對應的二叉樹最后所形成的二叉樹就是森林所對應的二叉樹。南京郵電大學計算機學院1.樹(Tree)轉換為二叉樹(BTree)算法樹可以唯一地表示成一棵二叉樹：⑴兄弟手拉手----將樹中的兄弟用線連接；⑵斷絕非長子之間的父子關系----對各結點，保留最左孩子的連線，去掉其余孩子的連線；⑶最后抖一抖----調整為習慣的二叉樹形(水平右斜，垂直左斜)。GDEFHJDEHFJG(a)樹(b)對應的二叉樹5.5.1森林與二叉樹的轉換南京郵電大學計算機學院DEFGHJABCKDEFGHJABCKGACKGA==>CK==>再看一例⑴兄弟手拉手⑵斷絕非長子之間的父子關系⑶最后抖一抖左孩子右兄弟樹轉換為二叉樹南京郵電大學計算機學院注意：⑴左孩子右兄弟。(樹→二叉樹)

二叉樹中有兩個結點X和Y，且X是Y的雙親

⑵樹的根結點沒有兄弟，所以樹對應的二叉樹根結點沒有右子樹二叉樹中樹中Y是X左孩子Y是X孩子Y是X右孩子Y是X兄弟南京郵電大學計算機學院森林轉換成二叉樹的具體做法：１.將森林中各樹的根用線連起來，２.在樹中，凡是兄弟用線連起來--兄弟手拉手；３.去掉從雙親到除了第一個孩子以外的孩子的連線，只保留雙親到第一個孩子的連線--斷絕非長子之間的父子關系；4.使之稍微傾斜成習慣的二叉樹形--最后抖一抖。其實，這里討論的森林是指有序森林，也可將一般的森林視為有序森林來對待。

5.5.1森林與二叉樹的轉換南京郵電大學計算機學院ABCFFDEGHJABCFFDEGHJABCFFDEGHJ森林轉換為二叉樹南京郵電大學計算機學院3.二叉樹轉換成森林(B→F)左孩子右兄弟ABCKDEFGHJADEHFJGBCK左孩子仍是孩子，右孩子變為兄弟××××南京郵電大學計算機學院一棵二叉樹B轉換成的森林中有多少棵樹？一棵二叉樹轉化成的森林中所具有的樹的數目，等于二叉樹從根結點開始沿右鏈到第一個沒有右孩子的結點所經過的結點數目。ABECDFGHIJ經過3個結點，故森林中3棵樹南京郵電大學計算機學院ABCDEFGHIJABCDEFGHIJ南京郵電大學計算機學院1.多重鏈表表示法其中m是樹的度。每個結點的指針域個數均為m，故又稱為等長的多重鏈表。優點：處理簡單。 缺點：空指針域多，有浪費。設樹中有n個結點，總共有n*m個指針域，其中，只有n-1個非空指針域，故空指針域個數為：n*m-(n-1)=n(m-1)+15.5.2樹和森林的存儲表示elementchild1child2……childm南京郵電大學計算機學院2.孩子兄弟表示法孩子兄弟(左子/右兄弟)表示法實質上就是樹所對應的二叉樹的二叉鏈表表示法。其每個結點為：leftChildelementrightSiblingDEFGHJDEFGHJ∧J∧∧G∧F

∧H∧E

D∧南京郵電大學計算機學院3.雙親表示法每個結點有兩個域：element和parent。parent域為指向該結點的雙親結點的下標。可以對樹中結點按自上而下、自左向右(按層次)的次序順序存儲起來。思考：如何查找結點的雙親和孩子？012345DEFGHJ-100012elementparent順序存儲的雙親表示法DEFGHJ雙親表示法南京郵電大學計算機學院4.三重鏈表表示法優點：可以很方便地得到節點的雙親和孩子信息。leftChildelementrightSiblingparentDEFGHJ∧J∧∧G

∧F

∧

H

∧

D

∧∧

E南京郵電大學計算機學院5.帶右鏈的先序表示法數據元素有三個數據項，element,lTag,sibling。

1.sibling指向結點的兄弟

2.lTag為0表示有孩子，孩子存于相鄰單元lTag為1表示無孩子3.數據元素按對應二叉樹的先序遍歷的順序存儲結點。南京郵電大學計算機學院南京郵電大學計算機學院

1．按深度方向遍歷對森林的深度遍歷與二叉樹類似，根據樹的遞歸定義，可以有兩種遍歷次序：先序遍歷和中序遍歷。森林(F)對應二叉樹(B)先序遍歷等價于先序遍歷中序遍歷等價于中序遍歷5.5.3樹和森林的遍歷南京郵電大學計算機學院

對上圖（a)的森林的先序遍歷的結果是：ABCKDEHFJG它等同于對(b)的二叉樹的先序遍歷。⑴先序遍歷

若森林為空，則遍歷結束。否則

a)訪問第一棵樹的根；

b)按先序遍歷第一棵樹的根結點的子樹組成的森林；

c)按先序遍歷其余樹組成的森林。南京郵電大學計算機學院⑵中序遍歷若森林為空，則遍歷結束否則a)按中序遍歷第一棵樹的根結點的子樹組成的森林；b)訪問第一棵樹的根；c)按中序遍歷其余樹組成的森林。南京郵電大學計算機學院2．按寬度方向遍歷首先訪問處于第一層的結點，然后訪問處于第二層的結點，再訪問第三層，…，等，最后訪問最下層的結點。對上圖的森林按寬度方向的遍歷結果是：ADBCEFGKHJ南京郵電大學計算機學院5.6堆和優先權隊列

堆是一種很有用的數據結構，它可以用于高效地實現優先權隊列。

優先權隊列中的元素，按其優先級的高低而不是按元素進入隊列的次序，來確定出隊列的次序。南京郵電大學計算機學院5.6.1堆

一個大小為n的堆是一棵包含n個結點的完全二叉樹，該樹中每個結點的關鍵字值大于等于其雙親結點的關鍵字值。完全二叉樹的根稱為堆頂。它的關鍵字值是整棵樹上最小的。這樣定義的堆稱為最小堆。也可構建最大堆。012345堆底堆頂南京郵電大學計算機學院最小堆的特點：堆頂元素是整個堆的最小元素南京郵電大學計算機學院（2）最小堆的另一定義當完全二叉樹以順序方式存儲時，實際上得到的是結點序列，所以最小堆又可以定義為：堆是n個元素的序列（k0,k1,…,kn-1），當且僅當滿足kik2i+1且kik2i+2,(i=0,1,2,…,(n-2)/2)時稱為最小堆。例１：判斷序列（23，53，34，65，83，74）是最小堆嗎

南京郵電大學計算機學院例２：判斷序列（23，98，34，65，83，74）是最小堆嗎？

98南京郵電大學計算機學院如何將給定的任意序列調整成最小堆？1.將序列寫成堆（完全二叉樹）的形式2.將堆調整為最小堆。整個調整過程：從下標（n-2）/2處的元素開始，調整（n-2）/2到0的每個元素。在每個元素調整的過程中，要逐個判斷每個元素是否滿足最小堆的條件，（即當前元素的值要小于等于孩子），若不滿足則此元素向下調整，即此元素要與左右孩子中的小者交換，交換后再與它的左右孩子中的小者比較，若不滿足條件則再交換，直到不再需要調整。南京郵電大學計算機學院例１：一個元素92向下調整的過程南京郵電大學計算機學院例2:將序列(36,91,24,12,47,30,52,85）調整為最小堆

2６４３１０７５從（n-2）/2處的元素開始，調整（n-2）/2到0的每個元素。南京郵電大學計算機學院1南京郵電大學計算機學院０南京郵電大學計算機學院template<classT>voidAdjustDown(Theap[],intr,intj){//對下標為r的元素調整，使其滿足最小堆的條件intchild=2*r+1;//child是r的左孩子Ttemp=heap[r];while(child<=j){if((child<j)&&(heap[child]>heap[child+1]))child++;//child指向左右孩子中的小者if(temp<=heap[child])break;heap[(child-1)/2]=heap[child];child=2*child+1;}heap[(child-1)/2]=temp;}程序中包含temp<=heap[child]的元素比較要求元素類型Ｔ已實現從元素類型Ｔ到可比較類型關鍵字的轉換，重載類型轉換符可實現這種轉換child//孩子上移到雙親的位置childr南京郵電大學計算機學院template<classT>voidAdjustDown(Theap[],intr,intj){//對下標為r的元素調整，使其滿足最小堆的條件intchild=2*r+1;//child是r的左孩子Ttemp=heap[r];while(child<=j){if((child<j)&&(heap[child]>heap[child+1]))child++;//child指向左右孩子中的小者if(temp<=heap[child])break;heap[(child-1)/2]=heap[child];child=2*child+1;}heap[(child-1)/2]=temp;}程序中包含temp<=heap[child]的元素比較要求元素類型Ｔ已實現從元素類型Ｔ到可比較類型關鍵字的轉換，重載類型轉換符可實現這種轉換child//孩子上移到雙親的位置childr南京郵電大學計算機學院template<classT>voidCreateHeap(Theap[],intn){for(inti=(n-2)/2;i>-1;i--)AdjustDown(heap,i,n-1)；}建堆的時間為O(nlog2n)。更深入分析可知，建堆時間復雜度為O(n)。

r0123456789此例從下標（n-2）/2開始調整此函數功能是建立最小堆，它通過從第（n-2）/2位置開始，直到第一個元素，重復調用AdjustDown函數實現之。南京郵電大學計算機學院5.6.2優先權隊列ADT

1．優先權隊列優先權隊列不同于先進先出（FIFO）隊列，優先權隊列中的元素，按其優先級的高低而不是按元素進入隊列的次序，來確定出隊列的次序。最小值為最高優先權。優先級的最高的元素放在隊首，最先出隊。2．堆是實現優先權隊列的有效的數據結構。

南京郵電大學計算機學院5.6.2優先權隊列ADTADTPrioQueue{數據：n0個元素的最小堆。運算：Create()：建立一個空隊列。Destroy()：撤消一個隊列。IsEmpty()：若隊列空，則返回true；否則返回false。IsFull()：若隊列滿，則返回true；否則返回falseAppend(x):元素值為x的新元素入隊列。

Serve(x):在x中返回具有最高優先權的元素值,并從優先權隊列中刪除該元素。}

南京郵電大學計算機學院5.6.3優先權隊列類template<classT>classPrioQueue{public: PrioQueue(intmSize=20); ~PrioQueue(){delete[]q;}; boolIsEmpty()const{returnn==0;} boolIsFull()const{returnn==maxSize;} voidAppend(constT&x); voidServe(T&x);private: voidAdjustDown(intr,intj); voidAdjustUp(intj);

T*q;

intn,maxSize;};南京郵電大學計算機學院優先權隊列的構造函數和析構函數template<classT>PriorityQueue<T>::PriorityQueue(intmQSize){maxSize=mSize;n=0;q=newT[maxSize];}~PriorityQueue(){delete[]q;};南京郵電大學計算機學院

優先權隊列中插入一個新元素的算法步驟：

1.首先將新元素插入到優先權隊列的最后

2.插入元素后，此隊列應保持優先權隊列的特點，所以，當新元素不滿足條件時，須進行調整，調整過程是由下向上，與雙親結點比較，若雙親結點大則新元素上浮，雙親結點下沉。

注：這一過程中與５.６.１節堆中的AdjustDown相反的比較路徑

南京郵電大學計算機學院例１：向優先權隊列中插入一個新元素２４南京郵電大學計算機學院AdjustUp函數AdjustUp(intj)設數組中0到j-1，這j個位置上的元素已滿足kik2i+1且kik2i+2,(i=0，1,2,…,（n-2）/2)條件，運行AdjustUp(intj)將使得增加一個元素q[j],這0-j個元素也滿足堆的特性。南京郵電大學計算機學院AdjustUp函數template<classT>voidPriorityQueue<T>::AdjustUp(intj){//將新元素q[j]向上調整inti=j;Ttemp=q[i];while(i>0&&temp<q[(i-1)/2]){ q[i]=q[(i-1)/2];//雙親下移 i=(i-1)/2;//i上移}q[i]=temp;}iii南京郵電大學計算機學院Append和Serve函數

template<classT>voidPriorityQueue<T>::Append(constT&x)//插入新元素到優先權隊列中{if(IsFull()){cerr<<"OverFlow"<<endl;exit(1);}q[n++]=x;AdjustUp(n-1);}0１３５４２南京郵電大學計算機學院從空隊列開始，依此向隊列中插入元素的過程南京郵電大學計算機學院

設從空隊列開始，依此向隊列中插入元素：71，74，2，72，54，93，52，28，則每次插入后隊列的狀態如下表南京郵電大學計算機學院template<classT>voidPriorityQueue<T>::Serve(T&x){if(IsEmpty()){cerr<<"UnderFlow"<<endl;exit(1);}x=q[0];q[0]=q[--n];

AdjustDown(0,n-1);}0１３５４２66５４３２0１7南京郵電大學計算機學院Append和Serve函數的時間

容易分析優先權隊列的插入和刪除運算的時間復雜度。由于具有n個結點的完全二叉樹的高度為

log2

(n+1)，所以AdjustDown和AdjustUp兩個算法中，比較和移動元素的次數均不會超過該高度。Append和Serve運算分別用一常數階調用上述兩個運算，所以它們的時間復雜度為O(log2n)。南京郵電大學計算機學院

本節將討論：

樹的路徑長度哈夫曼樹和哈夫曼算法5.7哈夫曼樹和哈夫曼編碼課堂提要第5章樹5.1樹的基本概念5.2二叉樹5.3二叉樹的遍歷5.5樹和森林5.7哈夫曼樹和哈夫曼編碼南京郵電大學計算機學院定義5.7從根到樹中任意結點的路徑長度是指從根結點到該結點的路徑上所包括的邊的數目。

5.7.1樹的路徑長度路徑(path)：從某個結點沿樹中的邊可到達另一個結點，則稱這兩個結點之間存在一條路徑。E和N之間存在一條路徑。EAFGBCDLJMNEAFGBCDLJMN南京郵電大學計算機學院定義5.8如果葉子結點是帶權的，則葉子結點的加權路徑長度是從根到該葉子的路徑長度與葉子的權的乘積。樹的帶權路徑長度為樹中所有葉子結點的加權路徑長度之和，記作其中，m是葉子結點的個數，wk是第k個葉子結點的權，lk是該葉子結點的路徑長度。南京郵電大學計算機學院(1)WPL=2*2+1*3+2*3+6*1=19(2)WPL=2*2+6*3+2*3+1*1=29南京郵電大學計算機學院一般地，權越大的葉子離根越近，則二叉樹的加權路徑長度越小。哈夫曼給出了求具有最小加權路徑長度二叉樹的算法，稱為哈夫曼算法。用哈夫曼算法構造的二叉樹稱為哈夫曼樹。5.7.2哈夫曼樹和哈夫曼算法南京郵電大學計算機學院哈夫曼算法可以描述如下：⑴用給定的一組權值{w1,w2,…,wn}生成一個森林F={T1，T2，…，Tn},其中每棵二叉樹Ti只有一個權值為wi的根結點，其左、右子樹均為空。⑵從F中選擇兩棵根結點權值最小的樹作為新樹根的左、右子樹，新樹根的權值是左、右子樹根結點的權值之和。(約定左子樹根權值小)⑶從F中刪除這兩棵樹，另將新二叉樹加入F中。⑷重復⑵和⑶，直到F中只包含一棵樹為止。此樹即為哈夫曼樹。（重復執行幾次？）南京郵電大學計算機學院構造哈夫曼樹的過程(約定左小右大)重復執行幾次？南京郵電大學計算機學院⑵W={3，5，9，11，12，13}南京郵電大學計算機學院構造哈夫曼樹的步驟：

1.準備工作：首先構造n棵哈夫曼樹對象，每棵樹只有一個權值為w[i]的根結點，且該對象的weight為w[i]，將它們逐一加入優先權隊列。２.構建哈夫曼樹：從優先權隊列中取出兩棵根結點值最小和次最小的哈夫曼樹x和y。以它們根的權值之和為根的權值，x和y為左、右子樹構造一棵新哈夫曼樹，并將新樹對象進優先權隊列。重復執行n-1次，此時，隊列中只剩下合并完成的哈夫曼樹。３.從隊列中取出構造完畢的哈夫曼樹，函數返回該哈夫曼樹。⑵W={3，5，9，11，12，13}南京郵電大學計算機學院5.7.3

哈夫曼樹類template<classT>classHfmTree:publicBinaryTree<T>{public:

operatorT()const{returnweight;}//重載類型轉換運算符，為了方便優先權隊列中，對象間的比較 TgetW(){returnweight;} voidputW(constT&x){weight=x;}SetNull(){root=NULL;}private:

Tweight;};南京郵電大學計算機學院5.7.4

構造哈夫曼樹HfmTree<T>CreateHfmTree(Tw[],intn)設數組w[]中保存n個元素類型為T的權值，函數返回一棵構造成功的哈夫曼樹。南京郵電大學計算機學院template<classT>HfmTree<T>CreateHfmTree(Tw[],intn){PrioQueue<HfmTree<T>>pq(n);

//空優先權隊列HfmTree<T>x,y,z,zero;//空哈夫曼樹for(inti=0;i<n;i++){//初始化z.MakeTree(w[i],x,y);//構造只有一個結點的哈夫曼樹對象

z.putW(w[i]);//將W[i]的值寫入wight域pq.Append(z);//將哈夫曼樹對象加入優先權隊列z.SetNull();//將z置空 }for(i=1;i<n;i++){ pq.Serve(x);//取出根結點權值最小的哈夫曼樹對象pq.Serve(y);/取出根結點權值次小的哈夫曼樹對象

z.MakeTree(x.getW()+y.getW(),x,y); z.putW(x.getW()+y.getW()); pq.Append(z); z.SetNull();}pq.Serve(z);returnz;}

W={3，5，9，11，12，13}南京郵電大學計算機學院1.等長編碼

A:00,B:01,C:10,D:11.

電文：ABACABDA.編碼：0001001000011100

譯碼：兩位一個字符。ASCII編碼是等長編碼。2.不等長編碼

A:0,B:01,C:10,D:101.

電文：ABACABDA.編碼：0010100011010

譯碼：產生二義性。原因：一個字符的編碼是另一個字符編碼的前綴。前綴編碼：一個字符的編碼不是另一個字符編碼的前綴。5.7.5哈夫曼編碼南京郵電大學計算機學院可以利用哈夫曼樹得到前綴編碼，即哈夫曼編碼。

方法如下：1.用權值構造哈夫曼樹2.約定左分支為0，右分支為1。3.哈夫曼編碼電文：

ABF編碼：1100110110

即左0右1南京郵電大學計算機學院5.8并查集與等價關系

首