數(shù)據(jù)結(jié)構(gòu)樹-2課件

5.5線

索

樹對二叉樹進行某種遍歷，可以得到一個線性有序的序列。例如對某二叉樹的中序遍歷結(jié)果:K,D,H,B,G,E,A,X,M,C,F該樹轉(zhuǎn)為線性排列，顯然其中結(jié)點具有唯一前驅(qū)和唯一后繼。圖5.5.1二叉樹ABCEFGHDKXMY想得到一個結(jié)點的前驅(qū)或后繼結(jié)點，每次總是從根開始遍歷。無論是采用遞歸方式，還是非遞歸方式，遍歷算法中一定包含著堆?？臻g。2.線索的方法存儲結(jié)構(gòu)

中序遍歷:A的前驅(qū)是————，B的前驅(qū)是————;E的前驅(qū)是————；D的前驅(qū)是————；圖5.5.1二叉樹ABCEFGHDKXMY一個結(jié)點N如果有左子樹，則該結(jié)點的前驅(qū)就是其左子樹中最右的子孫P。這個子孫結(jié)點的右鏈接域一定為空。EHGK中序遍歷:H的前驅(qū)是D，G的前驅(qū)是B;X的前驅(qū)是A圖5.5.1二叉樹ABCEFGHDKXMY一個結(jié)點N如果沒有左子樹，則該結(jié)點的前驅(qū)就是其所有祖先中,最接近它的“右傾”祖先P。這個結(jié)點N的左鏈接域本身就是空。線索二叉樹的實現(xiàn)規(guī)定：1）若結(jié)點有左子樹，則Lchild指向其左孩子；否則，Lchild指向其直接前驅(qū)(即線索)；2）若結(jié)點有右子樹，則Rchild指向其右孩子；否則，Rchild指向其直接后繼(即線索)。如何區(qū)別？約定:當flag域為0時,表示正常情況;當flag域為1時,表示線索情況.前驅(qū)(后繼)左(右)孩子為區(qū)別兩種不同情況，特增加兩個標志域：各1bitLflagLChilddataRChildRflag圖5.5.5中序線索樹A00B00C10∧D11E11F1∧1D,B,E,A,C,FNULLNULL圖5.5.6二叉樹ABEFHKNMDC圖5.5.7二叉樹前序遍歷線索樹ABMCKDNFHE圖5.5.8二叉樹中序遍歷線索樹ABMFNHKECD圖5.5.9二叉樹后序遍歷線索樹ABMDKHNFCE有關(guān)線索二叉樹的幾個術(shù)語：線索鏈表：線索：線索二叉樹：線索化：用含flag的結(jié)點樣式所構(gòu)成的二叉鏈表指向結(jié)點前驅(qū)和后繼的指針加上線索的二叉樹對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程線索化過程就是在遍歷過程中修改空指針的過程：將空的Lchild改為結(jié)點的直接前驅(qū)；將空的Rchild改為結(jié)點的直接后繼。非空指針呢？仍然指向孩子結(jié)點（稱為“正常情況”）二叉線索樹的結(jié)點結(jié)構(gòu)定義typedefstruct{ EType data;BinaryTreeNode *LChild;bool Lflag;BinaryTreeNode *RChild;bool Rflag;}BinaryTreeNode；前序二叉線索樹的遍歷

