數(shù)據(jù)結構與算法樹3

1、64 樹和森林樹和森林 6.4.1樹的存儲結構 一、雙親表示法（順序存儲） /-樹的雙親表存儲表示-/ #define max_tree_size 100 typedef struct ptnode telemtype data; int parent; /雙親位置域 ptnode; typedef struct ptnode nodesmax_tree_size; int 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ù)組下標:* 便于涉及雙親的操作；* 求結點的孩子時需要遍

2、歷整棵樹。6.4.1樹的存儲結構二、孩子表示法（順序存儲） #define max_tree_size 100 typedef struct ptnode telemtype data; int child1; /第1個孩子位置域 int child2; /第2個孩子位置域 . int childd; /第d個孩子位置域 ptnode; typedef struct ptnode nodesmax_tree_size; int n; /結點數(shù) ptree;孩子表示法舉例radefcbgkh0123456789數(shù)組下標:* 便于涉及孩子的操作；求雙親不方便；* 采用同構的結點，空間浪費。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 孩子鏈表存儲表示（鏈式存儲） typedef struct ctnode /孩子結點 int child; struct ctnode *next; *childptr; typedef struct telemtype data; childptr firstchild; /孩子鏈表頭指針 ctbox; typedef struct ctbox nodesmax_tree_size; int n, r; /結點數(shù)和根的位置 ctree;孩子鏈

4、表存儲表示舉例radefcbgkh0123456789數(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: 設樹t以孩子鏈表為存儲結構,尋找值為x的雙親結點的算法如下:status parent(ctree t, telemtype x)/ 當值為x的結點不存在時返回-2; / 當值為x的結點為根結點時返回-1, / 否則返回x結點的雙親結點的下標值. if(t.nodest.r.data = x) return 1

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

6、ee &t, telemtype x, int i) / 當值為x的結點不存在時返回-2;當值為x的結點為 /葉結點或無第i 棵子樹時返回-1, 否則返回1. for(k=0; k=t.n) return 2; / 值為x的結點不存在 p= t.nodesk.firstchild; j = 1; if(!p) return 1; / x結點為葉結點 if(i=1) / 刪除長子時,特殊處理 j =p-child; / 記住要刪除子樹的下標 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 個兒子 j = p-next-child; / 記住要刪除子樹的下標 s = p-next; p-next = s-next; free(s); deletej(t, j); / 遞歸刪除第j號結點及其子樹 return 1;三.孩子兄弟表示法-樹的二叉樹表示法(二叉鏈表示法)b/-樹的二叉鏈表(孩子兄弟)存儲表示- typedef struct csnode elemtype data; struct csnode *firstchild,*nextsibling; csnode, *cstr

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

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

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

11、到每一結點的路徑長度之和。b 樹的帶權路徑長度樹的帶權路徑長度: 樹的帶權路徑長度為樹中所有葉子結點(k)的帶權路徑長度kk之和,b通常記作： nb wpl= kk。b k=1 最優(yōu)二叉樹或赫夫曼(huffman)樹的定義b假設有n個權值1, 2, , n，試構造一棵有n個葉子結點的二叉樹,每個葉子結點帶權為i, 則其中：b帶權路徑長度wpl最小的二叉樹稱做b 最優(yōu)二叉樹最優(yōu)二叉樹b 或赫夫曼樹赫夫曼樹.例1：下面三棵二叉樹的四個葉子結點a,b,c,d的權值為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),構造赫夫曼樹ht,并求出n個字符的赫夫曼編碼hc.b if(n=1) return;bm=2*n-1;bht=(huffmantree)malloc(m+1)*sizeof(htnode);/0號單未用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最小的兩個結點,b / 其序號分別為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/-從葉子到根逆向求每個字符的赫夫曼編碼-b hc=(

14、hffmancode)malloc(n+1*sizeof(char *); /分配n個字符編碼的頭指針向量b cd=(char *)malloc(n*sizeof(char);/分配求編碼的工作空間b cdn-1=/0; /編碼結束符.求赫夫曼編碼的算法（續(xù)二）:b for(i=1;i=n;+i)/逐個字符求赫夫曼編碼b start=n-1;/編碼結束符位置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個字符編碼分配空間b strcpy(hci,&cdstart); /從cd復制編碼(串)到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; /遍歷赫夫曼樹時用作結點狀態(tài)標志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)/登記葉子結點的字符的編碼b hcp=(char *)malloc(cdlen+1) *sizeof(char);b cdcdlen=0;strcpy(hcp,cd);/復制編碼(串)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 /退到父結點,編碼長度減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