内容简介:创建哈夫曼树
二叉树的路径和?
所有叶子节点路径的总和。
什么是哈夫曼树?
路径和最短的二叉树
如何构造最优二叉树,也就是哈夫曼树
哈夫曼树的构建过程?
1.给出一个数组,以每个元素为基础,创建一个叶子节点数组。
2.从中找出权值最小的两个节点,构建一棵树。这棵树的权值等于两个节点权值之和。左子树等于权值最小的那个节点,右子树等于权值次小的那个节点。
3.将该树的根放入节点数组中原来权值最小的那个位置
4.不断执行2-3步骤,最终得到一棵哈夫曼树。
编程要点:找出最小的那个节点,再找出权值次小的那个节点。
代码实现过程:
#include<stdio.h> #include<stdlib.h> //二叉树的节点结构定义 struct _tree_node { //用来存放数据 int data; //存放左子树地址的指针 struct _tree_node *left_tree; //存放右子树地址的指针 struct _tree_node *right_tree; }; //定义类型 typedef struct _tree_node t_tree_node; //创建结点 t_tree_node *make_node(int data) { //分配一个内存 t_tree_node *tree_node_temp=malloc(sizeof(t_tree_node)); //将数据放入该结点,且左右子树设为空 tree_node_temp->data=data; tree_node_temp->left_tree=NULL; tree_node_temp->right_tree=NULL; //将该内存的首地址返回 return tree_node_temp; } //结点插入到树里 t_tree_node *insert_tree_node(t_tree_node *root,t_tree_node *newnode) { //如果根结点为空,则插入根节点 if(root==NULL) //第二次进来则相当于if(root->right_tree==NULL) { root=newnode; return root; } else { //如果数据大于根节点的数据则放到右边 if(newnode->data>root->data) { root->right_tree=insert_tree_node(root->right_tree,newnode); } else { root->left_tree=insert_tree_node(root->left_tree,newnode); } } return root; } t_tree_node *del_tree(t_tree_node *root) { //如果根非空 if(root) { //先删左子树 root->left_tree=del_tree(root->left_tree); //再删右子树 root->right_tree=del_tree(root->right_tree); //才是除根 free(root); root=NULL; return root; } } //中序遍历打印节点 void print_tree(t_tree_node *root) { if(root) { print_tree(root->left_tree); printf("%d ", root->data); print_tree(root->right_tree); } } //二叉树的深度 int depth(t_tree_node *root) { if(root==NULL) { return 0; } else { int ldepth=depth(root->left_tree);//40这个节点,左右子树为空 int rdepth=depth(root->right_tree);//60这个节点, if(ldepth>rdepth) { return ldepth+1; } else { return rdepth+1; } } } //构建哈弗曼树 t_tree_node *creat_huffman(int a[],int length) { //定义一个节点指针的数组 t_tree_node **array=malloc(length*sizeof(t_tree_node *)); //定义一个节点用来创建树 t_tree_node *q; int j; int zuixiao_idx,cixiao_idx; //创建节点数组 int i; for (i=0;i<length;i++) { array[i]=malloc(sizeof(t_tree_node)); array[i]->data=a[i]; array[i]->left_tree=NULL; array[i]->right_tree=NULL; } //比较的循环,次数是数组长度-1 for(i=0;i<length-1;i++) { j=0; //找出一个非空节点 while(array[j]==NULL) { j++; } //第一个非空节点 zuixiao_idx=j; for(j=0;j<length;j++) { if(array[j]&&array[j]->data<array[zuixiao_idx]->data) { zuixiao_idx=j; } } j=0; //找出一个非空节点 while(array[j]==NULL||j==zuixiao_idx) { j++; } cixiao_idx=j; //和其它节点对比 for (j=0;j<length;j++) { if(array[j]&&array[j]->data<array[cixiao_idx]->data&&j!=zuixiao_idx) { cixiao_idx=j; } } q=malloc(sizeof(t_tree_node)); q->data=array[zuixiao_idx]->data+array[cixiao_idx]->data; q->left_tree=array[zuixiao_idx]; q->right_tree=array[cixiao_idx]; //创建之后放到原来权值最小节点的位置 array[zuixiao_idx]=q; array[cixiao_idx]=NULL; } free(array); array=NULL; return q; } //带权路径和 int lengthsum(t_tree_node *root,int len) { if(root==NULL) { return 0; } else if(root->left_tree==NULL&&root->right_tree==NULL) { return root->data*len; } else { return lengthsum(root->left_tree,len+1)+lengthsum(root->right_tree,len+1); } } int main(void) { //创建一棵树 t_tree_node *root=NULL; // //定义一个临时变量,用来存储输入的数据 // int input; // //从键盘输入多个数,输入-1来结束输入 // while(scanf("%d",&input)&&input!=-1) // { // //将创建的节点插入树里 // root=insert_tree_node(root,make_node(input)); // } int a[12]={85,63,27,89,64,74,13,15,67,68,94,46}; root=creat_huffman(a,12); //遍历节点 print_tree(root); //删除一棵树 root=del_tree(root); }
以上所述就是小编给大家介绍的《创建哈夫曼树》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。