voidThreadPreOrder(BinaryTreeNode*BT){//前序二叉線索樹的遍歷BinaryTreeNode*p=BT;while(p){cout<<p->data<<"";if(!p->Lflag) p=p->LChild;else p=p->RChild;}}BinaryTreeNode *p=BT;bool flag;while(!p){while(!p->Lflag) //查找一棵子樹的最左子孫 p=p->LChild;flag=true;while(flag&&!p){cout<<p->data<<""; //訪問結(jié)點p=p->RChild; //查找p的右子樹的根或后繼結(jié)點if(!p->Rflag) //p結(jié)點存在右子樹時，為強制退出作準備flag=p->Rflag;}}二叉樹轉(zhuǎn)化為二叉線索樹二叉樹轉(zhuǎn)化為中序二叉線索樹P:當前訪問結(jié)點，

q:指向其前驅(qū)結(jié)點。另設(shè)一個堆棧，以非遞歸方式遍歷二叉樹。算法結(jié)束的條件是堆棧和p同時為空。B) “走過”p左子樹上的所有結(jié)點，直到左子樹為空。如果某結(jié)點無左孩子，則將該結(jié)點的左鏈接域的指針作為線索指向其前驅(qū)q，并將q指向這個無左孩子的結(jié)點；轉(zhuǎn)C步驟。C) 退棧，直到找到下一個可以“訪問”的結(jié)點，并用p指向該結(jié)點；如果p的前驅(qū)（q指向）的右鏈接域為空，則將q的右鏈接域作為線索指向p。轉(zhuǎn)B步驟。3。中序二叉樹線索樹中結(jié)點的插入

將一個由T指針指向的新結(jié)點插入到二叉線索樹中，作為S所指的結(jié)點左孩子或S所指的結(jié)點右孩子。如果S原來已經(jīng)存在左子樹（或右子樹），就將原來的左子樹（或右子樹）作為新結(jié)點T的左孩子（或右孩子）。線索樹的插入問題中，將S結(jié)點與T結(jié)點鏈接在一起是件簡單的事情，關(guān)鍵問題是要改變各結(jié)點的線索和對應(yīng)的線索標志。中序線索樹中插入的新結(jié)點T作為S的左孩子

If:S結(jié)點無左孩子新結(jié)點T的各值的變化：

T->RChild=S；

T->LChild=S->LChild。鏈接域標志的變化：

T->Lflag=1；T->Rflag=1S結(jié)點各個值的變化S->LChild=T；S->Lflag=0或false。

F

←最接近S結(jié)點的“右傾”祖先PSTS結(jié)點的最右子孫→

(b)S有左子樹

T

PSIf:S結(jié)點有左孩子//找S左子樹中的最右子孫q=T->LChild;while(!q->Rflag)q=q->RChild;q->RChild=T;

5.6一般樹的表示

和遍歷

ABCDEFGHIJK圖5.6.1一棵樹A∧BCDE∧FG∧H∧IJK∧圖5.6.2一棵樹存儲結(jié)構(gòu)typedefstructTreeNode{ EType data; TreeNode *son; TreeNode *next;}TreeNode；樹和森林與二叉樹的轉(zhuǎn)換轉(zhuǎn)換步驟：step1:將樹中同一結(jié)點的兄弟相連;加線抹線旋轉(zhuǎn)樹如何轉(zhuǎn)為二叉樹？孩子—兄弟表示法step2:保留結(jié)點的最左孩子連線，刪除其它孩子連線；step3:將同一孩子的連線繞左孩子旋轉(zhuǎn)45度角。二叉樹怎樣還原為樹？abeidfhgc要點：逆操作，把所有右孩子變?yōu)樾值埽?/p>

abdefhgicABCDEFGHJIABCDEFGHJIABCDEFGHJI5.6.2二叉樹、一般樹及森林的關(guān)系兄弟相連長兄為父頭樹為根孩子靠左A5.6.3一般樹的遍歷概念

樹的遍歷:例如：abdec前序序列：后序序列：abcdebdcea前序、后序前序遍歷訪問根結(jié)點；依次前序遍歷根結(jié)點的每棵子樹。后序遍歷依次后序遍歷根結(jié)點的每棵子樹；訪問根結(jié)點。樹沒有中序遍歷樹若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否一樣？abdec先序遍歷：后序遍歷：中序遍歷：decbaabdecabcdebdcea1.樹的先序遍歷與二叉樹的先序遍歷相同；2.樹的后序遍歷相當于二叉樹的中序遍歷；結(jié)論：樹的先序序列：abcde樹的后序序列：bdcea5.6.4一般樹的運算

