数据结构与算法树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; /结点数 ptree;双亲表示法举例radefcbgkhr -1 a 0 b 0 c 0 d 1 e 1 f 3 g 6 h 6 k 6 0123456789数组下标:* 便于涉及双亲的操作；* 求结点的孩子时需要遍

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; /结点数 ptree;孩子表示法举例radefcbgkh0123456789数组下标:* 便于涉及孩子的操作；求双亲不方便；* 采用同构的结点，空间浪费。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; /结点数和根的位置 ctree;孩子链

4、表存储表示举例radefcbgkh0123456789数组下标:* 便于涉及孩子的操作；* 求结点的双亲时不方便。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是森林,则可按如下规则转换成一棵二叉树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、下规则转换成森林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最优二叉树(赫夫曼树)b 路径长度路径长度: 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径上的分支数目称做路径长度。b 树的路径长度树的路径长度: 树的路径长度是从树根

11、到每一结点的路径长度之和。b 树的带权路径长度树的带权路径长度: 树的带权路径长度为树中所有叶子结点(k)的带权路径长度kk之和,b通常记作： nb wpl= kk。b k=1 最优二叉树或赫夫曼(huffman)树的定义b假设有n个权值1, 2, , n，试构造一棵有n个叶子结点的二叉树,每个叶子结点带权为i, 则其中：b带权路径长度wpl最小的二叉树称做b 最优二叉树最优二叉树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;求赫夫曼编码的算法（续一）: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; /编码结束符.求赫夫曼编码的算法（续二）: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; /遍历赫夫曼树时用作结点状态标志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