赫夫曼二叉树 数据结构作业题

#include<stdio.h> #include<malloc.h> #define new_node (struct node*)malloc(sizeof(struct node)) struct node { char simbol; float weight; struct node *left; struct node *right; }; struct node *root[25]; //根节点集合 int root_num = -1; //根节点个数 char code[20]; //前缀码序列 int i,j; //循环控制变量 struct node *min_root() { struct node *min; min = root[0]; j=0; for(i=0;i<=root_num;i++) if(root[i]->weight < min->weight) {min = root[i]; j=i;} root[j] = root[root_num--]; //删除最小节点 return min; } void visit(struct node *p) { if(p->left != NULL) { code[j++] = '0'; visit(p->left); code[j++] = '1'; visit(p->right); } else { printf("%c : ",p->simbol); puts(code); } code[j--]=0; } void main() { struct node *p; char simbol; float weight; printf("请输入:\n"); printf("输入格式为符号 权值(结束请输入@ 任意数字)：\n"); while(1) //输入根节点 { scanf("%c %f",&simbol,&weight); getchar(); if(simbol == '@') break; p = new_node; p->simbol = simbol; p->weight = weight; p->left = NULL; p->right = NULL; root[++root_num] = p; } while(root_num>0) //生成赫夫曼二叉树 { p=new_node; p->left = min_root(); p->right = min_root(); p->weight = p->left->weight + p->right->weight; root[++root_num] = p; //根节点指针放入根节点指针集合 } j=0; printf("前缀：\n"); visit(p); //访问赫夫曼二叉树，输出前缀码 }