将哈夫曼树转化成二叉树-技术方案-@大数据资讯

今晚感觉好爽啊，好久好久没有这种感觉，起床需要点爆发力，做事还需要点动力，给自己都没有下过这么大的决心写代码，帮她却写的很好，我自己都吃惊了。哈哈哈。。。今晚也是帮她写好西邮导航睡不着，那就敲了一下哈夫曼树转化成二叉树的代码，其实理解了真的不难，我定义F为一个二级指针，用它指向结点的地址，创建很简单，输入数据data和权值weight，再把它的左右置为NULL；

初始化话完了，就开始创建二叉树吧，我定义两个变量s1和s2，s1永远标记的是F这个指针数组中节点权值最小的一个，s2则为次小，特别注意，s1和 s2我每次初始化的时候都是放在F[i]!=NULL的结点上，这里用到了我前几次用的方法，利用for空语句循环找到s1和s2，对于如何让找出s1最小s2次小我已经说过了，就再次不用说了；

这里面的关键几步应该是如何把二叉树建立起来，假如说我已经找到小小s1和次小s2了，下面用图好解释：

创建出来就是这个样子了，经过一次创建成为下面这个样子，

循环n-1次之后二叉树就创建成功了，直接进入代码；

[cpp] view plaincopy

#include <iostream>
#include<stdlib.h>
#include<conio.h>
#define null NULL
typedef struct HuffNode{
char data;
int weight;
struct HuffNode *left,*right;
}HuffNode;
HuffNode *CreateHuffman(HuffNode **,int );
void preorder(HuffNode * );
void leafprint(HuffNode *);
void Print(HuffNode *);
HuffNode *CreateHuffman(HuffNode **F,int n){
HuffNode *p;
int i,j;
int k1=0,k2=1;
for(i=0;i<n-1;i++)
{
for(k1=0;k1<n&&F[k1]==null;k1++);
// printf("数据%c,权值%d\n",F[k1]->data,F[k1]->weight);
for(k2=k1+1;k2<n&&F[k2]==null;k2++);
// printf("数据%c,权值%d\n",F[k2]->data,F[k2]->weight);
for(j=k2;j<n;j++)
{
if(F[j])
{
if(F[j]->weight<F[k1]->weight)
{
k2=k1;
k1=j;
}
else if(F[j]->weight<F[k2]->weight&&F[k2])
{
k2=j;
}
}
}
printf("输出最小k1=%d k2=%d\n",k1,k2);
p=(HuffNode *)malloc(sizeof(HuffNode));
p->weight=F[k1]->weight+F[k2]->weight;
p->data='w';
p->left=F[k1];
p->right=F[k2];
F[k1]=p;
F[k2]=null;
Print(F[k1]);
}
return F[k1];
}
void Print(HuffNode *root){
if(root)
{
printf("数据%c,权值%d\n",root->data,root->weight);
Print(root->left);
Print(root->right);
}
}
void leafprint(HuffNode *root){
if(root)
{
if(root->left==NULL&&root->right==NULL)
printf("数据%c，权值%d\n",root->data,root->weight);
leafprint(root->left);
leafprint(root->right);
}
}
int main(int argc, char** argv) {
HuffNode **F;
HuffNode *root;
int n,i;
printf("请你输入节点的个数： ");
scanf("%d",&n);
F=(HuffNode **)malloc(n*sizeof(HuffNode *));
for(i=0;i<n;i++){
fflush(stdin);
F[i]=(HuffNode *)malloc(sizeof(HuffNode));
printf("\n输入第%d个节点的数据，权值: ",i+1);
scanf("%c%d",&F[i]->data,&F[i]->weight);
F[i]->left=F[i]->right=null;
}
root=CreateHuffman(F,n);
printf("\n先序遍历二叉树： \n");
Print (root);
printf("\n遍历叶子结点： \n");
leafprint(root);
return 0;
}

对于如何遍历二叉树先序，中序，后序都可以，随意运行结果

原文链接：http://blog.csdn.net/lotluck/article/details/41996255