④树的带权路径长度WPL(WeightedPathLengthofTree)树中所有叶子结点的带权路径长度之和，通常记为：⑤哈夫曼树(最优二叉树)设二叉树具有n个带权值的叶子结点,那么从根结点到各个叶子结点的路径长度与相应结点权值的乘积的和,叫做二叉树的带权路径长度。具有最小带权路径长度的二叉树称为哈夫曼树。<602.构造哈夫曼树(哈夫曼算法)由给定的n个权值{W1,W2,...,Wn},构造n棵只有一个叶子结点的二叉树,从而得到一个二叉树的集合F={T1,T2,...,Tn};在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树,这棵新的二叉树根结点的权值为其左、右子树根结点权值之和;在集合F中删除作为左、右子树的两棵二叉树,并将新建立的二叉树加入到集合F中;重复(2)、(3)两步,当F中只剩下一棵二叉树时,这棵二叉树便是所要建立的哈夫曼树。给定权值w=(1,3,5,7)来构造一棵哈夫曼树。3.哈夫曼编码前缀编码任一字符的编码都不是另一个字符的编码的前缀。4.哈夫曼编码算法的实现voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(p=HT,i=1;i<=n;++i;++p;++w)*p={*w,0,0,0};for(;i<=m;++i)*p={0,0,0,0};for(i=n+1;i<=m;i++){select(HT,i-1,s1,s2);//在HT[1..i-1],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=(HuffmanCode)malloc((n+1)*sizeof(char*));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].parent;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));strcpy(HC[i],&cd[start]);}free(cd);HC=malloc(…);cd=malloc(…);p=m;cdlen=0;for(i=1;i<=m;++i)HT[i].weight=0;while(p){if(HT[p].weight==0){//向左HT[p].weight=1;if(HT[p].lchild!=0){p=HT[p].lchild;cd[cdlen++]=‘0’;}elseif(HT[p].rchild==0){HC[p]=(char*)malloc((cdlen+1)*sizeof(char));cd[cdlen]=‘\0’;strcpy(HC[p],cd);}}elseif(HT[p].weight==1){//向右HT[p].weight=2;if(HT[p].rchild!=0){p=HT[p].rchild;cd[cdlen++]=‘1’;}else{HT[p].weight=0;p=HT[p].parent;--cdlen;}}例1:假设二叉树采用二叉链存储结构存储,试设计一个算法,输出一棵给定二叉树的所有叶子结点。解：输出一棵二叉树的所有叶子结点的递归模型f()如下：f(b)：不做任何事件若b=NULLf(b)：输出b结点的data域若b为叶子结点f(b)：f(b->lchild);f(b->rchild)其他情况voidDispLeaf(BiTreeb){if(b!=NULL){if(b->lchild==NULL&&b->rchild==NULL)printf("%c",b->data);else{DispLeaf(b->lchild);DispLeaf(b->rchild);}}}例2:求高度BiTreeDepth(b)求二叉树的高度的递归模型f()如下：f(NULL)=0f(b)=MAX{f(b->lchild),f(b->rchild)}+1其他情况对应的算法如下：intBiTreeDepth(BiTreeb){in