哈夫曼树

代码

#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;
}

截图