全國高等教育自學考試指定教材

計算機及應用專業（本科段）數據結構與算法第五章樹與二叉樹學習目標理解樹及二叉樹的基本概念，掌握二叉樹的基本性質掌握樹及二叉樹的存儲方式能夠實現樹及二叉樹的基本操作及遍歷算法掌握堆的概念及基本操作的實現。理解優先隊列的概念理解遞歸的概念，能夠實現遞歸程序掌握樹、森林與二叉樹之間的相互轉換掌握哈夫曼樹及哈夫曼編碼的概念，能夠構造哈夫曼樹并設計哈夫曼編碼本章主要內容樹的基本概念12二叉樹的操作3二叉樹樹和森林5哈夫曼樹及哈夫曼編碼6堆及優先隊列4第一節樹的基本概念樹是一種層次結構，是一種非線性結構日常生活中，經常會遇到具有層次關系的示例家族中部分成員的輩份關系樹的定義定義5-1一棵樹（tree）T是由一個或一個以上的結點組成的有限集，其中有一個特定的結點R稱為樹T的根結點。在集合中除根結點R外，其余的結點可劃分為k(k≥0)個不相交的子集T1,T2,…,Tk，其中每個子集都是樹，并且其相應的根結點R1,R2,…,Rk是R的孩子結點，R稱為Ri(1≤i≤k)的雙親結點，Ri(1≤i≤k)互稱為兄弟結點。子集Ti(1≤i≤k)稱為根R的子樹（subtree）樹的結點集合至少包含一個結點只含有一個結點的樹是只有根結點的樹，也就是單結點樹對于多結點的樹，必須有一個結點是根結點之間通過邊來連接，邊也稱為分支。含n個結點的樹有且僅有n-1條邊，這是樹的重要特性之一根結點的各子樹之間不會有重疊樹是一種層次結構，也是遞歸形式的含有A,B,C,D,E,F,G,H,I,J共10個結點的樹TA為根結點，{B,E,F}，{C,G}和{D,H,I,J}構成根結點A的三棵子樹，B,C,D分別是這三棵子樹的根樹中每個結點擁有的子樹的個數稱為結點的度結點的度即為其子結點的個數樹中結點的度的最大值稱為樹的度度為0的結點稱為葉結點，或終端結點度不為0的結點稱為分支結點如果樹中每個結點的孩子結點之間規定了次序，則樹稱為有序樹具有同一雙親結點的結點是兄弟結點從任一結點到根結點之間所經過的所有結點稱為該結點的祖先結點以任一結點為根的子樹中的所有結點稱為該結點的后代將線性結構中的前驅和后繼概念引申至樹中，將某結點的雙親結點看作是它的前驅，它的孩子結點看作是它的后繼除根結點外，每個結點均只有一個前驅結點根的前驅結點個數為0，除葉結點外，每個結點都有若干個后繼結點葉結點的后繼結點個數為0樹中每個元素的前驅的個數不會多于1個，后繼的個數可以是任意個樹是一種層次結構，設根為0層，根的孩子結點為1層，依此類推一般地，若某個結點位于i（i≥0）層，則它的孩子結點位于i+1層樹中結點的最大層數定義為樹的深度最大層數加1為樹的高度樹中從某一結點出發，到達另一個結點之間所經過的邊組成一條路徑路徑中所含的邊數為路徑長度雖然樹的路徑定義中并沒有限制路徑的方向，但路徑通常是沿一個方向延伸的，即從某一結點向根的方向延伸，或是從某一結點向葉結點方向延伸通常，以組成路徑的結點序列來表示該條路徑m（m≥0）棵互不相交的樹構成森林對樹中每個結點來說，其子樹的集合即為森林第二節二叉樹定義5-2二叉樹（binarytree）是結點的一個有限集合，這個集合或者為空，或者是由一個根結點以及兩棵互不相交的、分別稱為這個根的左子樹和右子樹的二叉樹組成。左子樹和右子樹的根分別稱為此二叉樹根結點的左孩子結點和右孩子結點二叉樹的左子樹和右子樹都可以存在或者為空，不同的存在狀態可以組合出5種基本形態一棵高度為h的二叉樹若有2h-1個結點，則二叉樹稱為滿二叉樹從形式上來看，滿二叉樹中除葉結點外，每個結點都有兩個孩子結點，即除最后一層外，每一層的結點都是“滿”的滿二叉樹中的n個結點進行連續編號，從編號為0的結點開始，由連續編號的任意多個結點組成的二叉樹稱為完全二叉樹特殊二叉樹滿二叉樹和完全二叉樹完全二叉樹的特性

