數(shù)據(jù)結(jié)構(gòu)樹的定義和基本術(shù)語課件

1、1、樹的定義和基本術(shù)語 基本概念樹：n o 個(gè)結(jié)點(diǎn)的集合，根、其余結(jié)點(diǎn)分為 m = 0 個(gè)集合，每一個(gè)集合本身又是一棵樹（子樹）度、葉子、父結(jié)點(diǎn)、兒子結(jié)點(diǎn)、祖先結(jié)點(diǎn)、層次、深度（或高度）有序樹及無序樹森林 m = 0 棵互不相交樹的集合其它表示方法： ( A(B(L,E),C(F),D(G(I),H)書上還介紹了兩種，請(qǐng)參考。ABCDEFGHILE、G：高度為 4 、度為 3 的樹(有的書稱之為 3 次樹)2、二叉樹2、性質(zhì)：性質(zhì)1：在二叉樹的第 i 層上至多有 2 i-1個(gè)結(jié)點(diǎn)BCDEFLA1層：結(jié)點(diǎn)個(gè)數(shù) 21-1=20 個(gè)2層：結(jié)點(diǎn)個(gè)數(shù) 22-1=21 個(gè)3層：結(jié)點(diǎn)個(gè)數(shù) 23-1=22 個(gè)

2、性質(zhì)2：深度為 K 的二叉樹至多有2 k- 1 個(gè)結(jié)點(diǎn)性質(zhì)3：二叉樹的葉子結(jié)點(diǎn)數(shù) n0 等于度為 2 的結(jié)點(diǎn)數(shù)n2 + 1 CEFLA1、定義空或有一個(gè)根，根有左子樹、右子樹；而左右子樹本身又是二叉樹。和樹的區(qū)別：可為空，左右子樹有序，不可顛倒。性質(zhì)4：具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2n + 12、二叉樹BCDEFLAPSQRUBCDEFLAPSQRXUWV滿二叉樹:每層結(jié)點(diǎn)數(shù)最多完全二叉樹: 滿二叉樹 或 從滿二叉樹最底層從右向左 依次去掉若干結(jié)點(diǎn)形成的2、二叉樹BCDEFLAPSQRU性質(zhì)5：對(duì)一棵有 n 個(gè)結(jié)點(diǎn)的完全二叉樹按照從第一層（根所在的層次到最后一層，并且 每一層都

3、按照從左到右的次序進(jìn)行編號(hào)。根結(jié)點(diǎn)的編號(hào)為 1，最后一個(gè)結(jié)點(diǎn)的編號(hào) 為 n。 1：對(duì)任何一個(gè)編號(hào)為 i 的結(jié)點(diǎn)而言，它的左兒子的編號(hào)為 2i( 若 2i = n) ,而右兒子的 編號(hào)為 2i+1(若 2i +1 = n)。 2：對(duì)任何一個(gè)編號(hào)為 j 的結(jié)點(diǎn)而言，它的父親結(jié)點(diǎn)的的編號(hào)為 j/2 。根結(jié)點(diǎn)無父結(jié) 點(diǎn)。1211109876543212、二叉樹3、二叉樹的存儲(chǔ)結(jié)構(gòu)： 順序存儲(chǔ)結(jié)構(gòu)： 一般情況：ABCDEFGHIL# define MAX_SIZE 10typedef struct BiTNode TELemType data; int lchild; int rchild; BitTN

4、ode;typdef BitTNode SqBiTreeMAX_SIZE; SqBiTree bt; A 1 -1 B 9 2 C 5 3 D 6 -1 E -1 -1 F -1 -1 G 8 7 H -1 -1I -1 -1L -1 4 0123456789rchild lchilddata 應(yīng)用范圍：適用于二叉樹上的結(jié)點(diǎn)個(gè)數(shù)已知，或不支持動(dòng)態(tài)存儲(chǔ)分配的高級(jí)語言。2、二叉樹3、二叉樹的存儲(chǔ)結(jié)構(gòu)： 順序存儲(chǔ)結(jié)構(gòu)： 特殊情況：# define MAX_SIZE 11typedef struct BiTNode TELemType data; int lchild; int rchild; Bit

5、TNode;typedef BitTNode SqBiTreeMAX_SIZE; SqBiTree bt; A 2 3 B 4 5 C 6 7 D 8 9 E 10 0 F 0 0 G 0 0 H 0 0I 0 0L 0 0012345678910rchild lchilddata 應(yīng)用范圍：適用于完全二叉樹，且結(jié)點(diǎn)個(gè)數(shù)已知。DCGEFBAHIL2、二叉樹3、二叉樹的存儲(chǔ)結(jié)構(gòu)： 順序存儲(chǔ)結(jié)構(gòu)： 特殊情況：若不是完全二叉樹，許多數(shù)據(jù)場(chǎng)為空，不合算。如下例所示：# define MAX_SIZE 10typedef TELemType SqBiTreeMAX_SIZE; SqBiTree bt;

6、A B HI 0123456789DBAHI2、二叉樹3、二叉樹的存儲(chǔ)結(jié)構(gòu)： 鏈接存儲(chǔ)結(jié)構(gòu)： 僅定義結(jié)點(diǎn)的類型即可。ABCDEFGHILtypedef struct BiTNode TELemType data; struct BiTNode * lchild; struct BiTNode * rchild; BitTNode, * BiTree;BiTree p; data lchild rchild標(biāo)準(zhǔn)形式：（二叉鏈表）data lchild rchild parenttypedef struct BiTNode TELemType data; struct BiTNode * lchi

7、ld; struct BiTNode * rchild; struct BiTNode * parent; BitTNode, * BiTree;BiTree p; 廣義標(biāo)準(zhǔn)形式：（三叉鏈表）3、遍歷二叉樹和線索二叉樹BCDELAXW1、遍歷二叉樹：設(shè) N 代表根節(jié)點(diǎn)，L 代表左子樹，R 代表右子樹。 a. 前序分析：結(jié)點(diǎn)的左兒子、左孫子、左后代、 將連續(xù)輸出。結(jié)點(diǎn)的右兒子將在結(jié)點(diǎn)、結(jié)點(diǎn)的左 NLR 子樹全部輸出之后才輸出。 b. 中序分析：最先輸出的結(jié)點(diǎn)是根結(jié)點(diǎn)的最左的左后代。將二叉樹中的結(jié)點(diǎn)投影到水平軸線上，則得到 LNR 中序遍歷的序列。 c. 后序分析：根結(jié)點(diǎn)（或子樹的根結(jié)點(diǎn)）將在它的

8、左、右子樹的結(jié)點(diǎn)輸出之后。因此，根結(jié)點(diǎn)（或子樹 LRN 的根結(jié)點(diǎn)）在中序序列中的序號(hào)等于它的左右子樹的結(jié)點(diǎn)個(gè)數(shù) 左右子樹中的最先被訪 問的結(jié)點(diǎn)的序號(hào)。注意，結(jié)點(diǎn)、右父親、右祖父、 將連續(xù)輸出。前序：A、L、B、E、C、D、W、X中序：B、L、E、A、C、W、X、D后序：B、E、L、X、W、D、C、ABCDELAXWB L E A C W X D3、遍歷二叉樹和線索二叉樹BCDELA1、遍歷二叉樹：續(xù)前序的程序?qū)崿F(xiàn)：1、根結(jié)點(diǎn)進(jìn)棧2、結(jié)點(diǎn)出棧，被訪問3、結(jié)點(diǎn)的右、左兒子（非空）進(jìn)棧4、反復(fù)執(zhí)行 2、3 ，至?？諡橹埂Ｇ靶颍篈、L、B、E、C、De.g:A出棧訪問L出棧訪問B出棧訪問E出棧訪問C出

9、棧訪問D出棧訪問后，棧空結(jié)束A進(jìn)棧C、L進(jìn)棧E、B進(jìn)棧D進(jìn)棧3、遍歷二叉樹和線索二叉樹1、遍歷二叉樹：續(xù)中序的程序?qū)崿F(xiàn)：1、結(jié)點(diǎn)（初始時(shí)是根結(jié)點(diǎn)）進(jìn)棧，沿左指針查找左兒子。2、若有左兒子，返回第一步。3、若無左兒子，判?？?？空則結(jié)束。非空，棧頂結(jié)點(diǎn)出棧 訪問。轉(zhuǎn)向右子樹，返回1。e.g:BCDELAXW中序：B、L、E、 A、C、W、 X、Dinitstack(s);push(s,t); / t 是根結(jié)點(diǎn)while (!stackempty(s) while (Gettop(s,p) & p ) / 有值且非空時(shí) push(s, p-lchild)； / null 值可能進(jìn)棧 pop (s,p

10、); / 空指針退棧 if (!stackempty(s) / 訪問結(jié)點(diǎn)，向右一步 pop(s, p); visit( p-data); push(s,p-rchild); 3、遍歷二叉樹和線索二叉樹1、遍歷二叉樹：設(shè)根結(jié)點(diǎn)初始時(shí)非空后序算法：1、結(jié)點(diǎn)（初始時(shí)為根）進(jìn)棧（正值），沿左指針查找左兒子 2、左兒子非空，返回1。 3、退棧。若為正值轉(zhuǎn) 4 ，否則轉(zhuǎn) 5。 4、負(fù)值進(jìn)棧轉(zhuǎn)向右子樹，如右兒子非空，則轉(zhuǎn)向 1；空轉(zhuǎn)向 3。 5、訪問結(jié)點(diǎn)（應(yīng)恢復(fù)正值），返回 3 6、反復(fù) 1 到 5 ，至?？諡橹?。 e.g:BCDELAXWinitstack(s); p = t; / t 是根結(jié)點(diǎn)的地址，如

11、圖為下標(biāo)1do while ( p != 0 ) / 有值且非空時(shí) push(s, p)；p = nodep.lchild; if (!stackempty(s) pop(s, p); if ( p 0 ) push(s, -p); p = nodep.rchild; ; else p= - p; visit( nodep.data ); p = 0; while ( !stackempty(s) )后序：B、E、L、X、 W、D、C、A0123Lchild dada rchildnode數(shù)組AL3245C06/ 結(jié)點(diǎn)p輸出之后，必須找到其父結(jié)點(diǎn)(在棧頂)，故 p=0 跳過while循環(huán)。ED

12、00W0845678BX00000703、遍歷二叉樹和線索二叉樹1、線索二叉樹：為什么采用線索二叉樹：二叉樹中的空指針場(chǎng)多達(dá) n + 1 個(gè)。簡(jiǎn)單證明：設(shè)二叉樹中結(jié)點(diǎn)的總數(shù)為 n，度為 2 的結(jié)點(diǎn)總數(shù)為 n2 ?？罩羔槇?chǎng)用方框代表。增加了方 框結(jié)點(diǎn)的二叉樹稱之為擴(kuò)展二叉樹。在該二叉樹之中，原來的 n 個(gè)結(jié)點(diǎn)全部成為度為 2 的結(jié) 點(diǎn)，方框結(jié)點(diǎn)成為葉子。根據(jù)二叉樹的性質(zhì) 3 ，原命題得證。e.g: n = 8 的二叉樹BCDELAXWBCDELAXW擴(kuò)展二叉樹怎樣利用這 n + 1 個(gè)空指針場(chǎng)？中序穿線樹后序穿線樹3、遍歷二叉樹和線索二叉樹1、線索二叉樹：中序穿線樹（中序線索二叉樹）的實(shí)現(xiàn)：在二

13、叉樹的結(jié)點(diǎn)的標(biāo)準(zhǔn)形式中，增加兩個(gè)標(biāo)志域，用于區(qū)別是否是穿線。如下所 示：其中 data 為數(shù)據(jù)場(chǎng)，ltag = 0 時(shí)，lchild 場(chǎng)指向本結(jié)點(diǎn)的真正的左兒子 ltag = 1 時(shí)，lchild 場(chǎng)指向本結(jié)點(diǎn)的按中序遍歷序列的前驅(qū)結(jié)點(diǎn)(穿線) rtag = 0 時(shí)，rchild 場(chǎng)指向本結(jié)點(diǎn)的真正的右兒子 rtag = 1 時(shí)，rchild 場(chǎng)指向本結(jié)點(diǎn)的按中序遍歷序列的后繼結(jié)點(diǎn)(穿線) e.g: n = 6 的二叉樹BCDELA中序穿線樹Lchild ltag data rtag rchild BCDELA無前驅(qū)結(jié)點(diǎn)無后繼結(jié)點(diǎn)3、遍歷二叉樹和線索二叉樹1、線索二叉樹：中序穿線樹中的結(jié)點(diǎn)的數(shù)

14、據(jù)結(jié)構(gòu)：BCDELA無前驅(qū)結(jié)點(diǎn)無后繼結(jié)點(diǎn)00000011111111ALBECD新增頭結(jié)點(diǎn)表示1:穿線0:實(shí)際兒子3、遍歷二叉樹和線索二叉樹1、線索二叉樹：在中序穿線樹上進(jìn)行中序遍歷、不用堆棧的的算法及程序要點(diǎn)：1、最先輸出最左的結(jié)點(diǎn)2、結(jié)點(diǎn)無右后件，則該結(jié)點(diǎn)的中序的后繼結(jié)點(diǎn)，由右兒子的指針場(chǎng)給出。但要注意以下情況：BCDELA無前驅(qū)結(jié)點(diǎn)無后繼結(jié)點(diǎn)3、結(jié)點(diǎn)有右兒子，則該結(jié)點(diǎn)的中序的后繼結(jié)點(diǎn)，是它的右子樹中的最左的結(jié)點(diǎn)。4、最先輸出的結(jié)點(diǎn)無前驅(qū)結(jié)點(diǎn)，最后輸出的結(jié)點(diǎn)無后繼結(jié)點(diǎn)。BDELA指向當(dāng)前結(jié)點(diǎn)指向后繼結(jié)點(diǎn)3、遍歷二叉樹和線索二叉樹1、線索二叉樹：在中序穿線樹上進(jìn)行中序遍歷、不用堆棧的程序?qū)崿F(xiàn)

15、Status inorderTraverse_Thr(BiThrTree T, status( * Visit ) (TElemType e ) ) p = T- lchild; while ( P != T ) while ( p-Ltag = Link ) p = p-lchid; / Link 表示有實(shí)在的兒子 Visit ( p- data); while ( p-rtag = Thread & p-rchid != T ) p = p-rchid ; Visit ( p- data) ; p = p-rchid ; return OK;指向當(dāng)前結(jié)點(diǎn)指向后繼結(jié)點(diǎn)BDELA/ 注意：p

16、是根結(jié)點(diǎn)的地址，T 為頭結(jié)點(diǎn)地址BCDELA無前驅(qū)結(jié)點(diǎn)無后繼結(jié)點(diǎn)01新增頭結(jié)點(diǎn)T4、樹和森林1、樹的存儲(chǔ)結(jié)構(gòu)標(biāo)準(zhǔn)形式：樹中的每個(gè)結(jié)點(diǎn)除有數(shù)據(jù)場(chǎng)之外，還有 K 個(gè)指針場(chǎng)；其中 K 為樹的度數(shù)。1、數(shù)據(jù)場(chǎng)第一個(gè)兒子結(jié)點(diǎn)的地址第二個(gè)兒子結(jié)點(diǎn)的地址第 K 個(gè)兒子結(jié)點(diǎn)的地址父親結(jié)點(diǎn)的地址廣義標(biāo)準(zhǔn)形式：在標(biāo)準(zhǔn)形式的基礎(chǔ)上，再增加指向父親結(jié)點(diǎn)的指針場(chǎng)。 E.g: 度數(shù) K 3 的樹ABCDEFGHILA 1 2 3 -1B 9 4 -1 0C 5 -1 -1 0D 6 7 -1 0E -1 -1 -1 1F -1 -1 -1 2G 8 -1 -1 3H -1 -1 -1 3I -1 -1 -1 6P -1

17、-1 -1 -1 0123456789-1 表示空缺點(diǎn)：空指針場(chǎng)太多，多達(dá) ( K -1 ) n + 1 個(gè)。改進(jìn)：結(jié)點(diǎn)中設(shè)立度數(shù)場(chǎng)， 指針場(chǎng)依度數(shù)定。但 操作麻煩。 采用左兒子、兄弟表 示法。用數(shù)組表示左圖的樹 4、樹和森林1、樹的存儲(chǔ)結(jié)構(gòu)左兒子、兄弟表示法：樹中的每個(gè)結(jié)點(diǎn)有數(shù)據(jù)場(chǎng)、指向它的第一棵子樹樹根的指針場(chǎng)、指向它的兄弟結(jié)點(diǎn)的指針場(chǎng)。實(shí)質(zhì)上是用二叉樹表示一棵樹。數(shù)據(jù)場(chǎng)第一棵子樹根結(jié)點(diǎn)的地址下一個(gè)親兄弟結(jié)點(diǎn)的地址 E.g: 度數(shù) K 3 的樹ABCDEFGHIL A B C D E F G H L I 4、樹和森林2、樹、森林于二叉樹的轉(zhuǎn)換樹轉(zhuǎn)換成相對(duì)應(yīng)的二叉樹：1、保留每個(gè)結(jié)點(diǎn)的最左面

18、的分支，其余分支都被刪除。2、同一父結(jié)點(diǎn)下面的結(jié)點(diǎn)成為它的左方結(jié)點(diǎn)的兄弟。 E.g: 度數(shù) K 3 的樹ABCDEFGHILABCDEFGHILABCDEFGHIL4、樹和森林2、樹、森林于二叉樹的轉(zhuǎn)換森林轉(zhuǎn)換成相對(duì)應(yīng)的二叉樹：增加一個(gè)虛擬的根結(jié)點(diǎn)，它的兒子為各棵樹的根。那么，就變成了樹轉(zhuǎn)換成二叉樹的問題。 E.g: 3 棵分別以B、 C、D為根的樹BCDEFGHILBCDEFGHILABCDEFGHILA 相應(yīng)的二叉樹4、樹和森林2、樹、森林于二叉樹的轉(zhuǎn)換森林轉(zhuǎn)換成相對(duì)應(yīng)的二叉樹：增加一個(gè)虛擬的根結(jié)點(diǎn)，它的兒子為各棵樹的根。那么，就變成了樹轉(zhuǎn)換成二叉樹的問題。 E.g: 3 棵分別以B、 C

19、、D為根的樹BCDEFGHILBCDEFGHILABCDEFGHIL 相應(yīng)的二叉樹4、樹和森林3、樹、森林的遍歷樹的前序、后序遍歷：1、類似于二叉樹的前序遍歷：NLR；N:根；L：左子樹（第一棵子樹）， R：其余的那些子樹，遍歷方向由第二棵子樹至最后一棵子樹2、類似于二叉樹的后序遍歷：LRN：L：左子樹（第一棵子樹），R：其 余的那些子樹，遍歷方向由第二棵子樹至最后一棵子樹， N:根NBCDEFGHILA T1 T2 T3LR前序：A、B、L、E、C、F、D、G、I、H后序：L、E、B、F、C、I、G、H、D、A4、樹和森林3、樹、森林的遍歷森林的前序、中序遍歷：前序遍歷類似于樹的前序遍歷。增

20、加一個(gè)虛擬的根結(jié)點(diǎn)，它的兒子為各棵樹的根。那么對(duì)這棵樹進(jìn)行前序遍歷，即得到森林的前序序列（不含樹根結(jié)點(diǎn)）中序遍歷類似于樹的后序遍歷。增加一個(gè)虛擬的根結(jié)點(diǎn)，它的兒子為各棵樹的根。那么對(duì)這棵樹進(jìn)行后序遍歷，即得到森林的中序遍歷（去掉樹根結(jié)點(diǎn)） 注意：在森林中通常稱為中序遍歷, 如稱之為后序遍歷更合理(和樹一致)。前序：B、L、E、C、F、D、G、I、H中序：L、E、B、F、C、I、G、H、DBCDEFGHILABCDEFGHIL4、樹和森林3、樹、森林的遍歷樹的前序、后序遍歷序列和相應(yīng)的二叉樹的前序、中序遍歷序列一一對(duì)應(yīng)：前序序列和對(duì)應(yīng)的二叉樹的前序序列完全一致。E、G：左圖的樹的根 A，及它的兒

21、子結(jié)點(diǎn) B、C、D 在樹的 的前序序列和相應(yīng)的二叉樹中前序序列中的序號(hào)。 根 A: 11 結(jié)點(diǎn) B： 22 結(jié)點(diǎn) C： 55 結(jié)點(diǎn) D： 77BCDEFGHILAABCDEFGHIL以 C 為例：在樹中： 序號(hào) 根節(jié)點(diǎn)數(shù) 第一棵子樹的結(jié)點(diǎn)數(shù) 1 5在二叉樹中： 序號(hào) 根節(jié)點(diǎn)數(shù) 左兒子數(shù)左兒子子樹結(jié)點(diǎn)數(shù) 1 54、樹和森林3、樹、森林的遍歷樹的前序、后序遍歷序列和相應(yīng)的二叉樹的前序、中序遍歷序列一一對(duì)應(yīng)：后序序列和對(duì)應(yīng)的二叉樹的中序序列完全一致。E、G：左圖的樹的根 A，及它的兒子結(jié)點(diǎn) B、C、D 在樹的 的后序序列和相應(yīng)的二叉樹的中序序列中的序號(hào)。 根 A: 1010 結(jié)點(diǎn) B： 33 結(jié)點(diǎn)

22、C： 55 結(jié)點(diǎn) D： 99BCDEFGHILAABCDEFGHIL后序：L、E、B、F、C、I、G、H、D、A以 C 為例：在樹中： 序號(hào) 第一棵子樹的結(jié)點(diǎn)數(shù) C 的子樹的結(jié)點(diǎn)數(shù) 1 5在二叉樹中： 序號(hào) B 的左子樹的結(jié)點(diǎn)數(shù) B 的結(jié)點(diǎn)數(shù) C 的左子樹結(jié)點(diǎn)數(shù) 1 5中序：L、E、B、F、C、I、G、H、D、A4、樹和森林3、樹、森林的遍歷森林的前序、中序（當(dāng)作后序更好理解）和相應(yīng)的二叉樹的前序、中序遍歷序列一一對(duì)應(yīng) E.g: 3 棵分別以B、 C、D為根的樹BCDEFGHILBCDEFGHILABCDEFGHILA 相應(yīng)的二叉樹6、赫夫曼樹及其應(yīng)用1、最優(yōu)二叉樹（赫夫曼樹） 路徑長(zhǎng)度：結(jié)點(diǎn)

23、之間的樹枝的總數(shù)樹的路徑長(zhǎng)度：從根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和樹的帶權(quán)路徑長(zhǎng)度：葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。設(shè)有 n 片葉子，它們的權(quán)值分別 為 w1、w2、.wn， 相應(yīng)的路徑長(zhǎng)度分別為 L1、L2、.Ln。 則樹的帶權(quán)路徑長(zhǎng)度可記為： nWPL = wklk k=1EGHLLEHGEGHL777524442255WPL=36WPL=46WPL=35最優(yōu)二叉樹或赫夫曼樹：樹的帶權(quán)路徑長(zhǎng)度 WPL 最小的二叉樹。6、赫夫曼樹及其應(yīng)用1、最優(yōu)二叉樹（赫夫曼樹） 赫夫曼算法（產(chǎn)生最優(yōu)二叉樹的算法）的實(shí)現(xiàn)：1、給定一個(gè)具有 n 個(gè)權(quán)值 w1,w2,wn 的結(jié)點(diǎn)的集合 F = T1,T2,Tn 。2、初始

24、時(shí)，設(shè) A F。3、執(zhí)行 i = 1 至 n-1 次循環(huán)，在每次循環(huán)時(shí)，做以下事情：從當(dāng)前集合中選取權(quán)值最小、次最小的兩個(gè)結(jié)點(diǎn)，以 這兩個(gè)結(jié)點(diǎn)作為內(nèi)部結(jié) 點(diǎn) bi 的左右兒子，bi 的權(quán)值為其左右兒子權(quán)值之和。在集合中刪除這兩個(gè)權(quán) 值最小、次最小的結(jié)點(diǎn)。這樣，在集合 A 中，結(jié)點(diǎn)個(gè)數(shù)便減少了一個(gè)。 e.g: 權(quán)值（此處為使用概率）分別為 2, 7, 4, 5 的結(jié)點(diǎn)集合 F C, A, S, T 已知。 請(qǐng)利用赫夫曼算法產(chǎn)生最優(yōu)二叉樹。C, 2A, 7S, 4T, 51、A=b1,6A, 7T, 5S, 4C, 22、A=b1,6A, 7S, 4C, 2b2,11 T, 53、A=b3,184

25、、A=6、赫夫曼樹及其應(yīng)用2、赫夫曼編碼 赫夫曼算法用于通信中的字符的編碼。將權(quán)值當(dāng)著使用概率。赫夫曼樹的左分支 標(biāo)記為 1，而右分枝標(biāo)記為 0；這從根到每一個(gè)葉子結(jié)點(diǎn)（字符）的路經(jīng)上標(biāo)記的字符組成的字 符串，即為該字符的赫夫曼編碼。 e.g: 權(quán)值（此處為使用概率）分別為 2, 7, 4, 5 的結(jié)點(diǎn)集合 F C, A, S, T 已知。 請(qǐng)利用赫夫曼算法產(chǎn)生最優(yōu)二叉樹。b1,6A, 7S, 4C, 2b2,11T, 5b3,18111000赫夫曼編碼：A：0T：10C：110S ：111赫夫曼編碼優(yōu)點(diǎn)： 占用二進(jìn)制位少e.g: 左圖發(fā)送長(zhǎng)度為 n 的字符串，等長(zhǎng)表示需 2n 個(gè)比特。因共有

26、四個(gè)字符，表示每個(gè)字符需 二個(gè) 比特。 采用赫夫曼編碼后，總的比特?cái)?shù) 35n/18, 因： A：1*7n /18 T： 2*5n /18 S： 3*4n /18 C：3*2n /18 7、回溯法與樹的遍歷1、回溯法簡(jiǎn)介：求最優(yōu)解、全部解答、一組解答的常用辦法，也 可用窮舉法求解。窮舉法：羅列所有可能性，得出解答?？赡芤?指數(shù)爆炸問題。 回溯法：搜索、試探、回溯；類似于樹的前序周 游。用約束函數(shù)削減結(jié)點(diǎn)。2、回溯法的形式描述：解表示成 n 元組（x1,x2,xn）的形式， xi 取自 初值集合 si 先構(gòu)造部分向量 （x1,x2,xi）, 一旦發(fā)現(xiàn)該向量 不合要求，則不必考慮（xi+1 , ,

