數(shù)據(jù)結(jié)構(gòu)與算法樹與二叉樹

1、數(shù)據(jù)結(jié)構(gòu)與算法樹與二叉樹,,趙穎 zhaoying511@126.com 中南大學(xué),，,,在本章前面的內(nèi)容中，我們首先講解了樹的定義，然后就過渡到對二叉樹的講解，包括二叉樹的定義、存儲結(jié)構(gòu)、基本操作（遍歷）等等問題。其實，二叉樹是樹的特例，對于樹，也會有存儲和基本操作。下面我們就來講解樹的相關(guān)問題，包括：樹的存儲結(jié)構(gòu)、樹的基本操作（遍歷）、樹與二叉樹的轉(zhuǎn)化,目錄,樹的存儲結(jié)構(gòu)樹、森林與二叉樹的轉(zhuǎn)化樹的遍歷應(yīng)用舉例：哈夫曼

2、樹,樹的存儲結(jié)構(gòu),雙親表示法在樹中，每個結(jié)點的雙親是唯一的，利用這個性質(zhì)，可以在存儲節(jié)點信息同時，為每個結(jié)點設(shè)置一個指向其雙親的指針，這樣就能唯一的表示一棵樹了。數(shù)據(jù)結(jié)點表示：數(shù)據(jù)元素域，雙親結(jié)點指針域物理存儲方式：順序表或者鏈表（下面用順序表為例，使用一組連續(xù)的存儲單元來存放樹中的結(jié)點）注意：雙親表示法（以及后面講的孩子表示法、雙親孩子表示法）是對樹這種結(jié)構(gòu)的一種邏輯表示法，對應(yīng)于具體的物理存儲方式可以使用順序表也可以使用

