数据结构树的讲解

6．4树和森林6.4.1树的存储结构一、双亲表示法（顺序存储）//-----------树的双亲表存储表示----------//#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;intparent;//双亲位置域}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intn;//结点数}PTree;双亲表示法举例RADEFCBGKHR-1A0B0C0D1E1F3G6H6K60123456789数组下标:*便于涉及双亲的操作；*求结点的孩子时需要遍历整棵树。6.4.1树的存储结构二、孩子表示法（顺序存储）#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;intchild1;//第1个孩子位置域intchild2;//第2个孩子位置域......intchildd;//第d个孩子位置域}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intn;//结点数}PTree;孩子表示法举例RADEFCBGKH0123456789数组下标:*便于涉及孩子的操作；求双亲不方便；*采用同构的结点，空间浪费。R1A4B0C6D0E0F7G0H0K023500000000089000000孩子链表存储表示（链式存储）typedefstructCTNode{//孩子结点intchild;structCTNode*next;}*ChildPtr;typedefstruct{TElemTypedata;ChildPtrfirstchild;//孩子链表头指针}CTBox;typedefstruct{CTBoxnodes[MAX_TREE_SIZE];intn,r;//结点数和根的位置}CTree;孩子链表存储表示举例RADEFCBGKH0123456789数组下标:*便于涉及孩子的操作；*求结点的双亲时不方便。RAB/CD/E/FG/H/K/123/45/6/789/T.nodes[];T.n=10;T.r=0;例1:设树T以孩子链表为存储结构,寻找值为x的双亲结点的算法如下:Statusparent(CtreeT,TElemTypex){//当值为x的结点不存在时返回-2;//当值为x的结点为根结点时返回-1,//否则返回x结点的双亲结点的下标值.if(T.nodes[T.r].data==x)return–1;//值为x的结点为根结点;for(i=0;iT.n;i++){p=T.nodes[i].firstchild;while(p&&T.nodes[p-child].data!=x)p=p-next;if(p)return(i);//找到x的双亲结点}return–2;//值为x的结点不存在}例2:删除值为x的结点的第i棵子树的算法delete如下：voiddeletej(Ctree&T,intj){//删除树T的第j号结点及其子树if(!T.nodes[j].firstchild){//删除叶结点for(i=j;iT.n-1;i++){//j号结点后的结点全部前移一位T.nodes[i].data=T.nodes[i+1].data;T.nodes[i].firstchild=T.nodes[i+1].firstchild;}T.n--;}else{while(s=T.nodes[j].firstchild){T.nodes[j].firstchild=s-next;i=s-child;free(s);deletej(T,i);//递归删除第i号结点及其子树}}}Statusdelete(Ctree&T,TElemTypex,inti){//当值为x的结点不存在时返回-2;当值为x的结点为//叶结点或无第i棵子树时返回-1,否则返回1.for(k=0;kT.n;k++)if(T.nodes[k].data==x)break;//找到值为x的结点if(k=T.n)return–2;//值为x的结点不存在p=T.nodes[k].firstchild;j=1;if(!p)return–1;//x结点为叶结点if(i==1){//删除长子时,特殊处理j=p-child;//记住要删除子树的下标T.nodes[k].firstchild=p-next;free(p);}else{while(p-next&&ji-1){p=p-next;j++;}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号结点及其子树return1;}三.孩子兄弟表示法---树的二叉树表示法(二叉链表示法)//-----树的二叉链表(孩子兄弟)存储表示------typedefstructCSNode{ELemTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;RADEFCBGKHR/A/DE//C/H/F/G/B/K//孩子兄弟表示法示例：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）依次先根遍历每棵子树。RADEBCFGHK二、后根遍历：（1）依次后根遍历每棵子树。（2）访问树的根结点；DEABGHKFCRRADEFCBGKH森林的两种遍历方法：一、先序遍历森林：若森林非空，则（1）访问森林中第一棵树的根结点；（2）先序遍历第一棵树的根结点的子树森林；（3）先序遍历除去第一棵树之后的森林。二、中序遍历森林：若森林非空，则（1）中序遍历第一棵树的根结点的子树森林；（2）访问森林中第一棵树的根结点；（3）中序遍历除去第一棵树之后的森林。6.6赫夫曼树及其应用6.6.1最优二叉树(赫夫曼树)路径长度:从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径上的分支数目称做路径长度。树的路径长度:树的路径长度是从树根到每一结点的路径长度之和。树的带权路径长度:树的带权路径长度为树中所有叶子结点(k)的带权路径长度ωkιk之和,通常记作：nWPL=∑ωkιk。k=1最优二叉树或赫夫曼(Huffman)树的定义假设有n个权值{ω1,ω2,…,ωn}，试构造一棵有n个叶子结点的二叉树,每个叶子结点带权为ωi,则其中：带权路径长度WPL最小的二叉树称做最优二叉树或赫夫曼树.例1：下面三棵二叉树的四个叶子结点a,b,c,d的权值为7、5、2、4abcd7524abcd7524cdab7524(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=22010c90ed51540ba30607080NNNNYYYYY107090ec54015ba3060d80NNNNYYYYY构造赫夫曼树的算法思想(1)根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn}其中每棵二叉树Ti中只有一个带权为Wi的根结点,其左右子树均空.(2)在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左.右子树根结点的权值之和.(3)在F中删除这两棵树,同时将新得到的二叉树加入F中.(4)重复(2)和(3),直到F只含一棵树为止.这棵树便是赫夫曼树.构造赫夫曼树举例cdab7524abc2d457abc6d57abcd1176.6.2赫夫曼编码赫夫曼树中没有度为1的结点---严格的二叉树//-----夫曼树和赫夫曼编码的存储表示-------typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树typedefchar**HuffmanCode;//动态分配数组存储赫夫曼编码表求赫夫曼编码的算法如下:VoidHuffmanCoding(HuffmanTree*HT,HuffmanCode*HC,int*w,intn){//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){//建赫夫曼树//在HT[1..i-1]选择parent为0且weight最小的两个结点,//其序号分别为s1和s2.select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}//-----从叶子到根逆向求每个字符的赫夫曼编码-----Hc=(HffmanCode)malloc((n+1*sizeof(char*));//分配n个字符编码的头指针向量cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间cd[n-1]=/0;//编码结束符.求赫夫曼编码的算法（续二）:for(i=1;i=n;++i){//逐个字符求赫夫曼编码start=n-1;//编码结束符位置for(c=i,f=HT[i];f!=0;c=f,f=Ht[f].parent)//从叶子至根逆向求编码if(HT[f].lchild==c)cd[--start]=0;elsecd[--start]=1;Hc[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间strcpy(HC[i],&cd[start]);//从cd复制编码(串)到HC}free(cd);//释放工作空间}//HuffanCoding求赫夫曼编码的算法如下://----------无栈非递归遍历赫夫曼树,求