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

1、64 樹和森林樹和森林 6.4.1樹的存儲(chǔ)結(jié)構(gòu) 一、雙親表示法（順序存儲(chǔ)） /-樹的雙親表存儲(chǔ)表示-/ #define max_tree_size 100 typedef struct ptnode telemtype data; int parent; /雙親位置域 ptnode; typedef struct ptnode nodesmax_tree_size; int n; /結(jié)點(diǎn)數(shù) ptree;雙親表示法舉例radefcbgkhr -1 a 0 b 0 c 0 d 1 e 1 f 3 g 6 h 6 k 6 0123456789數(shù)組下標(biāo):* 便于涉及雙親的操作；* 求結(jié)點(diǎn)的孩子時(shí)需要遍

2、歷整棵樹。6.4.1樹的存儲(chǔ)結(jié)構(gòu)二、孩子表示法（順序存儲(chǔ)） #define max_tree_size 100 typedef struct ptnode telemtype data; int child1; /第1個(gè)孩子位置域 int child2; /第2個(gè)孩子位置域 . int childd; /第d個(gè)孩子位置域 ptnode; typedef struct ptnode nodesmax_tree_size; int n; /結(jié)點(diǎn)數(shù) ptree;孩子表示法舉例radefcbgkh0123456789數(shù)組下標(biāo):* 便于涉及孩子的操作；求雙親不方便；* 采用同構(gòu)的結(jié)點(diǎn)，空間浪費(fèi)。r 1

3、a 4 b 0 c 6 d 0 e 0 f 7 g 0 h 0 k 0 2 3 5 0 0 0 0 0 0 0 0 0 8 9 0 0 0 0 0 0 孩子鏈表存儲(chǔ)表示（鏈?zhǔn)酱鎯?chǔ)） typedef struct ctnode /孩子結(jié)點(diǎn) int child; struct ctnode *next; *childptr; typedef struct telemtype data; childptr firstchild; /孩子鏈表頭指針 ctbox; typedef struct ctbox nodesmax_tree_size; int n, r; /結(jié)點(diǎn)數(shù)和根的位置 ctree;孩子鏈

4、表存儲(chǔ)表示舉例radefcbgkh0123456789數(shù)組下標(biāo):* 便于涉及孩子的操作；* 求結(jié)點(diǎn)的雙親時(shí)不方便。r a b / c d / e / f g / h / k /1 2 3 / 4 5 / 6 / 7 8 9 / t.nodes ; t.n=10; t.r = 0;例1: 設(shè)樹t以孩子鏈表為存儲(chǔ)結(jié)構(gòu),尋找值為x的雙親結(jié)點(diǎn)的算法如下:status parent(ctree t, telemtype x)/ 當(dāng)值為x的結(jié)點(diǎn)不存在時(shí)返回-2; / 當(dāng)值為x的結(jié)點(diǎn)為根結(jié)點(diǎn)時(shí)返回-1, / 否則返回x結(jié)點(diǎn)的雙親結(jié)點(diǎn)的下標(biāo)值. if(t.nodest.r.data = x) return 1

5、; /值為x的結(jié)點(diǎn)為根結(jié)點(diǎn); for(i=0;ichild.data != x) p = p-next; if(p) return (i); / 找到x的雙親結(jié)點(diǎn) return 2; / 值為x的結(jié)點(diǎn)不存在例2: 刪除值為x的結(jié)點(diǎn)的第i棵子樹的算法delete如下：void deletej(ctree &t, int j)/ 刪除樹t的第j號(hào)結(jié)點(diǎn)及其子樹 if(!t.nodesj.firstchild) / 刪除葉結(jié)點(diǎn) for(i=j; inext;i = s-child; free(s);deletej(t, i); / 遞歸刪除第i號(hào)結(jié)點(diǎn)及其子樹 status delete(ctr

6、ee &t, telemtype x, int i) / 當(dāng)值為x的結(jié)點(diǎn)不存在時(shí)返回-2;當(dāng)值為x的結(jié)點(diǎn)為 /葉結(jié)點(diǎn)或無第i 棵子樹時(shí)返回-1, 否則返回1. for(k=0; k=t.n) return 2; / 值為x的結(jié)點(diǎn)不存在 p= t.nodesk.firstchild; j = 1; if(!p) return 1; / x結(jié)點(diǎn)為葉結(jié)點(diǎn) if(i=1) / 刪除長子時(shí),特殊處理 j =p-child; / 記住要?jiǎng)h除子樹的下標(biāo) t.nodesk.firstchild = p-next; free(p); else while(p-next & jnext ; j+;

7、 if(ji-1 | !p-next) return 1; / 無第i 棵子樹 / p指向第i-1 個(gè)兒子 j = p-next-child; / 記住要?jiǎng)h除子樹的下標(biāo) s = p-next; p-next = s-next; free(s); deletej(t, j); / 遞歸刪除第j號(hào)結(jié)點(diǎn)及其子樹 return 1;三.孩子兄弟表示法-樹的二叉樹表示法(二叉鏈表示法)b/-樹的二叉鏈表(孩子兄弟)存儲(chǔ)表示- typedef struct csnode elemtype data; struct csnode *firstchild,*nextsibling; csnode, *cstr