27、xi+2, xn）； 削減結(jié)點(diǎn)，提高效率。用約束函數(shù)判斷是否合乎要求，滿足約束函數(shù)可 繼續(xù)構(gòu)造下去（即：xi+1 , ,xi+2, xn）；反之 ，則不必再構(gòu)造（被剪枝）。約束函數(shù)：顯約束：xi 的取值范圍 隱約束：各 xi 之間的關(guān)系。 e.g：四后問題：在 4 行 4 列的國(guó)際象棋棋 盤上尋找所有互不相互攻擊的四個(gè)皇 后的位置。 解：設(shè)解向量為 x1 ,x2 , x3 ,x4 ；且下標(biāo) i 代表該皇后所在的行數(shù)，xi 代表所在 的列數(shù)。 顯約束：xi ：1、2、3、4 隱約束： xi != xk /列數(shù)不等 i != k /行數(shù)不等 xi - i != xk - k /不可同在主 / 對(duì)角

28、線上 xi + i != xk + k /不可同在次 / 對(duì)角線上7、回溯法與樹的遍歷皇后皇后皇后皇后皇后皇后皇后皇后 i = k /行數(shù)等xi = xk /列數(shù)等 xi - i = xk - k / 同在主/ 對(duì)角線上xi + i = xk + k /同在次 / 對(duì)角線上3、皇后相互攻擊的情況分析：7、回溯法與樹的遍歷4、皇后相互攻擊的情況分析：Void nqueen( int n); / 求解 n 后問題的所有解 x( 1) = 0 ; k = 1 ; / 第 k 個(gè)皇后被放置在第 k 行， x( k ) 列 while ( k 0 ) x( k ) = x( k ) + 1; / 考察下

