前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >哈夫曼树

哈夫曼树

作者头像
AI那点小事
发布2020-04-20 12:34:02
3960
发布2020-04-20 12:34:02
举报
文章被收录于专栏:AI那点小事

代码

代码语言:javascript
复制
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

typedef struct node{
	struct node* lchild;
	struct node* rchild;
	int weight;
	node(int w,struct node* l,struct node* r){
		this->weight = w;
		this->lchild = l;
		this->rchild = r;
	}
}TreeNode;

struct cmp{
	bool operator()(TreeNode* node1,TreeNode* node2){
		return node1->weight > node2->weight;
	}
};


TreeNode* Create_HuffmanTree(int* weights,int size)
{
	priority_queue<TreeNode*,vector<TreeNode*>,cmp> q;
	for(int i = 0 ; i < size ; i++){
		TreeNode* node = new TreeNode(weights[i],NULL,NULL);
		q.push(node);
	}
	TreeNode* node1,*node2;
	while(q.size() != 1){
		node1 = q.top();
		q.pop();
		node2 = q.top();
		q.pop();
		TreeNode* node = new TreeNode(node1->weight+node2->weight,node1,node2);
		q.push(node);
	}
	TreeNode* root = q.top();
	q.pop();
	return root;
}

//先序遍历
void PreOrderTraversal(TreeNode* root)
{
	if(root == NULL){
		return;
	}
	cout<<root->weight<<" ";
	PreOrderTraversal(root->lchild);
	PreOrderTraversal(root->rchild);
} 

//中序遍历
void InOrderTraversal(TreeNode* root)
{
	if(root == NULL){
		return;
	}
	InOrderTraversal(root->lchild);
	cout<<root->weight<<" ";
	InOrderTraversal(root->rchild);
} 

//后序遍历
void PostOrderTraversal(TreeNode* root)
{
	if(root == NULL){
		return;
	}
	PostOrderTraversal(root->lchild);
	PostOrderTraversal(root->rchild);
	cout<<root->weight<<" ";
} 

int main()
{
	//初始化 
	int n;
	int* weights; 
	cout<<"请输入树节点个数:"<<endl;
	cin>>n;
	weights = new int[n];
	memset(weights,0,sizeof(weights[0])*n);
	cout<<"请输入树节点权重:"<<endl; 
	for(int i = 0 ; i < n ; i++){
		cin>>weights[i];
	}
	//构造哈夫曼树 
	TreeNode* root = Create_HuffmanTree(weights,n);
	//先序遍历哈夫曼树
	cout<<"哈夫曼树的先序遍历为:"<<endl;
	PreOrderTraversal(root);
	//中序遍历哈夫曼树
	cout<<endl<<"哈夫曼树的中序遍历为:"<<endl;
	InOrderTraversal(root);
	//后序遍历哈夫曼树
	cout<<endl<<"哈夫曼树的后序遍历为:"<<endl;
	PostOrderTraversal(root);
	
	return 0;
}

截图

在这里插入图片描述
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 代码
  • 截图
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档