创建哈夫曼树

栏目: 数据库 · 发布时间: 7年前

内容简介:创建哈夫曼树

二叉树的路径和?

所有叶子节点路径的总和。

什么是哈夫曼树?

路径和最短的二叉树

如何构造最优二叉树,也就是哈夫曼树

哈夫曼树的构建过程?

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);

}

以上所述就是小编给大家介绍的《创建哈夫曼树》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

JavaScript征途

JavaScript征途

朱印宏 / 电子工业出版社 / 2009-9 / 89.00元

《JavaScript征途》是一本学习JavaScript语言的权威书籍,在遵循语言学习的特殊规律基础上精心选材,力争做到统筹、有序,在结构上体现系统性和完整性。同时还重点挖掘JavaScript基于对象的开发精髓及函数式编程两个技术核心。《JavaScript征途》内容全面,由浅入深,包括6篇21章,主要内容包括:JavaScript语言的基本特性,开发简单的JavaScript程序,JavaS......一起来看看 《JavaScript征途》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具