29、一列 while ( (x( k ) = n ) & （ (k 行、 x(k)列的皇后同 ( 1 行、 x(1)列)， ( 2行、 x(2)列)，( k-1行、 x(k-1)列的皇后沖突時(shí) ) / 用約束函數(shù) x( k ) = x( k ) + 1 ； / 移到下一列 if (x( k ) = n ) / 發(fā)現(xiàn)一個(gè)新的可放位置 (k 行、 x(k) 列if ( k =n ) PRINT ( 1、 x(1)，( 2、x(2) 至 ( n、x(n ); / 一個(gè)解，得到n個(gè)后的位置else k = k + 1; x( k ) = 0 ； / 在下一行尋找合適行、列放置皇后 else k = k-1

30、; / 回溯，回退一行 7、回溯法與樹的遍歷4、四皇后問題解答樹的遍歷過程： e.g: 在 （1行 、1列）的皇后的遍歷過程(1、1)(2、1)(2、2)(2、3)(2、4)(3、1)(3、2)(3、3)(3、4)(4、1)(4、2)(4、3)(4、4)(3、1)(3、2)(3、3)(3、4)皇后皇后皇后8、樹的計(jì)數(shù)1、二叉樹的確定 前序（后序） 中序 唯一確定一棵二叉樹 e.g: 前序: A、B、D、E、F、C 中序: D、B、E、F、A、C確定過程: 1、 定根 A 2、在中序序列中找到 A 3、中序序列中的 A 的左部為 A 的左子樹 上的所有結(jié)點(diǎn)， A 的右部為 A 的右子 樹中的所有

31、結(jié)點(diǎn)。 4、根據(jù) A 的左子樹的所有結(jié)點(diǎn)的前序序 列確定 A 的左子樹的根節(jié)點(diǎn)，它是 A 的左兒子。 5、根據(jù) A 的右子樹的所有結(jié)點(diǎn)的前序序 列確定 A 的右子樹的根節(jié)點(diǎn)，它是 A 的右兒子。 6、 在左、右子樹中反復(fù)以上過程。至所有 結(jié)點(diǎn)處理完畢。結(jié)束 前序: A、B、D、E、F、C 中序: D、B、E、F、A、C 前序: A、B、D、E、F、C 中序: D、B、E、F、A、C 前序: B、D、E、F 中序: D、B、E、F 前序: E、F 中序: E、FA D、B、E、F CA D、E、FCBABCD E、F8、樹的計(jì)數(shù)1、二叉樹的確定 前序（后序） 中序 唯一確定一棵二叉樹 e.g:

32、前序: A、B、D、E、F、C 中序: D、B、E、F、A、C確定過程: 1、 定根 A 2、在中序序列中找到 A 3、中序序列中的 A 的左部為 A 的左子樹 上的所有結(jié)點(diǎn)， A 的右部為 A 的右子 樹中的所有結(jié)點(diǎn)。 4、根據(jù) A 的左子樹的所有結(jié)點(diǎn)的前序序 列確定 A 的左子樹的根節(jié)點(diǎn)，它是 A 的左兒子。 5、根據(jù) A 的右子樹的所有結(jié)點(diǎn)的前序序 列確定 A 的右子樹的根節(jié)點(diǎn)，它是 A 的右兒子。 6、 在左、右子樹中反復(fù)以上過程。至所有 結(jié)點(diǎn)處理完畢。結(jié)束 前序: A、B、D、E、F、C 中序: D、B、E、F、A、C 前序: A、B、D、E、F、C 中序: D、B、E、F、A、CE

33、F 前序: B、D、E、F 中序: D、B、E、F 前序: E、F 中序: E、FA D、B、E、F CA D、E、FCBABCD8、樹的計(jì)數(shù)1、互不相似的二叉樹的棵數(shù)的計(jì)算 計(jì)算要點(diǎn): 設(shè)二叉樹的前序的序列 為 1、2、3 n 不同的中序序列的對(duì)應(yīng) 著不同樹形的二叉樹 不同的中序序列的總數(shù) 是不同樹形的二叉樹的 總和不同的中序序列在中序 周游時(shí)和相應(yīng)的進(jìn)出棧 序列一一對(duì)應(yīng)。 不同的進(jìn)出棧序列的總 數(shù)是不同樹形的二叉樹 的總和 實(shí)例：e.g: 當(dāng) 二叉樹的結(jié)點(diǎn)個(gè)數(shù) n = 3 前序序列為 1、2、3 時(shí)1231231231231231、進(jìn)棧2、進(jìn)棧3、進(jìn)棧3、出棧2、出棧1、出棧1、進(jìn)棧2、進(jìn)

34、棧2、出棧3、進(jìn)棧3、出棧1、出棧1、進(jìn)棧2、進(jìn)棧2、出棧1、出棧3、進(jìn)棧3、出棧1、進(jìn)棧1、出棧2、進(jìn)棧3、進(jìn)棧2、出棧3、出棧1、進(jìn)棧1、出棧2、進(jìn)棧2、出棧3、進(jìn)棧3、出棧8、樹的計(jì)數(shù)1、互不相似的二叉樹的棵數(shù)的計(jì)算 實(shí)例：e.g: 當(dāng) 二叉樹的結(jié)點(diǎn)個(gè)數(shù) n = 3 前序序列為 1、2、3 時(shí)1231231231231231、進(jìn)棧2、進(jìn)棧3、進(jìn)棧3、出棧2、出棧1、出棧1、進(jìn)棧2、進(jìn)棧2、出棧3、進(jìn)棧3、出棧1、出棧1、進(jìn)棧2、進(jìn)棧2、出棧1、出棧3、進(jìn)棧3、出棧1、進(jìn)棧1、出棧2、進(jìn)棧3、進(jìn)棧2、出棧3、出棧1、進(jìn)棧1、出棧2、進(jìn)棧2、出棧3、進(jìn)棧3、出棧 進(jìn)出棧序列總數(shù)的計(jì)算為2n

35、個(gè)方格中放置 3 個(gè) 1 的組合數(shù) 不合理的序列總數(shù)e.g: n = 3 時(shí)，6格放置3個(gè) 1 的序列情況：1 代表進(jìn)棧，0 表示出棧 1 1 1 0 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 0 0 1 1 1 1 0 0 1 1 0合理不合理8、樹的計(jì)數(shù)1、互不相似的二叉樹的棵數(shù)的計(jì)算 進(jìn)出棧序列總數(shù)的計(jì)算為2n 個(gè)方格中放置 n 個(gè) 1 的組合數(shù) 不合理的序列總數(shù)e.g: n = 3 時(shí)，6格放置3個(gè) 1 的序列情況：1 代表進(jìn)棧，0 表示出棧 1 1 1 0 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0

36、 1 1 0 0 1 0 1 0 1 0 0 0 0 1 1 1 1 0 0 1 1 0合理不合理n = 3 時(shí)，6 格放置 3 個(gè) 1 的序列情況： 3 序列總數(shù) 2 3 3 1不合理的序列總數(shù)： 2 3因此，n = 3 時(shí)進(jìn)出棧序列的總數(shù)為： 3 3 + 1 2 32 3推廣到結(jié)點(diǎn)數(shù)為 n 時(shí)的進(jìn)出棧序列總數(shù)： nn + 1 2 nn + 18、樹的計(jì)數(shù)2、推論：結(jié)點(diǎn)數(shù)為 n + 1 時(shí)的互不相似的有序樹總數(shù)和結(jié)點(diǎn)數(shù)為 n 時(shí)的互不相似的二叉樹的總數(shù)相等。12312312312312302311230123013201320E.g: n = 4 的所有樹 形只需考慮以下二叉樹的棵數(shù)即可023112301230132013208、樹的計(jì)數(shù) 結(jié)點(diǎn)數(shù)為 n 時(shí)的互不相似的