一般樹以二叉樹形式存儲時，一般樹的大部分的運算可以用二叉樹的算法來實現(xiàn)，如一般樹的前序遍歷、后序遍歷、結(jié)點的個數(shù)等。一般樹二叉樹形式存儲下結(jié)點的度。一般樹二叉樹形式存儲下層次遍歷

樹的應(yīng)用一（族譜）樹的應(yīng)用二：利用樹型結(jié)構(gòu)的搜索算法模擬因特網(wǎng)域名的查詢5.7.1分類二叉樹

分類二叉樹又可以稱為二叉排序樹或二叉搜索樹。在大量數(shù)據(jù)的處理中，為了便于數(shù)據(jù)查找，對輸入的數(shù)據(jù)采用分類二叉樹的方式存儲，從而可以大大提高查找的效率，其時間效率是O(nlog2n)。

按中序遍歷一棵分類二叉樹，其結(jié)果是一個按某一特征值（關(guān)鍵字）排序的線性序列。定義：設(shè)key1,key2,…,keyn是一個數(shù)據(jù)集合中數(shù)據(jù)元素的對應(yīng)關(guān)鍵字，按下列原則建立的二叉樹稱為分類二叉樹。(1)每個元素有一個關(guān)鍵字，并且沒有任意兩個元素有相同的關(guān)鍵字。(2)根結(jié)點的左子樹的關(guān)鍵字（如果存在）小于根結(jié)點的關(guān)鍵字。(3)根結(jié)點的右子樹的關(guān)鍵字（如果存在）大于根結(jié)點的關(guān)鍵字。(4)根結(jié)點的左右子樹也都是分類二叉樹。數(shù)據(jù)集合的關(guān)鍵字：

｛15，23，12，8，13，9，25，21，18｝

15(a)1523(b)152312(c)1523128(d)152312813(e)1523128139(f)152312813925(g)15231281392521(h)1523128139252118(i)1523128139252118如何使中序遍歷的結(jié)果按關(guān)鍵字降序排列呢？

｛15，23，12，8，13，9，25，21，18｝2分類二叉樹運算

1）分類二叉樹中數(shù)據(jù)元素的查找

while(p) if(SearchKey<p->data.key) p=p->LChild; else if(SearchKey>p->data.key) p=p->RChild; else { x=p->data; returntrue;}圖5.7.2查找結(jié)點1815231281392521182。將結(jié)點插入到分類二叉樹中

