數(shù)據(jù)結(jié)構(gòu)Ch6樹

1、數(shù) 據(jù) 結(jié) 構(gòu) Ch.6 樹計(jì) 算 機(jī) 學(xué) 院 肖明軍Email: 1Ch.6 樹樹形結(jié)構(gòu)：二叉樹，樹，森林等結(jié)點(diǎn)間有分支，具有層次關(guān)系 特征：每個(gè)結(jié)點(diǎn)最多只有一個(gè)直接前驅(qū)，但可有多個(gè)直間后繼開始結(jié)點(diǎn) 根終端結(jié)點(diǎn) 葉其余結(jié)點(diǎn) 內(nèi)部結(jié)點(diǎn)應(yīng)用：家譜、行政架構(gòu)等，計(jì)算機(jī)系統(tǒng)中的文件目錄等2.樹的概念Def: 樹是n (n=0) 個(gè)結(jié)點(diǎn)的有限集，為空時(shí)稱為空樹，否則它滿足：有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；其余結(jié)點(diǎn)可分為m (m=0) 個(gè)互不相交的子集1 ，2，m，其中每個(gè)子集本身又是一棵樹，并稱之為根的子樹3.樹的概念遞歸定義：刻畫了樹的固有特性：非空樹由若干棵子樹構(gòu)成，子樹由較小子樹構(gòu)成表示：4.樹

2、的概念術(shù)語：結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹數(shù)目（樹的度）葉子：終端結(jié)點(diǎn)，度為的結(jié)點(diǎn)分支結(jié)點(diǎn)：非終端結(jié)點(diǎn)，度內(nèi)部結(jié)點(diǎn)：根之外的分支結(jié)點(diǎn)根：開始結(jié)點(diǎn)孩子、雙親：某結(jié)點(diǎn)的子樹的根稱為該 結(jié)點(diǎn)的孩子，該結(jié)點(diǎn)為孩子的雙親 直接前驅(qū)（雙親） 直接后繼（孩子）兄弟：同一雙親的孩子互為兄弟5.樹的概念術(shù)語：路徑：道路（自上而下） 若存在一結(jié)點(diǎn)序列k1,k2,，kj，使得ki是ki+1的雙親（=i=0) 棵互不相交的樹的集合 樹和森林非常接近：刪去樹根 森林 森林加上一根 樹7.樹的概念邏輯特征：父子關(guān)系（非線性關(guān)系）：任一結(jié)點(diǎn)至多有一直接前驅(qū)（雙親）結(jié)點(diǎn)，但可有多個(gè)直接后繼（子女）結(jié)點(diǎn)開始結(jié)點(diǎn)：根終端結(jié)點(diǎn)：葉祖先與

3、子孫關(guān)系：是對父子關(guān)系的延拓，它定義了樹中結(jié)點(diǎn)的縱向關(guān)系橫向關(guān)系：有序樹定義了同一組兄弟間的從左到右的長幼關(guān)系，可將其延拓到結(jié)點(diǎn)間的橫向次序：k1和k2是兄弟，k1在左，則k1的任一子孫在k2的任一子孫的左邊其余結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn)8.二叉樹 是一種特殊的樹型結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)至多只有二棵子樹，一般樹可轉(zhuǎn)換為二叉樹，計(jì)算機(jī)用途甚廣.二叉樹的定義ef: 二叉樹是n(n=0)個(gè)結(jié)點(diǎn)的有限集，它或者是空集，或由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的，分別稱作根的左子樹和右子樹的二叉樹組成9.1 二叉樹的定義形態(tài)與度為的有序樹區(qū)別： 當(dāng)某一結(jié)點(diǎn)只有一孩子時(shí)，有序樹中它理所當(dāng)然為長子，但二叉樹中，一個(gè)結(jié)點(diǎn)只有一個(gè)孩子亦需分出

