数据结构树的讲解.ppt

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;,双亲表示法举例,* 便于涉及双亲的操作； * 求结点的孩子时需要遍历整棵树。,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;,孩子表示法举例,* 便于涉及孩子的操作；求双亲不方便； * 采用同构的结点，空间浪费。,孩子链表存储表示（链式存储）,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;,孩子链表存储表示举例,* 便于涉及孩子的操作； * 求结点的双亲时不方便。,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; /值为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 / 递归删除第i号结点及其子树 ,Status delete(Ctree ,三.孩子兄弟表示法 -树的二叉树表示法(二叉链表示法),/-树的二叉链表(孩子兄弟)存储表示- typedef struct CSNode ELemType data; struct CSNode *firstchild,*nextsibling; CSNode, *CSTree;,孩子兄弟表示法示例：,6.4.2 森林与二叉树的转换 一.森林转换成二叉树,如果F=T1,T2, ,Tm是森林,则可按如下规则转换成一棵二叉树B=(root,LB,RB)。 (1)若F为空，即m=0,则B为空树； (2)若F非空，即m0，则B的根root即为森林中第一棵树的根ROOT(T1)； B的左子树LB是从T1中根结点的子树森林F1=T11,T12, ,T1m1转换而成的二叉树; 其右子对RB是从森林F=T2,T3, ,Tm 转换而成的二叉树.,二. 二叉树转换成森林,如果B=(root,LB,RB)是一棵二叉树,则可按如下规则转换成森林F=T1,T2, ,Tm： (1)若B为空，则F为空； (2)若B非空，则F中第一棵树T1的根ROOT(T1)即为二叉树B的根root； T1中的根结点的子树森林 F1是由B的左子树LB转换而成的森林; F中除T1之外其余树组成的森林F=T2,T3, ，Tm是由B的右子树RB转换而成的森林。,6.4.3 树和森林的遍历,树的两种遍历方法： 一、先根遍历： （1）访问树的根结点； （2）依次先根遍历每棵子树。 R A D E B C F G H K 二、后根遍历： （1）依次后根遍历每棵子树。 （2）访问树的根结点； D E A B G H K F C R,森林的两种遍历方法：,一、先序遍历森林： 若森林非空，则 （1）访问森林中第一棵树的根结点； （2）先序遍历第一棵树的根结点的子树森林； （3）先序遍历除去第一棵树之后的森林。 二、中序遍历森林： 若森林非空，则 （1）中序遍历第一棵树的根结点的子树森林； （2）访问森林中第一棵树的根结点； （3）中序遍历除去第一棵树之后的森林。,6.6 赫夫曼树及其应用 6.6.1最优二叉树(赫夫曼树),路径长度: 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径上的分支数目称做路径长度。 树的路径长度: 树的路径长度是从树根到每一结点的路径长度之和。 树的带权路径长度: 树的带权路径长度为树中所有叶子结点(k)的带权路径长度kk之和, 通常记作： n WPL= kk。 k=1,最优二叉树 或赫夫曼(Huffman)树的定义,假设有n个权值1, 2, , n，试构造一棵有n个叶子结点的二叉树,每个叶子结点带权为i, 则其中： 带权路径长度WPL最小的二叉树称做 最优二叉树 或赫夫曼树.,例1：下面三棵二叉树的四个叶子结点a,b,c,d的权值为7、5、2、4,(a)WPL=7x2+5x2+2x2+4x2 = 36 (b)WPL=7x3+5x3+2x1+4x2 = 46 (c)WPL=7x1+5x2+2x2+4x2 = 35,例2 最佳判定方法(p.144) (a)WPL=10x4+30x4+40x3+15x2+5x1=315 (b)WPL=5x3+15x3+40x2+30x2+10x2=220,10,70,90,e,c,5,40,15,b,a,30,60,d,80,N,N,N,N,Y,Y,Y,Y,Y,构造赫夫曼树的算法思想,(1) 根据给定的n个权值w1,w2, ,wn构成n棵二叉树的集合F=T1,T2, ,Tn其中每棵二叉树Ti中只有一个带权为Wi的根结点,其左右子树均空. (2) 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左.右子树根结点的权值之和. (3) 在F中删除这两棵树,同时将新得到的二叉树加入F中. (4) 重复(2)和(3),直到F只含一棵树为止.这棵树便是赫夫曼树.,构造赫夫曼树举例,6.6.2 赫夫曼编码 赫夫曼树中没有度为1的结点-严格的二叉树,/-夫曼树和赫夫曼编码的存储表示- typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; /动态分配数组存储赫夫曼树 typedef char *HuffmanCode; /动态分配数组存储赫夫曼编码表,求赫夫曼编码的算法如下:,Void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) /w存放n个字符的权值(均0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC. if(n=1) return; m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /0号单未用 for(p=HT,i=1;i=n;+i,+p,+w) *p=*w,0,0,0; for(;i=m;+i,+p) *p=0,0,0,0;,求赫夫曼编码的算法（续一）:,for(i=n+1;i=m;+i) /建赫夫曼树 /在HT1i-1选择parent为0且weight最小的两个结点, / 其序号分别为s1和s2. select(HT,i-1,s1,s2); HTs1.parent=i;HTs2.parent=i; HTi.lchild=s1;HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; /-从叶子到根逆向求每个字符的赫夫曼编码- Hc=(HffmanCode)malloc(n+1*sizeof(char *); /分配n个字符编码的头指针向量 cd=(char *)malloc(n*sizeof(char);/分配求编码的工作空间 cdn-1=“/0“; /编码结束符.,求赫夫曼编码的算法（续二）:,for(i=1;i=n;+i) /逐个字符求赫夫曼编码 start=n-1; /编码结束符位置 for(c=i,f=HTi;f!=0;c=f,f=Htf.parent) /从叶子至根逆向求编码 if(HTf.lchild=c) cd-start=“0“; else cd-start=“1“; Hci=(char *)malloc(n-start)*sizeof(char); /为第i个字符编码分配空间 strcpy(HCi, /释放工作空间 /HuffanCoding,求赫夫曼编码的算法如下:,/-无栈非递归遍历赫夫曼树,求赫夫曼编码 HC=(HuffmanCode)malloc(n+1)*sizeof(char *); p=m;cdlen=0; for(i=1;i=m;+i) HTi.weight=0; /遍历赫夫曼树时用作结点状态标志 while(p) if(HTp.weight=o) /向左 Htp.weight=1; if(HTp.lchild!=0)p=HTp.lchild;cdcdlen+=“0“; else if(HTp.rchild=0)/登记叶子结点的字符的编码 HCp=(char *)malloc(cdlen+1) *sizeof(char); cdcdlen=“0“;strcpy(HCp,cd);/复制编码(串) ,无栈非递归遍历赫夫曼树, 求赫夫曼编码,else if (HTp.weight=1) /向右 HTp.weight=2; if (HTp.rchild!=0)p=HTp.rchild; cdcdlen+=“1“; else /HTp.weight=2,退回 HTp.weight=0;p=HTp.parent;-cdlen; /退到父结点,编码长度减1 /else /while,例6-2 八种字符,其频率分别为: 0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,6.8 树的计数,称二叉树T和T相似是指:二者都为空树或者二者均不为空树,且它们的左右子树分别相似. 称二