二叉樹的性質性質1在二叉樹的i層上最多有2i個結點(i≥0)證明：使用數學歸納法證明

歸納基礎：

對于非空的二叉樹T，根在0層，本層只有20=1個結點，結論成立

歸納假設：

設二叉樹T中i-1層最多有2i-1個結點，考慮i層，由于i層的結點均為i-1層結點的孩子結點，而二叉樹中每個結點最多有兩個孩子結點，故i層最多有2

2i-1=2i個結點

根據歸納法原理，性質1得證

性質3對任何非空二叉樹T，設n0是葉結點的個數，n2是度為2的結點的個數，則有n0=n2+1證明：設二叉樹T中度為1的結點個數為n1，則T中結點總數n為 n=n0+n1+n2 n-1=2

n2+1

n1+0

n0

將上兩式聯立求解，得到 n0=n2+1

例5-3一棵二叉樹共有20個結點，其中葉結點為5個，則度為l的結點個數是（）。A．11B．9C．6D．4答案為A二叉樹的存儲——順序存儲結構對于完全二叉樹，各層自上至下，同層間自左至右，將結點依次存入數組從前至后的各個元素中。按照前面使用過的編號方法，一般來講，編號為i的結點存放在數組中下標為i的位置使用這樣的存儲規則可以很方便地找到二叉樹中的相關結點，即若知道二叉樹某一結點保存在數組中下標i的位置，則可以很方便地求出它的雙親結點（若存在）和左、右孩子結點（若存在）在數組中的位置對于一般的二叉樹，順序存儲的思想是，針對二叉樹中的每個位置，不論這個位置有沒有結點，都在數組中預留保存空間。采用這種存儲方式保存完全二叉樹時，既不浪費空間，又便于有關操作的實現例5-4設高度為k（k≥1）的二叉樹T采用順序存儲結構保存在數組B[2k-1]中，在沒有保存T中元素的數組位置中，保存一個區別于T中元素的特殊標記。B中保存的特殊標記個數最多為（）。A．k-1B．2k-1C．2k-k-1D．2k-1答案為C鏈式存儲結構定義一個結點結構：它含有兩個指針域，一個指針用來指向該結點左孩子所在的結點，稱為左孩子指針，簡稱為左指針；另一個指針用來指向該結點右孩子所在的結點，稱為右孩子指針，簡稱為右指針。此外，還定義一個用來保存結點中數據的數據域二叉鏈表表示二叉樹結點類的定義及二叉樹的定義二叉鏈表中結點類的定義及二叉樹的定義typedefintELEMType;typedefstructBNode //二叉樹結點{ ELEMTypedata; //數據域 structBNode*left,*right;

//指向左孩子、右孩子的指針}BinTNode;typedefBinTNode*BTree; //二叉樹二叉鏈表中到底有多少空指針域呢設二叉樹中有n個結點，每個結點都含有兩個指針域，則二叉鏈表中共有2

n個指針域已知含n個結點的樹中僅含有n-1個分支，即只有n-1個指針域不為空，則其余的n+1個指針域均為空可以看出，二叉鏈表中有超過一半的指針域都是空的，這些都是結構性開銷第三節二叉樹的操作二叉樹的生成按照二叉樹的順序存儲方式，將二叉樹各結點值保存在一維數組中，然后建立二叉鏈表如要建立如下的二叉鏈表輸入的數組是inta[]={0,1,2,3,4,NA,5,NA,NA,NA,NA,NA,NA,6};函數CreateBinaryTree遞歸處理二叉鏈表的生成調用它的主程序中先創建一個根結點，其中保存數組首元素的值，該結點作為參數傳遞給函數CreateBinaryTree。這個結點的位置是下標0，將這個位置值也作為參數傳給函數CreateBinaryTree主程序中BTreeroot;root=(BTree)malloc(sizeof(BinTNode));root->data=a[0];root->left=NULL;root->right=NULL;調用函數CreateBinaryTree。參數0是起始位置CreateBinaryTree(0,n,a,root);生成二叉鏈表如果下標i處的結點有左孩子，則其應該保存在下標2