4、其左右10.2 二叉樹的性質(zhì)性質(zhì)：二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i1，根為第1層） pf：歸納法歸納基礎(chǔ)：i=1,2i-1=1,第1層上只有根，故成立歸納假設(shè)：設(shè)所有的j（1 ji）命題成立即： 第j層結(jié)點(diǎn)數(shù)j-1歸納步驟：j=i時(shí)，第i-1層結(jié)點(diǎn)數(shù) i-2(由歸納假設(shè)) 因?yàn)?，每個(gè)結(jié)點(diǎn)至多有兩個(gè)孩子 所以，第i層上結(jié)點(diǎn)數(shù) i-2=2i-111.2 二叉樹的性質(zhì)性質(zhì)深度為h的二叉樹至多有h-1個(gè)結(jié)點(diǎn)（h1).Pf: 深度一定時(shí)，僅當(dāng)每層上結(jié)點(diǎn)達(dá)到最大時(shí)，該樹結(jié)點(diǎn)最多 利用性質(zhì)1知，深度為h的二叉樹至多有： 20+21+2h-1 = 2h-112.2 二叉樹的性質(zhì)性質(zhì)在任一二叉樹中，設(shè)葉

5、子數(shù)為n0，度為的結(jié)點(diǎn)數(shù)為n2則n0=n2+1. Pf: 設(shè)n1為度為的結(jié)點(diǎn)總數(shù)，則結(jié)點(diǎn)總數(shù)n等于度， 度和度結(jié)點(diǎn)數(shù)之和 n = n0+n1+n2 / 二叉樹 （.）另一方面，除根外，其余結(jié)點(diǎn)均是其雙親的孩子，樹中： 孩子結(jié)點(diǎn)總數(shù) = n1+2n2 n-1 = n1+2n2 n = n1+2n2+1 （.）由.和.：n0=n2+113.2 二叉樹的性質(zhì)滿二叉樹：深度為h的具有h-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹完全二叉樹：若一二叉樹至多只有最下兩層上結(jié)點(diǎn)的度數(shù)可小于，且最下一層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置，則稱為完全二叉樹某結(jié)點(diǎn)無左孩子，則它必為葉子滿二叉樹是完全二叉樹，但反之未必成立14

6、.2 二叉樹的性質(zhì)性質(zhì)具有n個(gè)結(jié)點(diǎn)的完全二叉樹高為 或pf: 樹高為h，則前h-1層是高為h-1的滿二叉樹，結(jié)點(diǎn)總數(shù) = 2h-1-1. 2h-1-1 n 2h-1 (2h-1 n+1 2h) / 第h層上至少有一個(gè)結(jié)點(diǎn) 2h-1 n 2h /整數(shù) h-1 lgn h (h-1 1，則ki的雙親是 (2) 若2in,則ki的左孩子為k2i；否則ki無左孩子，即它必 為葉子。/因此，完全二叉樹中編號i 的結(jié)點(diǎn)必為葉子; (3) 若2i+1n,則ki的右孩子為k2i+1 ,否則ki無右孩子; (4) 若i為奇數(shù)且大于1，則ki的左兄弟為ki-1，否則ki無左兄 弟; (5) 若i為偶數(shù)且小于n，則

7、ki的右兄弟為ki+1，否則ki無右兄 弟。 證明從略。176.2.3 二叉樹的存儲結(jié)構(gòu) 上述關(guān)系中，編號足以反 映結(jié)點(diǎn)間的邏輯關(guān)系 可將n個(gè)結(jié)點(diǎn)存儲在向量 bt0.n中，其中： bt0 不用，或存儲n bt1.n 存儲編號為1至n的結(jié)點(diǎn)186.2.3 二叉樹的存儲結(jié)構(gòu)缺點(diǎn) 對一般的二叉樹，須按完全二叉樹的編號來存儲，浪費(fèi)空間，最壞情況是右單支樹，k個(gè)結(jié)點(diǎn)需2k-1個(gè)結(jié)點(diǎn)空間。結(jié)論 這種結(jié)構(gòu)只適用于存儲完全二叉樹，且插入和刪除不便。196.2.3 二叉樹的存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)類型定義 typedef struct node DataType data; struct node *lch

8、ild, *rchild; BinTNode; / 結(jié)點(diǎn)類型 typedef BinTNode *BinTree; /二叉樹類型206.2.3 二叉樹的存儲結(jié)構(gòu) 在二叉樹中，所有類型為BinTNode的結(jié)點(diǎn)，加上一個(gè)指向根的BinTree型頭指針root，就構(gòu)成了二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)，稱之為二叉鏈表 顯然，二叉鏈表由根指針root唯一確定。例子特性 空樹 root = NULL 葉子 左右指針為空 空指針數(shù)：n個(gè)結(jié)點(diǎn)，共有2n個(gè)指針域，但只有n-1個(gè)結(jié)點(diǎn)是別人的孩子，故空指針數(shù)為n+1216.3 遍歷二叉樹概念定義：沿某搜索路線，依次對樹中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問。重要性：是其它運(yùn)算的基

