數據結構與算法樹與二叉樹

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

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

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

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

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

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

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

8、維數組元素增加一個表示雙親結點的域parent，用來指示結點的雙親在一維數組中的位置。這樣查找孩子和雙親就都很方便了。,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,樹的存儲結構,孩子兄弟表示法樹的存儲結構還有一種方法：孩子

9、兄弟表示法。下面我們簡要介紹一下這種方法。這種方法將引出下一個問題：樹與二叉樹的轉化問題。孩子兄弟表示法也是一種鏈式存儲結構。它通過描述每個結點的一個孩子和兄弟信息來反映結點之間的層次關系，其結點結構為：firstchild為指向該結點第一個孩子的指針nextsibling為指向該結點的下一個兄弟item是數據元素內容,樹的存儲結構,孩子兄弟表示法typedef struct CSNode{ EntryType ite

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

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

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

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

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

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

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

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

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

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

20、,11}，構造哈夫曼樹的過程。,練習,,練習,,練習,,7 8,15,58,29,,29,,14,,,,,,,,,,3 5,8,42,23,,19,,11,,,,,,,,,,練習,,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ōu)編碼的思考--編碼的由來在數據通訊中，經常需要將傳送的文字轉換成由二進制字符0，1組成的二進制串，我們稱之為編碼。例如，假設要傳送的電文為ABACCDA，電文中只含有A，B，C，D四種字符，若這四種字符采用下表所示的編碼，則電文的代碼為000010000100100111 000，長度為21。,在傳送電文時，我們總是希望傳送時間盡可能短，這就要求電文代碼盡可能短可以如何

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

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

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

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

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

27、 CAST SAT AT A TASA 字符集合是 { C, A, S, T }，各個字符出現的頻度(次數)是 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,若按各個字符出現的概

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

29、。 總編碼長度正好等于霍夫曼樹的帶權路徑長度WPL。 霍夫曼編碼是一種前綴編碼。解碼時不會混淆。,實驗,實現構造哈夫曼樹的算法根據輸入的n個帶權結點，構造出哈夫曼樹，并且把構造結果輸出到屏幕提示：,哈夫曼樹的存儲結構#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域保存結點的權值，lchild和rchild域分別保存該結點的左、右孩子結點在數組tree[m]中的序號，從而建立起結點之間的關系。,,void HaffmanTree(HNodeType HuffNode [ ]){ /*哈夫曼樹的構造算法*/ int ….. /*申明變量*/ for (i=0;i&

31、lt;2*n-1;i++) /*數組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”,&