插入算法與查找算法的一個顯著區(qū)別是：查找中，如果找到，則成功。在插入時也要查找，是當查找失敗時，說明找到了插入點；查找成功時，說明有相同的數(shù)據(jù)元素出現(xiàn)，這在分類二叉樹中是不允許的，即插入失敗。圖5.7.3插入新結(jié)點22152312813925211822←插入結(jié)點while(p){ parent=p; if(x.key<p->data.key) p=p->LChild; else if(x.key>p->data.key) p=p->RChild; else returnfalse;//重復(fù)出現(xiàn)，即相等值結(jié)點出現(xiàn)}//找到插入點，為x申請一個空間填入其值，并將該結(jié)點連接至parent BinaryTreeNode*q=newBinaryTreeNode; q->data=x; If(BT){//原樹非空 if(x.key<parent->data.key) parent->LChild=q; else parent->RChild=q; } else//插入到空樹中 BT=q; returntrue;}刪除分類二叉樹中的結(jié)點刪除結(jié)點x的三種情況：x是葉子結(jié)點；x只有一個非空子樹；x有兩個非空子樹(a)刪除左葉子

x

←被刪結(jié)點p指向(b)刪除根結(jié)點且只有一個孩子x

←被刪結(jié)點p指向←新根(c)刪除非根結(jié)點且只有一個孩子x

←被刪結(jié)點p指向圖5.7.4刪除一個左右子樹非空的結(jié)點x

x最小

(d)

最大←被刪結(jié)點p最大或最小其中一個結(jié)點替換x堆排序1991年計算機先驅(qū)獎獲得者、斯坦福大學(xué)計算機科學(xué)系教授羅伯特·弗洛伊德(RobertW．Floyd)和威廉姆斯(J．Williams)在1964年共同發(fā)明了著名的堆排序算法(HeapSort)1堆樹的定義

最大樹：所謂最大樹就是每個結(jié)點的值都大于或等于其子結(jié)點（如果存在）值。最小樹：所謂最小樹就是每個結(jié)點的值都小于或等于其子結(jié)點（如果存在）值。堆樹簡稱為堆，是一棵二叉樹。堆有如下特征：如果一棵順序二叉樹本身又滿足最大樹的條件，則這棵順序二叉樹就是最大堆；如果一棵順序二叉樹本身又滿足最小樹的條件，則這棵順序二叉樹就是最小堆。圖5.7.5最大樹或最小樹52305052417581252301755230505241755230524175(d)(a)(b)(c)(e)20一般樹，最大樹

二叉樹

，最小樹

順序二叉樹最大堆

？

2堆樹的意義

順序二叉樹的高度最小，具有n個結(jié)點的順序二叉樹的高度是log2n。如果在這棵樹中按分枝查找，搜索的次數(shù)可以達到最少；順序二叉樹以順序存儲方式存儲時，空間不會造成浪費，節(jié)省了動態(tài)存儲方式下鏈接域的空間耗費。利用數(shù)組下標，可以用公式來表達順序二叉樹中各結(jié)點之間的邏輯關(guān)系。堆排序--數(shù)據(jù)排序的一種經(jīng)典方法

先將堆頂元素（最大結(jié)點）移到結(jié)果數(shù)據(jù)存儲空間，再從堆中余下的結(jié)點（左子樹或右子樹）中選出一個最大結(jié)點，移到堆頂，即將堆中余下的結(jié)點重新“調(diào)整”為一個新堆.將堆頂結(jié)點移到結(jié)果數(shù)據(jù)存儲空間的下一個空間位置，如此下去，直到所有的結(jié)點都被移到結(jié)果數(shù)據(jù)存儲空間。5230524175移去堆頂52304175如何構(gòu)造一個初始堆樹?有了初始堆，在排序時，當移走根結(jié)點時，對余下的樹又如何再“調(diào)整”為一棵新堆?移去該結(jié)點？

1.初始化一個非空的最大堆

一個順序二叉樹以順序存儲方式存儲時，就是連續(xù)地存儲在數(shù)組元素空間中.第一個元素位置存放的是順序二叉樹的根結(jié)點，最后一個數(shù)組元素位置存放的是順序二叉樹中最下面一層中最右的結(jié)點。15221235479555624715836916106211121238052361662553812127952415每個數(shù)據(jù)在邏輯上關(guān)聯(lián)的數(shù)據(jù)不一定是接下來的數(shù)組空間中的數(shù)據(jù).i:左孩子2*i;右孩子2*i+1臨時存放數(shù)據(jù)元素245堆：比較交換結(jié)點i，2*i及2*i+1構(gòu)造初始堆

首先將所有的葉子結(jié)點（最底層結(jié)點）看成為若干個子堆(只有一個結(jié)點)N的子樹已經(jīng)是子堆，則新的根結(jié)點是N和它的子樹（一個或兩個）根結(jié)點的值中最大的結(jié)點值。

構(gòu)造N所指結(jié)點為根的堆算法思想：A.

先將N所指結(jié)點的值復(fù)制到一個工作空間中臨時存放。B.

再將N所指結(jié)點的孩子中，值較大的與工作空間中的值比較：1)