9、礎(chǔ)，很多樹上操作均依賴于遍歷操作，只是訪問結(jié)點(diǎn)所做的操作不同。如何遍歷？遍歷線性結(jié)構(gòu)很容易：從開始結(jié)點(diǎn)出發(fā)，依次訪問當(dāng)前結(jié)點(diǎn)的后繼，直至終端結(jié)點(diǎn)為止。遍歷路線只有一條(如單鏈表，從頭指針開始)。 但二叉樹中每個(gè)結(jié)點(diǎn)可能有兩個(gè)后繼，故遍歷路線不唯一，須找到適用于每個(gè)結(jié)點(diǎn)的相同的遍歷規(guī)則。226.3 遍歷二叉樹 在二叉樹的遞歸定義中，非空樹組成為： D、L、R 在任一結(jié)點(diǎn)上，可按某種次序執(zhí)行三個(gè)操作： 訪問根結(jié)點(diǎn)(D)，遍歷該結(jié)點(diǎn)的左子樹(L),遍歷該結(jié)點(diǎn)的右子樹(R) 顯然有六種執(zhí)行次序： 遍歷規(guī)則(從左到右) DLR,LDR,LRD的差別是訪問根的先后次序不同前序(先序，先根)遍歷：DLR中序

10、(中根)遍歷：LDR后序(后根)遍歷：LRD 236.3 遍歷二叉樹遍歷算法 以中根為例，遍歷二叉樹定義為： if 二叉樹非空 then (1) 遍歷左子樹 / 即遍歷二叉樹 (2) 訪問根 / 將(1)(2)和(2)(3)對調(diào)后為先根和后根遍歷 (3) 遍歷右子樹 /即遍歷二叉樹 / 否則為空操作 (遞歸結(jié)束條件) void Inorder(BinTree T) / T為二叉樹的頭指針 if (T) / T非空，T為空時(shí)為空操作 Inorder(T-lchild); / 遞歸遍歷左子樹 printf(“%c”, T-data)；/ 訪問根結(jié)點(diǎn)，具體問題，此 / 操作不同 Inorder(T-

11、rchild); / 遞歸遍歷右子樹 時(shí)間：O(n)246.3 遍歷二叉樹遍歷序列包絡(luò)線是遞歸遍歷路線向下：表示遞歸調(diào)用，更 深一層向上：表示遞歸結(jié)束，返 回一層 每個(gè)結(jié)點(diǎn)經(jīng)過3次，第1次經(jīng)過時(shí)訪問所得結(jié)點(diǎn)序列為前序，第2次經(jīng)過時(shí)訪問所得結(jié)點(diǎn)序列為中序，第3次經(jīng)過時(shí)訪問所得結(jié)點(diǎn)序列為后序。1個(gè)開始結(jié)點(diǎn)，1個(gè)終端結(jié)點(diǎn)，其余結(jié)點(diǎn)均有一個(gè)直接前驅(qū)和一個(gè)直接后繼，為區(qū)別3種次序在前面冠以 葉子的相對次序相同256.3 遍歷二叉樹通用的遍歷算法 因?yàn)樵L問結(jié)點(diǎn)的操作依賴于具體問題，故可將它作為一個(gè)函數(shù)指針參數(shù)放于遍歷算法的參數(shù)表中，調(diào)用時(shí)，使其指向具體的訪問結(jié)點(diǎn)的應(yīng)用函數(shù) void Inorder( Bi

12、nTree T, void (*Visit)(DataType x) ) if (T) Inorder(T-lchild, Visit); (*Visit)(T-data); Inorder(T-rchild, Visit); 其中Visit是一函數(shù)指針，它指向形如void f(DataType x)的函數(shù)，故可將訪問結(jié)點(diǎn)的操作寫在函數(shù)f中，通過調(diào)用語句： Inorder(root, f); 將f的地址傳給Visit。266.3 遍歷二叉樹通用的遍歷算法 例如，可將打印操作為 void print(DataType x) print(“%c”, x); 調(diào)用Inorder(root, prin

13、t)，即可完成前述算法。函數(shù)名：函數(shù)代碼的起址。276.3 遍歷二叉樹建立二叉鏈表 上述算法假定二叉鏈表已建立 建立二叉樹對應(yīng)的二叉鏈表方法很多先序遍歷構(gòu)造法 輸入先序序列，加入虛結(jié)點(diǎn)(輸入時(shí)用空格符“ ”)以示空指針的位置，例如前述的二叉樹，輸入為： ABDCEF286.3 遍歷二叉樹 void CreateBinTree(BinTree *T) / 注意T為指針的指針 char ch; if (ch = getchar() = n) return; / 回車結(jié)束輸入 if (ch = ) / 讀入空格 *T = NULL； / 將相應(yīng)的指針置空 else / 讀入的是結(jié)點(diǎn)數(shù)據(jù) *T = (

14、BinTNode*) malloc(sizeof(BinTNode); (*T)-data = ch; / 生成新結(jié)點(diǎn)，相當(dāng)于訪問根節(jié)點(diǎn) CreateBinTree(&(*T)-lchild); / 遍歷左子樹 CreateBinTree(&(*T)-rchild); / 遍歷右子樹 建樹時(shí)調(diào)用 CreateBinTree(&root), 將root(BinTree類型)的地址復(fù)制給T，故修改*T就相當(dāng)于修改了實(shí)參root本身。 時(shí)間：O(n)296.4 線索二叉樹基本概念 在一基本數(shù)據(jù)結(jié)構(gòu)上常常需要擴(kuò)充，增加輔助信息，其目的是：開發(fā)新操作；加速已有操作。線索 利用空指針域(n+1個(gè))存放指向

15、結(jié)點(diǎn)在某種遍歷次序下的前驅(qū)和后繼指針線索鏈表 加上線索的二叉鏈表線索二叉樹 相應(yīng)的二叉樹稱為線索二叉樹目的：加速遍歷操作 加速查找任一結(jié)點(diǎn)在某種遍歷次序下的前驅(qū)和后繼操作如何區(qū)別結(jié)點(diǎn)的指針域 孩子指針：指向孩子？ 線索指針：指向其某種遍歷次序下的前驅(qū)和后繼的線索？306.4 線索二叉樹基本概念結(jié)點(diǎn)結(jié)構(gòu)線索標(biāo)志中序線索樹和中序線索鏈表中序序列：CBDAFHGIE316.4 線索二叉樹基本概念中序線索樹中必有兩個(gè)指針域?yàn)榭涨靶蚓€索樹中，有幾個(gè)指針域?yàn)榭眨?前序序列的開始結(jié)點(diǎn)為根，故當(dāng)它的左子樹非空時(shí)，其指針域指向左指子樹，此時(shí)前序序列開始結(jié)點(diǎn)左指針非空。 但是，前序序列的終端結(jié)點(diǎn)的右指針必為空。

