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