创建哈夫曼树

栏目: 数据库 · 发布时间: 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);

}

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

查看所有标签

猜你喜欢:

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

法律论证理论

法律论证理论

罗伯特·阿列克西 / 舒国滢 / 中国法制出版社 / 2002-12-01 / 30.00

阿列克西的著作探讨的主要问题是如法律裁决之类的规范性陈述如何以理性的方式证立。阿列克西将规范性陈述的证立过程看作实践商谈或“实践言说”,而将法律裁决的证立过程视为“法律言说” 。由于支持法律规范的法律商谈是普遍实践言说的特定形式,所以法律论证理论应当立基于这种一般理论。 在阿列克西看来,如果裁决是理性言说的结果,那么这一规范性陈述就是真实的或可接受的。其基本观念在于法律裁决证立的合理性取决于......一起来看看 《法律论证理论》 这本书的介绍吧!

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

URL 编码/解码
URL 编码/解码

URL 编码/解码

SHA 加密
SHA 加密

SHA 加密工具