16、僅當(dāng)只有1個(gè)根結(jié)點(diǎn)或根的左子樹為空時(shí)有兩個(gè)空指針。326.4 線索二叉樹基本概念后序線索樹中，開始結(jié)點(diǎn)的左指針必為空，僅當(dāng)只有1個(gè)根時(shí)或根的右子樹為空時(shí)有兩個(gè)空指針。 與前序線索樹對稱帶頭結(jié)點(diǎn)的線索鏈表 樹上6.11圖(b). 令空指針也指向此哨兵336.4 線索二叉樹基本概念線索樹中，如何判定結(jié)點(diǎn)是否為葉子？ ltag = rtag = 1 (適用于三種線索樹)有時(shí)線索樹只有左線索或右線索之一線索化將二叉樹變?yōu)榫€索樹的過程按某種次序遍歷，在遍歷過程中用線索取代空指針。 typedef enum Link, Thread PointerTag; / 0為Link，1為Thread typede

17、f struct node DataType data; PointerTag ltag, rtag; struct node *lchild, *rchild; BinThrNode, *BinThrTree;設(shè)p和pre分別指向遍歷過程中當(dāng)前訪問結(jié)點(diǎn)和其前驅(qū)，即*pre和*p是 前驅(qū)和后繼的關(guān)系，其中pre為全局量，在遍歷過程中建立線索。以中序?yàn)槔?，pre初始為NULL，因?yàn)橹行蚯膀?qū)對開始結(jié)點(diǎn)是NULL。346.4 線索二叉樹 void InorderThreading(BinThrTree p) / pre為全局量，初值為NULL if (p) InorderThreading(p-lc

18、hild); / 左子樹線索化 p-ltag = (p-lchild) ? Link : Thread; / 左指針非空，置為 / Link，否則為線索。 p-rtag = (p-rchild) ? Link : Thread; if (pre) / 若*pre存在 if (pre-rtag = Thread) / 當(dāng)前結(jié)點(diǎn)*p的前驅(qū)右標(biāo)志為線索 pre-rchild = p; / 令*pre的右線索指向中序后繼*p if (p-ltag = Thread) / 當(dāng)前結(jié)點(diǎn)的左線索已建立 p-lchild = pre; /令當(dāng)前節(jié)點(diǎn)的左線索指向中序前驅(qū) pre = p; /使*pre為*p的前驅(qū)