8、ee;radefcbgkhradechfgbk孩子兄弟表示法示例：6.4.2 森林與二叉樹的轉(zhuǎn)換森林與二叉樹的轉(zhuǎn)換一.森林轉(zhuǎn)換成二叉樹b如果f=t1,t2, ,tm是森林,則可按如下規(guī)則轉(zhuǎn)換成一棵二叉樹b=(root,lb,rb)。b (1)若f為空，即m=0,則b為空樹；b (2)若f非空，即m0，則b的根root即為森林中第一棵樹的根root(t1)；b b的左子樹lb是從t1中根結(jié)點(diǎn)的子樹森林f1=t11,t12, ,t1m1轉(zhuǎn)換而成的二叉樹;b 其右子對(duì)rb是從森林f=t2,t3, ,tm 轉(zhuǎn)換而成的二叉樹.二. 二叉樹轉(zhuǎn)換成森林b如果b=(root,lb,rb)是一棵二叉樹,則可按如

9、下規(guī)則轉(zhuǎn)換成森林f=t1,t2, ,tm：b (1)若b為空，則f為空；b (2)若b非空，則f中第一棵樹t1的根root(t1)即為二叉樹b的根root；b t1中的根結(jié)點(diǎn)的子樹森林 f1是由b的左子樹lb轉(zhuǎn)換而成的森林;b f中除t1之外其余樹組成的森林f=t2,t3, ，tm是由b的右子樹rb轉(zhuǎn)換而成的森林。6.4.3 樹和森林的遍歷樹和森林的遍歷b 樹的兩種遍歷方法：b一、先根遍歷：b （1）訪問樹的根結(jié)點(diǎn)；b （2）依次先根遍歷每棵子樹。b r a d e b c f g h kb二、后根遍歷：b（1）依次后根遍歷每棵子樹。b（2）訪問樹的根結(jié)點(diǎn)；b d e a b g h k f

10、c r radefcbgkh森林的兩種遍歷方法：b 一、先序遍歷森林：b 若森林非空，則b （1）訪問森林中第一棵樹的根結(jié)點(diǎn)；b （2）先序遍歷第一棵樹的根結(jié)點(diǎn)的子樹森林；b （3）先序遍歷除去第一棵樹之后的森林。b二、中序遍歷森林：b 若森林非空，則b（1）中序遍歷第一棵樹的根結(jié)點(diǎn)的子樹森林；b （2）訪問森林中第一棵樹的根結(jié)點(diǎn)；b （3）中序遍歷除去第一棵樹之后的森林。6.6 赫夫曼樹及其應(yīng)用6.6.1最優(yōu)二叉樹(赫夫曼樹)b 路徑長度路徑長度: 從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑,路徑上的分支數(shù)目稱做路徑長度。b 樹的路徑長度樹的路徑長度: 樹的路徑長度是從樹根

11、到每一結(jié)點(diǎn)的路徑長度之和。b 樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度: 樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點(diǎn)(k)的帶權(quán)路徑長度kk之和,b通常記作： nb wpl= kk。b k=1 最優(yōu)二叉樹或赫夫曼(huffman)樹的定義b假設(shè)有n個(gè)權(quán)值1, 2, , n，試構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹,每個(gè)葉子結(jié)點(diǎn)帶權(quán)為i, 則其中：b帶權(quán)路徑長度wpl最小的二叉樹稱做b 最優(yōu)二叉樹最優(yōu)二叉樹b 或赫夫曼樹赫夫曼樹.例1：下面三棵二叉樹的四個(gè)葉子結(jié)點(diǎn)a,b,c,d的權(quán)值為7、5、2、4abcd7524abcd7524cdab7524(a)wpl=7x2+5x2+2x2+4x2 = 36(b)wpl=7x3