i+1處如果有右孩子，則應該保存在下標2

i+2處故在函數內，判斷數組中位置2

i+1及位置2

i+2處是否保存了元素值如果確實有值，則分配空間創建結點且保存數組中相應位置的元素值，并讓下標i處結點的相應指針指向新創建的結點然后再以2

i+1或2

i+2為參數值，遞歸調用函數，去處理2

i+1或2

i+2位置處結點的左孩子和右孩子如果數組中數據的存儲是正確的，則能正確建立二叉鏈表。如果位置2

i+1或位置2

i+2處沒有保存元素值，則遞歸結束二叉樹的遍歷對非空的二叉樹的遍歷可以相應地分解為三項“子任務”訪問根結點遍歷左子樹（即依相應的規律訪問左子樹中的全部結點）遍歷右子樹（即依相應的規律訪問右子樹中的全部結點）常規的3種遍歷算法分別是先序遍歷、中序遍歷和后序遍歷。這3種遍歷也分別稱為先根遍歷、中根遍歷和后根遍歷先序遍歷算法若二叉樹為空，則返回；否則依次執行以下操作（1）訪問根結點（2）先序遍歷左子樹（3）先序遍歷右子樹中序遍歷算法若二叉樹為空，則返回；否則依次執行以下操作（1）中序遍歷左子樹（2）訪問根結點（3）中序遍歷右子樹后序遍歷算法若二叉樹為空，則返回；否則依次執行以下操作（1）后序遍歷左子樹（2）后序遍歷右子樹（3）訪問根結點先序遍歷過程中序遍歷過程后序遍歷過程例5-6寫出其先序、中序及后序遍歷序列先序遍歷序列為A,B,D,G,H,J,K,E中序遍歷序列為G,D,J,H,K,B,E,A后序遍歷序列為G,J,K,H,D,E,B,A先序遍歷算法先序遍歷算法中序遍歷算法中序遍歷算法后序遍歷算法后序遍歷算法給出二叉樹的先序遍歷序列和中序遍歷序列，能唯一確定該二叉樹給出二叉樹的后序遍歷序列和中序遍歷序列，能唯一確定該二叉樹例5-7設二叉樹T的先序遍歷序列是A,B,D,G,H,J,K,E，中序遍歷序列是G,D,J,H,K,B,E,A，畫出二叉樹T由先序遍歷序列可知，T的根是A在中序遍歷序列中查找A的位置，位于A前面的是其左子樹的中序遍歷序列，位于A后面的是其右子樹的中序遍歷序列從而將原問題的求解（對整棵樹的還原）分解為兩個更小問題的求解（對兩棵子樹的還原）例5-8統計以二叉鏈表表示的二叉樹T中葉結點的個數T中葉結點的個數等于根左子樹中葉結點的個數加上根右子樹中葉結點的個數。所以如果遞歸調用已經得到了兩棵子樹中葉結點的個數，那么將結果相加即求解例5-9編寫程序，返回二叉樹T的高度仍是使用遞歸的思想去編寫程序。如果左子樹的高度和右子樹的高度都已經知道，則二叉樹T的高度就可求得，樹的高度是兩棵子樹中較高者的高度再加1層序遍歷所謂按層遍歷，即是從根結點開始逐層向下遍歷，直到最后一層對于同一層的結點，由左到右遍歷各結點同一層中的結點相繼被訪問，同時，它們之間的相對次序也決定著它們孩子結點的相對次序。即同一層中的結點u和結點v，若先遍歷u再遍歷v，則u的孩子結點的遍歷也早于v的孩子結點的遍歷按層進行遍歷先訪問最上面一層即0層中的元素，輸出1然后依次訪問1的子結點2和3再繼續訪問2的子結點和3的子結點依此類推，得到的層序遍歷結果是：1,2,3,4,5,6,7層序遍歷算法二叉樹層序遍歷的算法遍歷的非遞歸實現仍然將一棵二叉樹分為三部分：根、左子樹和右子樹。從根開始遍歷二叉樹時，根的左子樹和右子樹的遍歷不能同時進行，只能先遍歷一棵子樹，同時保存二叉樹中尚不能遍歷部分的信息，留待一棵子樹處理完畢后再處理分析二叉樹的遍歷過程可知，使用棧來保存相關信息先序遍歷算法在進入左子樹進行處理之前，需要在棧中保存右子樹的相關信息，以便當左子樹處理完畢，能夠根據保存的線索找到右子樹的根。所以，棧中保存右子樹的根即可程序中序遍歷算法中序遍歷時，先進行左子樹的遍歷，然后遍歷根，再遍歷右子樹。所以棧中保存根的信息，遍歷完左子樹后，從棧中找到根，訪問根，同時也能容易地找到右子樹程序后序遍歷算法類似于中序遍歷過程，在進入左子樹遍歷之前，需要先保存根的信息。當左子樹遍歷結束，從棧中找到根，但此時因為右子樹尚未遍歷，所以根并不能從棧中彈出，仍需要保存在棧中，只有當右子樹也遍歷結束后，才能訪問根棧中保存的結點需要入棧兩次出棧兩次。為了能有所區別，二叉樹結點入棧時，附帶一個標記位flag。第一次出棧時，并不訪問結點。第二次出棧時才訪問它將二叉樹結點和標記組合在一起，定義新的棧的類型，專用于非遞歸實現二叉樹的后序遍歷過程typedefstruct SNode //進棧帶標記結點{ BinTNodebtreeNode; //二叉樹結點