19、，循環(huán)不變量 InorderThreading(p-rchild); / 右子樹線索化 時(shí)間：和遍歷相同O(n). 后序(前序)線索化類似于此。訪問根結(jié)點(diǎn)356.4 線索二叉樹操作(加速) (1) 找某結(jié)點(diǎn)*p(中序線索樹中)中序前驅(qū)和后繼結(jié)點(diǎn)找*p的中序后繼i） 若*p的右子樹空，則p-rchild為右線索，直接指向*p的中序后繼ii）若*p的右子樹非空(rtag為0)，則*p的中序后繼必是其右子樹中第一個(gè)中序遍歷到的結(jié)點(diǎn)，其特征是： 從*p的右孩子開始，沿其左鏈往下找，直至找到一個(gè)沒有左孩子的結(jié)點(diǎn)為止，不妨稱其為右子樹中“最左下”的結(jié)點(diǎn)。 這里k 1, Rk不一定是葉子，其右子樹可為空，可

20、非空。算法 請自己給出找給定結(jié)點(diǎn)*p的中序后繼算法。時(shí)間O(h)，快于無線索的二叉樹。 p366.4 線索二叉樹找*p的中序前驅(qū) 中序是對稱序，其方法與(1)完全對稱 i） 若*p的ltag = 1，則中序前驅(qū)為lchild ii）若*p的ltag = 0，則中序前驅(qū)是*p的左子樹中 “最右下”的結(jié)點(diǎn)。 加速作用 在普通二叉樹中，找*p中序后繼： 對于ii）同樣有效 對于 i）就必須從根開始遍歷。 有線索是直接從線索找到O(1)。但線索一般“向上”指向其祖先，而二叉樹中無向上的鏈接，只能從根開始遍歷得到，最壞情況O(n)。376.4 線索二叉樹 (2) 找*p的后序前驅(qū)和后序后繼(在后序線索樹

21、中)找*p的后序前驅(qū)(易) i） 若*p的ltag = 1(左子樹為空)，則后序前驅(qū)為p-lchild ii）若*p的ltag = 0(左子樹非空)，則后序前驅(qū)為p的左孩子或右孩子 根是在遍歷左右子樹L和R之后被訪問 *p的前驅(qū)必是L和R中最后一個(gè)遍歷到的結(jié)點(diǎn) if (p的右孩子非空) then return p-rchild; / 后序前驅(qū)為p的右孩子 else return p-lchild; /后序前驅(qū)為p的左孩子找*p的后序后繼(難)(見右圖) i） 若*p為根，無后繼，返回NULL ii） 若*p是其雙親右子，則*p的后序后繼是雙親 iii）若*p是其雙親左子，但*p無右兄弟，則*p

22、的 后序后繼亦為雙親386.4 線索二叉樹找*p的后序后繼(續(xù))iv）若*p是其雙親左子，但*p有右兄弟，則*p的 后序后繼是其右兄弟子樹中1st后序遍歷到的結(jié)點(diǎn)，它是該子樹中“最左下的葉結(jié)點(diǎn)”結(jié)論：找后序前驅(qū)易 找后序后繼難，因?yàn)椋?只有*p的右子樹為空(rtag = 1)時(shí)，p-rchild是線索，可直接找到； 否則，一般須涉及*p的雙親，故僅給出*p時(shí)，須從根遍歷。 (3) 找*p的前序前驅(qū)和前序后繼 類似于后序的情況分析 討論：找前序前驅(qū)難(涉及雙親) 找前序后繼易 396.4 線索二叉樹 (4) 遍歷線索二叉樹 遍歷某次序的線索二叉樹，只要從該次序下的開始結(jié)點(diǎn)出發(fā)，反復(fù)找其后繼直至終