12、+5x3+2x1+4x2 = 46(c)wpl=7x1+5x2+2x2+4x2 = 35例2 最佳判定方法(p.144)(a)wpl=10 x4+30 x4+40 x3+15x2+5x1=315(b)wpl=5x3+15x3+40 x2+30 x2+10 x2=22010c90ed51540ba30607080nnnnyyyyy107090ec54015ba3060d0),構(gòu)造赫夫曼樹ht,并求出n個(gè)字符的赫夫曼編碼hc.b if(n=1) return;bm=2*n-1;bht=(huffmantree)malloc(m+1)*sizeof(htnode);/0號(hào)單未用b for(p=ht,

13、i=1;i=n;+i,+p,+w) *p=*w,0,0,0;b for(;i=m;+i,+p) *p=0,0,0,0;求赫夫曼編碼的算法（續(xù)一）:b for(i=n+1;i=m;+i) /建赫夫曼樹b /在ht1.i-1選擇parent為0且weight最小的兩個(gè)結(jié)點(diǎn),b / 其序號(hào)分別為s1和s2.b select(ht,i-1,s1,s2);b hts1.parent=i;hts2.parent=i;b hti.lchild=s1;hti.rchild=s2;b hti.weight=hts1.weight+hts2.weight;bb/-從葉子到根逆向求每個(gè)字符的赫夫曼編碼-b hc=(

14、hffmancode)malloc(n+1*sizeof(char *); /分配n個(gè)字符編碼的頭指針向量b cd=(char *)malloc(n*sizeof(char);/分配求編碼的工作空間b cdn-1=/0; /編碼結(jié)束符.求赫夫曼編碼的算法（續(xù)二）:b for(i=1;i=n;+i)/逐個(gè)字符求赫夫曼編碼b start=n-1;/編碼結(jié)束符位置b for(c=i,f=hti;f!=0;c=f,f=htf.parent)b /從葉子至根逆向求編碼b if(htf.lchild=c) cd-start=0;b else cd-start=1;b hci=(char *)malloc(

15、n-start)*sizeof(char);b /為第i個(gè)字符編碼分配空間b strcpy(hci,&cdstart); /從cd復(fù)制編碼(串)到hcb b free(cd); /釋放工作空間b/huffancoding 求赫夫曼編碼的算法如下:b/-無棧非遞歸遍歷赫夫曼樹,求赫夫曼編碼bhc=(huffmancode)malloc(n+1)*sizeof(char *);bp=m;cdlen=0;bfor(i=1;i=m;+i)b hti.weight=0; /遍歷赫夫曼樹時(shí)用作結(jié)點(diǎn)狀態(tài)標(biāo)志bwhile(p)b if(htp.weight=o)/向左b htp.weight=1;b

16、if(htp.lchild!=0)p=htp.lchild;cdcdlen+=0;b else if(htp.rchild=0)/登記葉子結(jié)點(diǎn)的字符的編碼b hcp=(char *)malloc(cdlen+1) *sizeof(char);b cdcdlen=0;strcpy(hcp,cd);/復(fù)制編碼(串)b b 無 棧 非 遞 歸 遍 歷 赫 夫 曼 樹 ,求赫夫曼編碼b else if (htp.weight=1)/向右b htp.weight=2;b i f ( h t p . r c h i l d ! = 0 ) p = h t p . r c h i l d ; cdcdlen

17、+=1;b else /htp.weight=2,退回b htp.weight=0;p=htp.parent;-cdlen;b /退到父結(jié)點(diǎn),編碼長度減1b /elseb/while500029000700080001400023000300011000000000000000000000000ht.weight parent lchild rchild 1 2 3 4 5 6 7 8 91011121314155900291400710008100014120023130039001111008111715123419138929145104215611581521210001314ht.weight parent lchild rchild 1 2 3 4 5 6 7 8 9101112131415532311178291400000001111110 1 1 012345678 1 01 1 1 01