如果工作空間中值更大，新堆已經(jīng)形成，就將工作空間中的值存放到N所指的位置，結(jié)束。2）如果某個孩子的結(jié)點值更大，則將這個值存放到這個孩子雙親的結(jié)點位置，即N位置。此時，工作空間中的結(jié)點還未找到存放位置，再將上移的孩子結(jié)點位置作為N所指的新位置，轉(zhuǎn)到B步驟。for(inti=HeapSize/2;i>=1;i--)//從最后一個結(jié)點的根開始，直到第一個結(jié)點1)i=HeapSize/2=10/2=5，heap[5]=722)i--;i=5;heap[4]=53…..123456789100最大堆調(diào)整(1)最大堆調(diào)整(2)初始化一個非空的最大堆算法

for(inti=HeapSize/2;i>=1;i--){//從最后一個結(jié)點的根開始，直到第一個結(jié)點heap[0]=heap[i];//將i結(jié)點值復(fù)制到工作空間heap[0]中

intson=2*i; //son的雙親結(jié)點是heap[0]的目標位置， //son首先指向i的左孩子

while(son<=HeapSize){//找左右孩子中較大結(jié)點if(son<HeapSize&&heap[son]<heap[son+1]) son++;//son<HeapSize時，存在右孩子，如左孩子小于右孩子，son指向右孩子if(heap[0]>=heap[son])//大孩子再與工作空間中結(jié)點值再比較 break;//工作空間中值大，找到heap[0]的目標位置heap[son/2]=heap[son];//將大孩子上移至雙親位置son*=2;//son下移一層到上移的結(jié)點（大孩子）位置}heap[son/2]=heap[0]; //heap[0]存放到目標位置4.堆排序

不必再開辟另一個結(jié)果存儲區(qū)，只要將刪除的堆頂結(jié)點存放到當前堆的最后一個葉子結(jié)點空間中就可以。

492525*211608012345082525*16214902543149252125*160808252125*1649交換0號與5號對象,5號對象就位初始最大堆基于初始堆進行堆排序0816

21

25*

25

492525*082116490123451625*082521490254312525*210816491625*210825

49交換0號與4號對象,4號對象就位從0號到4號重新調(diào)整為最大堆25*1608212549012345081625*25214902543125*16210825

4908162125*

25

49交換0號與3號對象,3號對象就位從0號到3號重新調(diào)整為最大堆211625*082549012345081625*25214902543121160825*

25

49081621

25*

25

49交換0號與2號對象,2號對象就位從0號到2號重新調(diào)整為最大堆160825*212549012345081625*25214902543116082125*

25

490816

21

25*

25

49交換0號與1號對象,1號對象就位從0號到1號重新調(diào)整為最大堆利用分類二叉樹查找及堆排序?qū)崿F(xiàn)學(xué)生成績管理

堆排序算法voidHeapSort(ETypea[],intn){//利用堆對a[1:n]數(shù)組中的數(shù)據(jù)排序heap=a; MaxHeapInit(heap,intn); ETypex;for(inti=n-1;i>=1;i--){MaxHeapDelete(heap,&x);heap[i+1]=x;}}StatusMaxHeapDelete(ETypea[],EType&x){//插入x到最大堆中Heap=a;if(HeapSize==0)returnERROR; //堆空x=heap[1]; //最大結(jié)點存放到xheap[0]=heap[HeapSize--]; //最后一個結(jié)點存放到heap[0]，調(diào)整堆中元素的個數(shù)inti=1,son=2*i;

while(son<=HeapSize){if(son<HeapSize&&heap[son]<heap[son+1])son++;if(heap[0]>=heap[son])break;heap[i]=heap[son]; //孩子上移i=son; //下移根結(jié)點指針，繼續(xù)比較son=son*2;}heap[i]=heap[0];returnOK;}5.7.3樹的路徑長度和哈夫曼樹（Huffman）樹的路徑長度1)簡單路徑長度:從樹中一個結(jié)點到另一個結(jié)點之間的分枝構(gòu)成這兩個結(jié)點之間的路徑。2)樹的簡單路徑長度:是指從樹的根結(jié)點到每個結(jié)點的路徑長度之和。

3)加權(quán)路徑長度:樹中的每個葉子結(jié)點有權(quán)值，即每個葉子結(jié)點的大小不同（重要性不同），那么從葉子到根結(jié)點之間的長度，就是葉子的權(quán)值與葉子到根結(jié)點之間路徑長度（分枝數(shù)）的乘積。AEIHDGFBC圖5.7.10一棵二叉樹AEIHDGFBC圖5.7.11一棵順序二叉樹1*2+2*3+3*3=17

1*2+2*4+3*2=16

結(jié)論:如果結(jié)點數(shù)相同，則順序二叉樹是具有最小簡單路徑長度的二叉樹。圖5.7.13一棵帶權(quán)二叉樹EIHF2364圖5.7.12一棵帶權(quán)二叉樹EIHF64236*3+4*3+2*2+3*2=40

2*3+3*3+6*2+4*2=35結(jié)論:結(jié)點的權(quán)值大的結(jié)點更接近根結(jié)點，樹的加權(quán)路徑長度就相對更小。

實際應(yīng)用:情報檢索，信息編碼數(shù)據(jù)元素的信息或信息存放的地址存入葉結(jié)點之中，分枝結(jié)點僅僅用于檢索判斷條件。不同的信息具有不同的檢索頻率，檢索頻率高的信息就是檢索概率大的信息，概率就是一個權(quán)值。實際檢索時，檢索頻率高的信息應(yīng)該檢索判斷的次數(shù)盡可能的少，即大權(quán)值的結(jié)點如果更接近根結(jié)點，檢索樹的檢索效率就越高，也就是樹的加權(quán)路徑長度越小。

2.哈夫曼樹及構(gòu)成算法哈夫曼樹又稱為最優(yōu)二叉樹:有n個結(jié)點，它們分別具有不同的權(quán)值，將這n個結(jié)點作為葉結(jié)點可以構(gòu)造出m種不同的二叉樹，這些二叉樹具有不同的加權(quán)路徑長度，則其中加權(quán)路徑長度最小的二叉樹稱為最優(yōu)二叉樹或哈夫曼樹。Huffman常譯為赫夫曼、霍夫曼、哈夫曼等(a)原始堆623439623346233499(b)初始化堆236439233642336499最小堆刪除2，3后的堆349653496523(d)插入5后的堆3465922L↓33R↓5523D↓346933469(c)刪除2，3后的堆34963496(e)刪除3，4后的堆5695696952333L↓44R↓7734D↓4569(f)插入7后的堆5679569769523734(g)刪除5，6后的堆679797997345L↓66R↓11D↓523523116(h)插入11后的堆791179119734523116(i)刪除7，9后的堆91111169734115231167L↓99R↓16D↓734(j)插入16后的堆11161116523116169734(k)刪除11，16后的堆16973411L↓16R↓27D↓52311627523116169734(l)插入27后的堆272727523116169734圖5.7.14利用堆構(gòu)造哈夫曼樹的過程檢索判斷檢索判斷{2，3，3，4，6,9}構(gòu)造哈夫曼樹.27523116169734{2，3，3，4，5,6,9}{2，3，3，4，5,6,7,9}{2，3，3，4，6,9}{2，3，3，4，5,6,7,9,11}{2，3，3，4，5,6,7,9,11,16}{2，3，3，4，5,6,7,9,11,16,27}3哈夫曼編碼一種文本壓縮算法，是根據(jù)符號在一段文字中的相對出現(xiàn)頻率不同，來壓縮編碼。是通信中最經(jīng)典的壓縮編碼symbol（符號）

code（編碼）A010B100C000D111ABACCDA:21bitsymbol（符號）

code（編碼）A00B01C10D11ABACCDA:14bit信息ABACCDA字母B和D只出現(xiàn)過一次，字母A則出現(xiàn)過三次。如果能使字母A的位數(shù)比字母B和字母D的位數(shù)少。整個信息編碼長度將大大地減少.symbol（符號）

co