23、端結(jié)點(diǎn)為止。中序 找開始結(jié)點(diǎn)(最左下結(jié)點(diǎn))，找當(dāng)前結(jié)點(diǎn)中序后繼，直至終端結(jié)點(diǎn)(p-rchild = NULL) 頭結(jié)點(diǎn)的右指針指向開始結(jié)點(diǎn)較方便前序 找開始結(jié)點(diǎn)(根)，找當(dāng)前結(jié)點(diǎn)的前序后繼，直至終端結(jié)點(diǎn) (p-rchild = NULL) 頭結(jié)點(diǎn)的右指針指向終端結(jié)點(diǎn)較方便后序 找終端結(jié)點(diǎn)(根)，找當(dāng)前結(jié)點(diǎn)的后序前驅(qū)，直至開始結(jié)點(diǎn) (p-lchild = NULL)，得到的是后序序列的逆序列 頭結(jié)點(diǎn)的右指針指向開始結(jié)點(diǎn)較方便時(shí)間：仍為O(n)，但因?yàn)榉沁f歸，略快于遞歸的方法對遍歷而言 前序線索樹中，只需保留右線索樹即可 中序線索樹中，保留左、右線索之一均可 后序線索樹中，只需保留左線索即可406

24、.5 樹和森林樹、森林與二叉樹的轉(zhuǎn)換樹 = 二叉樹 樹中每個(gè)結(jié)點(diǎn)有多個(gè)孩子 = 二叉樹只有兩個(gè)孩子 長子及右鄰兄弟 = 二叉樹的左右孩子 節(jié)點(diǎn)X的長子是其左子，X的右兄弟是其右子每個(gè)結(jié)點(diǎn)僅保留與長子的連線所有兄弟結(jié)點(diǎn)間連線416.5 樹和森林樹、森林與二叉樹的轉(zhuǎn)換森林 = 二叉樹將各樹轉(zhuǎn)換為二叉樹(根無右兄弟，所以無右子)將各根作為兄弟互連426.5 樹和森林樹、森林與二叉樹的轉(zhuǎn)換二叉樹 = 樹或森林設(shè)x是y的左孩子，則將x的右孩子，右孩子的右孩子，都與y相連去掉所有雙親到右孩子的連線436.5 樹和森林樹的存儲結(jié)構(gòu)雙親鏈表表示法 每結(jié)點(diǎn)雙親唯一，故存儲結(jié)點(diǎn)時(shí)，增加一個(gè)parent域指向雙親，