3、鏈表，要注意區(qū)分邏輯表示和物理存儲的差別。,樹的存儲結(jié)構(gòu),雙親表示法const MAX_TREE_SIZE = 100; typedef struct { 　　　　　　 // 結(jié)點結(jié)構(gòu)　 ElemType data;　 int parent;　　　　　　　　　// 雙親位置域　} PTNode;typedef struct { 　　　　 //

4、 樹結(jié)構(gòu)　PTNode nodes[MAX_TREE_SIZE];　int r, n;　　　　　　　　 // 根的位置和結(jié)點數(shù)　} PTree;,樹的存儲結(jié)構(gòu),雙親表示法好處：有利用于“向上”查找 (利用結(jié)點雙親的唯一性)。不利：“向下”查找需遍歷全部存儲結(jié)點。,R=0, n=10,樹的存儲結(jié)構(gòu),孩子表示法孩子表示法主要描述的是結(jié)點的孩子關(guān)系。由于每個結(jié)點的孩子個數(shù)不定，所以在每個結(jié)點上設(shè)置多個

5、指向孩子的指針域（稱作多重孩子域）的方式是不合適的。這種方法不但不能確定要設(shè)置多少個指針域，而且會浪費空間。如何表示孩子更好呢？,data,child1,,,,child2,child3,,childd,,,樹的存儲結(jié)構(gòu),孩子表示法為樹中所有結(jié)點建立一個線性表，用一個地址連續(xù)的存儲空間來存儲，數(shù)組中每個元素2個域，一個數(shù)據(jù)域（存放結(jié)點的數(shù)據(jù)），一個指針域（指向該結(jié)點的所有孩子組成的單鏈表的表頭）為每個結(jié)點的所有孩子結(jié)點都建

6、立一個線性表，且以單鏈表作它的存儲結(jié)構(gòu)，單鏈表中每個元素2個域，一個數(shù)據(jù)域（存放該孩子在結(jié)點數(shù)組中的下標(biāo)），一個指針域（指向下一個孩子結(jié)點）。,樹的存儲結(jié)構(gòu),孩子表示法typedef struct CTNode {　 // 孩子結(jié)點 int child; struct CTNode *next;} *ChildPtr;　typedef struct { ElemType data; 　// 結(jié)點的

7、數(shù)據(jù)元素 ChildPtr firstchild; // 孩子鏈表頭指針} CTBox;　　typedef struct { CTBox nodes[MAX_TREE_SIZE]; int n, r; 　　　// 結(jié)點數(shù)和根結(jié)點的位置} CTree;,樹的存儲結(jié)構(gòu),孩子表示法優(yōu)點：尋找某個結(jié)點的孩子比較容易缺點：尋找雙親比較麻煩,樹的存儲結(jié)構(gòu),孩子雙親表示法將雙親表示法和孩子表示法結(jié)合起來，即將一

8、維數(shù)組元素增加一個表示雙親結(jié)點的域parent，用來指示結(jié)點的雙親在一維數(shù)組中的位置。這樣查找孩子和雙親就都很方便了。,A -1,B 0,C 0,D 1,E 1,F 1,G 2,G 3,I 3,J 3,2,3,4,,,8,9,10,,,,5,6,,7,0123456789,,,,parent,樹的存儲結(jié)構(gòu),孩子兄弟表示法樹的存儲結(jié)構(gòu)還有一種方法：孩子

9、兄弟表示法。下面我們簡要介紹一下這種方法。這種方法將引出下一個問題：樹與二叉樹的轉(zhuǎn)化問題。孩子兄弟表示法也是一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。它通過描述每個結(jié)點的一個孩子和兄弟信息來反映結(jié)點之間的層次關(guān)系，其結(jié)點結(jié)構(gòu)為：firstchild為指向該結(jié)點第一個孩子的指針nextsibling為指向該結(jié)點的下一個兄弟item是數(shù)據(jù)元素內(nèi)容,樹的存儲結(jié)構(gòu),孩子兄弟表示法typedef struct CSNode{ EntryType ite

10、m; struct CSNode *firstchild,*nextsibling;}CSNode,*CSTree;,目錄,樹的存儲結(jié)構(gòu)樹、森林與二叉樹的轉(zhuǎn)化樹的遍歷應(yīng)用舉例：哈夫曼樹,樹、森林與二叉樹的轉(zhuǎn)化,在樹或森林與二叉樹之間有一一對應(yīng)關(guān)系任何一個樹可以唯一的轉(zhuǎn)化為一個二叉樹任何一個森林可以唯一的轉(zhuǎn)化為一個二叉樹任何一個二叉樹都可以唯一的轉(zhuǎn)化為一個樹或者森林下面來看：樹轉(zhuǎn)化為二叉樹的方法森林轉(zhuǎn)化為二叉

11、樹的方法二叉樹轉(zhuǎn)化為森林或樹的方法,樹、森林與二叉樹的轉(zhuǎn)化,樹轉(zhuǎn)化為二叉樹的方法將這棵樹用孩子兄弟表示法存儲，此時，樹中的每個結(jié)點最多有兩個指針：一個指針指向第一個孩子，另一個指針指向右側(cè)第一個兄弟。當(dāng)你將這兩個指針看作是二叉樹中的左孩子指針和孩子右指針時，就是一棵二叉樹了。特點：由于樹的根無兄弟，所以二叉樹根結(jié)點無右孩子,樹、森林與二叉樹的轉(zhuǎn)化,森林轉(zhuǎn)化為二叉樹的方法將森林轉(zhuǎn)換成二叉樹的方法與一棵樹轉(zhuǎn)換成二叉樹的方法類似，只是

12、把森林中所有樹的根結(jié)點看作兄弟關(guān)系，并對其中的每棵樹依依地進行轉(zhuǎn)換。,樹、森林與二叉樹的轉(zhuǎn)化,二叉樹轉(zhuǎn)化為森林或樹的方法把二叉樹轉(zhuǎn)換到樹和森林自然的方式是：若結(jié)點x是雙親y的左孩子，則把x的右孩子，右孩子的右孩子，…，都與y用連線連起來，最后去掉所有雙親到右孩子的連線。,練習(xí),把T1，T2，T3，3棵樹轉(zhuǎn)化為3個二叉樹把3棵樹的森林轉(zhuǎn)化為1個二叉樹,練習(xí),,目錄,樹的存儲結(jié)構(gòu)樹、森林與二叉樹的轉(zhuǎn)化樹的遍歷應(yīng)用舉例：哈夫曼樹,

13、樹的遍歷,二叉樹遍歷的分類二叉樹由根結(jié)點、根結(jié)點的左子樹和根結(jié)點的右子樹三部分組成，如果限定先左后右，按照訪問根結(jié)點的順序，那么分先序遍歷、中序遍歷、后序遍歷樹遍歷的分類假設(shè)仍然按照從左到右的遍歷規(guī)則由于一個樹結(jié)點可以有兩顆以上的子樹，所以無法討論樹的中序遍歷。因此按照訪問根結(jié)點的時機，樹的遍歷通常分：先序遍歷和后序遍歷,樹的遍歷,樹的先序遍歷當(dāng)樹非空時1：訪問根結(jié)點2：依次從左到右，先訪問根，遍歷根的各棵子樹,樹先序

14、遍歷 ABEFCDG對應(yīng)二叉樹先序遍歷 ABEFCDG樹的先根遍歷結(jié)果與其對應(yīng)二叉樹表示的前序遍歷結(jié)果相同樹的先根遍歷可以借助對應(yīng)二叉樹的前序遍歷算法實現(xiàn),樹的遍歷,樹的后序遍歷當(dāng)樹非空時1：依次后根遍歷根的各棵子樹2：訪問根結(jié)點,樹后根遍歷 EFBCGDA對應(yīng)二叉樹中序遍歷 EFBCGDA樹的后根遍歷結(jié)果與其對應(yīng)二叉樹表示的中序遍歷結(jié)果相同樹的后根遍歷可以借助對應(yīng)二叉樹的中序遍歷算法實現(xiàn),樹的遍歷,樹的層次遍歷按照

15、層次的順序依次遍歷樹其實二叉樹中也可以使用層次遍歷的方式,遍歷序列：A，B，C，D，E，F(xiàn)，G，H，I，J,目錄,樹的存儲結(jié)構(gòu)樹、森林與二叉樹的轉(zhuǎn)化樹的遍歷應(yīng)用舉例：哈夫曼樹,哈夫曼樹,最優(yōu)二叉樹，也稱哈夫曼（Haffman）樹是指對于一組帶有確定權(quán)值的葉結(jié)點，構(gòu)造的具有最小帶權(quán)路徑長度的二叉樹。為了理解這個概念，需要先看看下面幾個概念什么是樹的路徑與路徑長度？如果一棵樹的一串結(jié)點n1,n2,…,nk有如下關(guān)系：結(jié)

16、點ni是ni+1的父結(jié)點（1≤i<k）,就把n1,n2,…,nk稱為一條由n1至nk的路徑。這條路徑的長度是k-1。 整個樹的路徑長度則是指由根結(jié)點到所有葉結(jié)點的路徑長度之和。,哈夫曼樹,什么是二叉樹的帶權(quán)路徑長度呢？最優(yōu)二叉樹，也稱哈夫曼（Haffman）樹指的是二叉樹，所以我們把定義的目標(biāo)縮小為二叉樹設(shè)二叉樹具有n個帶權(quán)值的葉結(jié)點，那么從根結(jié)點到各個葉結(jié)點的路徑長度與相應(yīng)結(jié)點權(quán)值的乘積之和叫做二叉樹的帶權(quán)路徑長度 ，記作

17、：,Wk為第k個葉結(jié)點的權(quán)值，Lk 為第k個葉結(jié)點的路徑長度,WPL＝2×2＋4×2＋5×2＋3×2＝28,哈夫曼樹,二叉樹的形態(tài)和帶權(quán)路徑長度的關(guān)系在給定一組具有確定權(quán)值的葉結(jié)點，可以構(gòu)造出不同的帶權(quán)二叉樹。例如，給出4個葉結(jié)點，設(shè)其權(quán)值分別為1，3，5，7，我們可以構(gòu)造出形狀不同的多個二叉樹。這些形狀不同的二叉樹的帶權(quán)路徑長度將各不相同。,大家算算，那個二叉樹帶權(quán)路徑長度最短？,,,哈夫

18、曼樹,由此可見，由相同權(quán)值的一組葉子結(jié)點所構(gòu)成的二叉樹有不同的形態(tài)和不同的帶權(quán)路徑長度，那么如何找到帶權(quán)路徑長度最小的二叉樹（即哈夫曼樹）呢？根據(jù)哈夫曼樹的定義，一棵二叉樹要使其WPL值最小，必須使權(quán)值越大的葉結(jié)點越靠近根結(jié)點，而權(quán)值越小的葉結(jié)點越遠(yuǎn)離根結(jié)點。哈夫曼（Haffman）依據(jù)這一特點提出了一種方法。,哈夫曼樹,哈夫曼（Haffman）提出的方法（1）由給定的n個權(quán)值{W1，W2，…，Wn}構(gòu)造n棵只有一個葉結(jié)點的二叉樹

19、，從而得到一個二叉樹的集合F＝{T1，T2，…，Tn}；（2）在F中選取根結(jié)點的權(quán)值最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新的二叉樹根結(jié)點的權(quán)值為其左、右子樹根結(jié)點權(quán)值之和；（3）在集合F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到集合F中；（4）重復(fù)（2）（3）兩步，當(dāng)F中只剩下一棵二叉樹時，這棵二叉樹便是所要建立的哈夫曼樹。,哈夫曼樹,,練習(xí),假設(shè)有一組權(quán)值{5,29,7,8,14,23,3

20、,11}，構(gòu)造哈夫曼樹的過程。,練習(xí),,練習(xí),,練習(xí),,7 8,15,58,29,,29,,14,,,,,,,,,,3 5,8,42,23,,19,,11,,,,,,,,,,練習(xí),,100,7 8,15,58,29,,29,,14,,,,,,,,,,3 5,8,42,23,,19,,11,,,,,,,,,,,,,WPL=(23+29)*2+(11+14)*3+(

21、3+5+7+8)*4=271,哈夫曼樹應(yīng)用—哈夫曼編碼,最優(yōu)編碼的思考--編碼的由來在數(shù)據(jù)通訊中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進制字符0，1組成的二進制串，我們稱之為編碼。例如，假設(shè)要傳送的電文為ABACCDA，電文中只含有A，B，C，D四種字符，若這四種字符采用下表所示的編碼，則電文的代碼為000010000100100111 000，長度為21。,在傳送電文時，我們總是希望傳送時間盡可能短，這就要求電文代碼盡可能短可以如何

22、改進對A、B、C、D的編碼呢？,哈夫曼樹應(yīng)用—哈夫曼編碼,最優(yōu)編碼的思考--等長編碼改進一下電文為ABACCDA，傳送的電文中只有四種字符，只需兩位字符的串便可分辨，對上述電文進行編碼所建立的代碼為00010010101100，長度為14。,剛才2種編碼都是“等長編碼”如果在編碼時考慮字符出現(xiàn)的頻率，讓出現(xiàn)頻率高的字符采用盡可能短的編碼，出現(xiàn)頻率低的字符采用稍長的編碼，構(gòu)造一種不等長編碼，則電文的代碼就可能更短。,哈夫曼樹應(yīng)用—

23、哈夫曼編碼,最優(yōu)編碼的思考--不等長編碼不等長編碼舉例電文為ABACCDA，根據(jù)四個字符A、B、C和D在電文中出現(xiàn)的頻率為它們設(shè)計的編碼分別為0、00、1和01，則上述七個字符的電文可轉(zhuǎn)換成總長為9的字符串“000011010”。問題是，這樣對嗎？為什么？這樣的編碼產(chǎn)生一個新的問題，即如何反譯成原文，編碼存在多義性。例如上述字符串中前四個字符的子串“0000”就可有多種譯法，或“AAAA”，或是“ABA”，也可以是“BB”等

24、在建立不等長編碼時，必須使任何一個字符的編碼都不是另一個字符編碼的前綴,哈夫曼樹應(yīng)用—哈夫曼編碼,最優(yōu)的不等長編碼的2大問題問題一：根據(jù)電文字符出現(xiàn)頻率，要求構(gòu)造使電文的編碼總長最短的不等長編碼方案問題二：必須使任何一個字符的編碼都不是另一個字符編碼的前綴 哈夫曼樹能幫助我們建立最合理的不等長編碼哈夫曼樹能解決這2個問題為什么呢？？？？,哈夫曼樹應(yīng)用—哈夫曼編碼,哈夫曼樹解決問題一的理由在哈夫曼編碼樹中，樹的帶權(quán)路徑長度的

25、含義是各個字符的碼長與其出現(xiàn)次數(shù)的乘積之和，也就是電文的代碼總長，所以采用哈夫曼樹構(gòu)造的編碼是一種能使電文代碼總長最短的不等長編碼。哈夫曼樹解決問題二的理由采用哈夫曼樹進行編碼，則不會產(chǎn)生上述二義性問題。因為，在哈夫曼樹中，每個字符結(jié)點都是葉結(jié)點，它們不可能在根結(jié)點到其它字符結(jié)點的路徑上，所以一個字符的哈夫曼編碼不可能是另一個字符的哈夫曼編碼的前綴，從而保證了譯碼的非二義性。,哈夫曼樹應(yīng)用—哈夫曼編碼,哈夫曼編碼的方法（1）利用字

26、符集中每個字符的使用頻率作為權(quán)值構(gòu)造一個哈夫曼樹；（2）從根結(jié)點開始，為到每個葉子結(jié)點路徑上的左分支賦予0，右分支賦予1，并從根到葉子方向形成該葉子結(jié)點的編碼。,設(shè)給出一段報文： CAST CAST SAT AT A TASA字符集合是 { C, A, S, T }，（不包括空格）各個字符出現(xiàn)的頻度(次數(shù))是 W＝{ 2, 7, 4, 5 }。試試看如何編碼？,設(shè)給出一段報文： CAST

27、 CAST SAT AT A TASA 字符集合是 { C, A, S, T }，各個字符出現(xiàn)的頻度(次數(shù))是 W＝{ 2, 7, 4, 5 }。 若給每個字符以等長編碼 A : 00 T : 10 C : 01 S : 11則總編碼長度為 ( 2+7+4+5 ) * 2 = 36.,,,,,,,,,7,,,,2,5,4,0,1,0,0,1,1,若按各個字符出現(xiàn)的概

28、率不同而給予不等長編碼，可望減少總編碼長度。 各字符出現(xiàn)概率為{ 2/18, 7/18, 4/18, 5/18 },化整為 { 2, 7, 4, 5 }。以它們?yōu)楦魅~結(jié)點上的權(quán)值, 建立霍夫曼樹。左分支賦 0，右分支賦 1，得霍夫曼編碼(變長編碼)。,霍夫曼編碼樹,A : 0 T : 10 C : 110 S : 111它的總編碼長度：7*1+5*2+( 2+4 )*3 = 35。比等長編碼的情形要短

29、。 總編碼長度正好等于霍夫曼樹的帶權(quán)路徑長度WPL。 霍夫曼編碼是一種前綴編碼。解碼時不會混淆。,實驗,實現(xiàn)構(gòu)造哈夫曼樹的算法根據(jù)輸入的n個帶權(quán)結(jié)點，構(gòu)造出哈夫曼樹，并且把構(gòu)造結(jié)果輸出到屏幕提示：,哈夫曼樹的存儲結(jié)構(gòu)#define n 7#define m 2*n-1typedef int datatype;typedef struct{ float weight; int lcjild,rch

30、ild,parent;} hufmtree;hufmtree tree[m];,weight域保存結(jié)點的權(quán)值，lchild和rchild域分別保存該結(jié)點的左、右孩子結(jié)點在數(shù)組tree[m]中的序號，從而建立起結(jié)點之間的關(guān)系。,,void HaffmanTree(HNodeType HuffNode [ ]){ /*哈夫曼樹的構(gòu)造算法*/ int ….. /*申明變量*/ for (i=0;i&

31、lt;2*n-1;i++) /*數(shù)組HuffNode[ ]初始化*/ { HuffNode[i].weight=0; HuffNode[i].parent=-1; HuffNode[i].lchild=-1; HuffNode[i].rchild=-1; } for (i=0;i<n;i++) scanf(“%d”,&