intflag; //標記}StackTNode; typedefstruct{ //用于后序遍歷的棧 StackTNodeelement[maxSize]; inttop; //棧頂位置}SeqBTreeStackforPostT;程序二叉樹的應用可以使用二叉樹來表示一個表達式，這樣的二叉樹稱為表達式樹2*y*(a+3*y)-b畫出表達式樹先根據運算符的優先級對表達式加括號去掉最外層括號。中間的運算符為根，前后兩部分分別對應于左子樹和右子樹對左子樹遞歸執行步驟②對右子樹遞歸執行步驟②當遇到空串時，遞歸結束例5-12已知算術表達式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為（）A．-A+B*C/DEB．-A+B*CD/EC．-+*ABC/DED．-+A*BC/DE答案：D

第四節堆及優先隊列前一種關系表明，任何一個分支結點的值都不大于它子結點的值，所以樹根結點的值是全部結點中的最小值。這樣的堆稱為最小堆或小根堆后一種關系表明，任何一個分支結點的值都不小于它子結點的值，故樹根結點的值是全部結點中的最大值。這樣的堆稱為最大堆或大根堆樹根結點稱為堆頂堆的定義中還隱含了遞歸的含義，當用完全二叉樹的形式表示堆時，樹中的任意一棵子樹都可以構成堆，并且保持與原來同樣的性質最大堆中任何結點的子樹仍是最大堆最小堆中任何結點的子樹仍是最小堆最小堆和最大堆堆的類型定義#defineHeapSize30 //堆的容量typedefintELEMType; //元素類型typedefstructHeap{ ELEMTypeheap[HeapSize]; //存放元素的數組 intn; //堆中當前元素個數};堆的基本操作intcreatHeap(maxHeap*H,ELEMTypearr[],intn); //創建堆intinsertHeap(maxHeap*H,ELEMTypex); //在堆中插入元素xintdeleteHeap(maxHeap*H,ELEMType*x); //刪除堆頂元素intisHeapEmpty(maxHeap*H); //如果堆為空，則返回1，否則返回0intisHeapFull(maxHeap*H); //如果堆為滿，則返回1，否則返回0最大堆的類型定義#defineHeapSize30 //堆的容量typedefintELEMType; //元素類型typedefstructmaxHeap{ ELEMTypeheap[HeapSize]; //存放元素的數組 intn; //堆中當前元素個數};判空、判滿創建最大堆向最大堆中插入新元素刪除堆頂元素例5-1370,13,65,24,56,48,92,86，將其建成最大堆例5-14在最大堆中插入新元素40例5-15刪除最大堆的堆頂優先隊列一些應用中，各元素本身還被賦予一個優先值，可以用一個非負整數表示優先值。優先值也稱為優先權。具有優先值的各元素保存在一個結構中，這個結構稱為優先隊列。輸出時，選擇最優先的元素輸出。“最優先”取決于優先值的定義，可以是優先值最小，也可以是優先值最大。第五節樹和森林樹的存儲結構父結點表示法孩子結點表示法孩子-兄弟表示法父結點表示法樹中每個結點至少含兩個域，一個域用來保存結點本身的值，另一個域用來保存結點之父結點的相關信息孩子結點表示法父結點-孩子結點表示法孩子-兄弟表示法為樹中的每個結點定義一個存儲結點，其中有左、右兩個指針域，左指針域指向這個結點的第一個孩子結點，右指針域指向這個結點的下一個兄弟結點樹、森林與二叉樹的轉換樹和二叉樹都可以用二叉鏈表作為存儲結構同一個二叉鏈表，若按樹的存儲含義來解釋，可以還原為樹。若按二叉樹的存儲含義來解釋，可以還原為二叉樹正是因為這一點，可以在樹與二叉樹之間建立一種對應關系轉換規則規則1：將森林轉換成二叉樹設F={T1,T2,…,Tm}是森林，則可按如下規則將森林F轉換為一棵二叉樹B=(root,LB,RB)（1）若F為空（m=0），則B為空樹（2）若F非空（m>0），則森林中T1的根作為二叉樹B的根root；T1中各子樹組成的森林F1={T11,T12,…,T1s}轉換成的二叉樹作為B的左子樹BL；森林F’={T2,T3,…,Tm}轉換成的二叉樹作為B的右子樹BR森林轉換為二叉樹轉換規則規則2：將二叉樹還原為森林設B=(root,BL,BR)是一棵二叉樹，則可按如下規則轉換成森林F={T1,T2,…,Tm}（1）若B為空，則F為空（2）若B非空，則B的根root作為F中第一棵樹T1的根；B的左子樹BL還原得到的森林作為T1的各子樹；B的右子樹BR還原得到的森林作為F中的T2,T3,…,Tm樹和森林的遍歷樹的兩種遍歷策略先序（根）遍歷先訪問樹的根結點，再依次先序遍歷根結點的各棵子樹后序（根）遍歷若樹的根結點有子樹，則首先后序遍歷各棵子樹，然后再訪問根結點；否則（根結點無子樹），只訪問根結點森林的兩種遍歷策略先序遍歷森林森林的先序遍歷過程，是按照樹的排列次序，先序遍歷各棵樹后序遍歷森林森林的后序遍歷過程，是按照樹的排列次序，后序遍歷各棵樹可以看出，森林的遍歷序列中，各棵樹中的結點不會混雜在一起森林與對應的二叉樹的遍歷序列的關系二叉樹的先序遍歷序列和中序遍歷序列，與森林的先序遍歷序列和后序遍歷序列分別相同第六節哈夫曼樹及哈夫曼編碼編碼ASCII編碼、Unicode碼、電報碼定長編碼算法簡單，效率高在編碼長度確定之后，譯文的長度完成取決于原文的長度變長編碼變長編碼前綴特性：一個編碼方案中，任何一個字符的編碼都不是該方案中任何其他字符編碼的前綴，這樣的編碼稱為具有前綴特性正是因為編碼方案具有前綴特性，才能夠保證譯碼過程的正確性和唯一性。可以使用二叉樹來表示一個編碼方案在二叉樹的分支上標注0或1，從根到某結點的路徑上，各分支標注的0或1組成一個編碼哈夫曼樹二叉樹中，葉結點的帶權路徑長度定義為葉結點的權值乘上其到根結點的路徑長度二叉樹的帶權路徑長度，就是樹中所有葉結點的帶權路徑長度之和二叉樹的外部帶權路徑長度記為WPL其中n為葉結點個數，wk為第k個葉結點的權值，lk為第k個葉結點的路徑長度各字符出現的頻度分別是6、12、25、30，構造4棵二叉樹，分別計算其WPL值4棵二叉樹的帶權路徑長度WPL分別為134、195、139和146我們的任務是構造具有最小WPL且滿足前綴特性的編碼樹設有n個權值{w1,w2,…,wn}，構造具有n個葉結點的二叉樹，每個葉結點帶有一個權值wi。在所有這樣的二叉樹中，帶權路