哈夫曼树的建立（根据输入的权值，建立一棵哈夫曼树）

#include<iostream.h> #include<stdio.h> #define n 7 #define m 2*n-1 #define maxval 999 typedef struct hufmtree { float weight; int lchild,rchild,parent; }hufmtree; void creathufmtree(hufmtree *tree) { int i,j,p1,p2; float small1,small2,f; for(i=0;i<=m;i++) { tree[i].parent=0; tree[i].lchild=0; tree[i].rchild=0; tree[i].weight=0.0; } for(i=1;i<=n;i++) { cout<<"输入权值："; cin>>f; tree[i].weight=f; } for(i=n+1;i<=m;i++) { p1=0; p2=0; small1=maxval; small2=maxval; for(j=1;j<=i-1;j++) if(tree[j].parent ==0) if(tree[j].weight<small1) { small2=small1; small1=tree[j].weight; p2=p1; p1=j; } else if(tree[j].weight<small2) { small2=tree[j].weight; p2=j; } tree[p1].parent=i; tree[p2].parent=i; tree[i].lchild=p1; tree[i].rchild=p2; tree[i].weight=tree[p1].weight+tree[p2].weight ; } } void print_hufmtree(hufmtree *tree) { int i; printf("哈夫曼循环：\n"); printf("节点序号 双亲节点 左孩子 右孩子 权值\n"); for( i=m;i>=1;i--) { printf("%d",i); printf("%15d",tree[i].parent); printf("%10d",tree[i].lchild); printf("%10d",tree[i].rchild ); printf("%13.2f\n",tree[i].weight); } } void hafcode( hufmtree *tree) { int code[n+1][n+1]; int i,j,f,c; for(i=1;i<=n;i++) { j=n; f=tree[i].parent; c=i; while(f!=0) { if(tree[f].rchild==c)code[i][j]=1; else code[i][j]=0; code[i][0]=j; j--; c=f; f=tree[f].parent; } } cout<<"\n"; cout<<"编码为：\n"; for(i=1;i<=n;i++) { cout<<"序号: "<<i<<" "<<"权值："<<tree[i].weight <<" "; for(j=code[i][0];j<=n;j++) cout<<code[i][j]; cout<<"\n"; } } main() { hufmtree tree[m+1]; creathufmtree(tree); print_hufmtree(tree); hafcode(tree); return 0; }