25、用向量表示較方便特點(diǎn)：向上鏈接，根的parent為-1 求指定結(jié)點(diǎn)雙親(O(1)及祖先(O(h)方便 求指定結(jié)點(diǎn)孩子及后代須遍歷數(shù)組O(n)類型說明(略)446.5 樹和森林樹的存儲結(jié)構(gòu)孩子鏈表表示法若k叉樹用k叉鏈表表示，會導(dǎo)致浪費(fèi)空間 樹邊n-1條 空指針kn-(n-1)=n(k-1)+1設(shè)度數(shù)域，結(jié)點(diǎn)不等長、運(yùn)算不便孩子鏈表：每結(jié)點(diǎn)設(shè)一孩子鏈表，將結(jié)點(diǎn)及相應(yīng)孩子鏈表的頭指針放在一向量中。456.5 樹和森林樹的存儲結(jié)構(gòu)孩子鏈表表示法（續(xù)）特點(diǎn)：易實(shí)現(xiàn)找結(jié)點(diǎn)的孩子及子孫(向下查找易) 難實(shí)現(xiàn)找結(jié)點(diǎn)的雙親及祖先(向上查找難)雙親孩子鏈表表示法 在孩子鏈表中，增加parent域 此方法結(jié)合了雙

26、親鏈表和孩子鏈表的優(yōu)點(diǎn)，向上向下查找均方便類型說明：略孩子兄弟鏈表表示法 樹 = 二叉樹時(shí)，結(jié)點(diǎn)關(guān)系由：最左孩子、右鄰兄弟表 示466.5 樹和森林樹和森林的遍歷先序遍歷樹 先訪問樹的根；然后依次先序遍歷根的每棵子樹后序遍歷樹 先依次后序遍歷根的每棵子樹；然后訪問樹的根；先序遍歷森林先訪問森林中第一棵樹的根；然后先序遍歷第一棵樹中根結(jié)點(diǎn)的各子樹所構(gòu)成的森林；最后先序遍歷除第一棵外其它樹構(gòu)成的森林后序遍歷森林后序遍歷森林中第一棵樹的根結(jié)點(diǎn)的各子樹所構(gòu)成的森林；然后訪問第一棵樹的根；最后后序遍歷除第一棵外其它樹構(gòu)成的森林先序遍歷恰好等價(jià)于先序遍歷對應(yīng)的二叉樹，后序遍歷恰好等價(jià)于中序遍歷對應(yīng)的二叉樹

27、。476.6 Huffman樹及其應(yīng)用6.6.1 最優(yōu)二叉樹概念結(jié)點(diǎn)路徑長度：根到該結(jié)點(diǎn)所經(jīng)過的邊數(shù)樹的路徑長度：所有結(jié)點(diǎn)的路徑長度之和 (結(jié)點(diǎn)數(shù)相同時(shí)，完全二叉樹的路徑長度最短)結(jié)點(diǎn)的帶權(quán)路徑長度： 結(jié)點(diǎn)的權(quán)值Wi 結(jié)點(diǎn)的路徑長度li樹的帶權(quán)路徑長度(實(shí)際上是加權(quán)外部路徑長度) 所有葉子的加權(quán)路徑長度之和486.6 Huffman樹及其應(yīng)用6.6.1 最優(yōu)二叉樹最優(yōu)二叉樹（Huffman樹） 在權(quán)為w1,w2,wn的葉子所構(gòu)成的所有的二叉樹，WPL最小的二叉樹稱為最優(yōu)二叉樹 例 n=4，a:7, b:5, c:2, d:4若葉子權(quán)值相同，完全二叉樹一定是最優(yōu)二叉樹，否則不一定496.6 Hu

28、ffman樹及其應(yīng)用6.6.1 最優(yōu)二叉樹構(gòu)造最優(yōu)二叉樹 顯然，權(quán)越大應(yīng)離根越近，Huffman首先提出了構(gòu)造方法：1）初始森林：根據(jù)給定的n個(gè)權(quán)w1,w2,wn構(gòu)成一個(gè)包含n棵二叉樹的森林F=T1,T2,Tn. 其中Ti只有一個(gè)根(亦為葉子)結(jié)點(diǎn)，其權(quán)為wi;2）合并：在F中選兩棵根的權(quán)最小的二叉樹(若不止兩棵，則任選)作為左、右孩子，將其合并為一棵新樹，新根權(quán)值為這兩個(gè)結(jié)點(diǎn)的權(quán)值之和；3）對新森林F重復(fù)2)，直至只剩下一棵樹為止。506.6 Huffman樹及其應(yīng)用6.6.1 最優(yōu)二叉樹構(gòu)造最優(yōu)二叉樹算法特點(diǎn)初始有n棵樹，每棵樹僅有一個(gè)孤立結(jié)點(diǎn)合并：每合并一次，少一棵樹，故只需合并n-1次

29、 每合并一次產(chǎn)生1新結(jié)點(diǎn)，且新結(jié)點(diǎn)度為2，故最終的 Huffman樹有2n-1個(gè)結(jié)點(diǎn)： 實(shí)際上任何嚴(yán)格二叉樹中，葉子數(shù)為n時(shí)，總結(jié)點(diǎn)數(shù)為2n-1。516.6 Huffman樹及其應(yīng)用6.6.1 最優(yōu)二叉樹構(gòu)造最優(yōu)二叉樹存儲結(jié)構(gòu) #define n 100 / 葉子數(shù) #define m 2*n-1 / 結(jié)點(diǎn)總數(shù) typedef struct float weight; / 權(quán)，不妨設(shè)0 int lchild, rchild, parent; / 指針 HTNode; typedef HTNode HuffmanTreem; parent域作用：找雙親結(jié)點(diǎn) 為-1時(shí)表示根，區(qū)分根與非根構(gòu)造算法5

30、26.6 Huffman樹及其應(yīng)用void CreateHuffmanTree (HuffmanTree T) / 構(gòu)造最優(yōu)樹，根為Tm-1 int i, p1, p2; InitHuffmanTree(T); / 初始化, 將2n-1個(gè)結(jié)點(diǎn)的3個(gè)指針置空(-1),權(quán)置為0 InputWeight(T); / 輸入n個(gè)葉子(根)的權(quán)存于T0.n-1中，初 /始化森林F0中的根權(quán) for (i = n; i 平均碼長最小前綴碼 樹中任一葉子不可能是其它葉子的祖先 每葉子編碼不可能是其它葉子編碼的前綴算法實(shí)現(xiàn) (對字符集編碼，即葉子集編碼) typedef struct char ch; / 放字

31、符 char bitsn+1; / 放位串0結(jié)束，碼長不會超過n CodeNode; / 存放Huffman編碼的結(jié)點(diǎn) typedef CodeNode HuffmanCoden;586.6.2 Huffman編碼 void HuffmanCoding (HuffmanTree T, HuffmanCode H) / 根據(jù)哈夫曼樹T求哈夫曼編碼表H int c, p, i; / c和p分別指示樹T中孩子和父親的位置 char cdn+1; / 臨時(shí)存放編碼 int start; / 指示編碼在cd中的起始位置 cdn = 0; / 從后往前放編碼 for (i = 0; i = 0) / 到根

32、為止 if (Tp.lchild = c) cd-start = 0; / 若Tc是Tp的左子樹生成代碼0 else cd-start = 1; / 否則生成代碼1 c = p; / 繼續(xù)上溯 strcpy(Hi.bits, &cdstart); / 復(fù)制編碼位串 / endfor / 時(shí)間: O(n.h)596.6.2 Huffman編碼4. 應(yīng)用 (數(shù)據(jù)文件的壓縮與解壓)壓縮數(shù)據(jù)文件 (對文件編碼) for (依次從f1中讀入字符c) 在Huffman編碼表H中，找Hi.ch = c 將c轉(zhuǎn)換為Hi.bits寫入壓縮文件f2中； / 按bits0，1串寫入“位”，設(shè)f2是二進(jìn)制文件 加壓譯

33、碼 (對壓縮文件解碼) for (依次讀入f2中的位串) / 直至文件結(jié)束 從Huffman樹根Tm-1出發(fā) 若當(dāng)前讀入0，走向左孩子，否則走向右孩子； 若到達(dá)葉子Ti，便譯出字符Hi.ch寫入還原文件中，然后 重新從根出發(fā)譯碼 Note: 實(shí)際壓縮與解壓時(shí)，編碼的0/1位串，不是字符串，即寫入壓縮文件中的是“位”606.7 回溯法與搜索樹回溯法思想 有一類問題，需要找出它的解集合，或要求找出滿足某些約束條件下的最優(yōu)解，最簡單的方法是回溯法。 所謂回溯就是走回頭路，即在一定的約束條件下試探地搜索前進(jìn)，若前進(jìn)中受阻，則回頭另擇道路繼續(xù)搜索(搜索路線是一棵樹)N皇后問題(Gauss 1777-18

34、55 德國數(shù)學(xué)家)高斯8后問題 (1850提出)，即在88國際象棋棋盤上，安放8個(gè)皇后，要求彼此互不攻擊，有多少個(gè)解，這些解的格局如何？ 他本人未解決此問題 原因： 種格局，92個(gè)解(包括對稱解)616.7 回溯法與搜索樹攻擊(約束條件) 同一行、列，同一對角線的兩皇后互相攻擊i+j: 135度對角線：同一對角線上元素行列號之和相等(2n-1條) 02n-2j-i: 45度對角線：同一對角線上元素行列號之差相等(2n-1條) (n-1),0,n-1626.7 回溯法與搜索樹回溯法 從第1行開始依次放置皇后，每行從第1列開始試探位置是否安全，安全則放置，若某行所有位置均不安全，則回溯到上一行，重新放置。將上述求解過程中棋盤狀態(tài)的每一步變化用樹來表示，則可用4叉樹表示(如書上Fig6.29),該樹反映了狀態(tài)空間中搜索過程，不滿足約束條件的結(jié)點(diǎn)不再生長(即被剪枝)。 先序遍歷該樹636.7 回溯法與搜索樹N皇后算法 設(shè)t