[OD E 100] 生成哈夫曼树

题目

题目描述
给定长度为 n 的无序的数字数组，每个数字代表二叉树的叶子节点的权值，数字数组的值均大于等于 1 。请完成一个函数，根据输入的数字数组，生成哈夫曼树，并将哈夫曼树按照中序遍历输出。

为了保证输出的二叉树中序遍历结果统一，增加以下限制:又树节点中，左节点权值小于等于右节点权值，根节点权值为左右节点权值之和。当左右节点权值相同时，左子树高度高度小于等于右子树。

注意: 所有用例保证有效，并能生成哈夫曼树提醒:哈夫曼树又称最优二叉树，是一种带权路径长度最短的一叉树。

所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为 0 层，叶结点到根结点的路径长度为叶结点的层数)

输入描述
例如：由叶子节点

5 15 40 30 10 

生成的最优二叉树如下图所示，该树的最短带权路径长度为

40 * 1 + 30 * 2 + 15 * 3 + 5 * 4 + 10 * 4 = 205

输出描述
输出一个哈夫曼的中序遍历数组，数值间以空格分隔

示例1

输入
5
5 15 40 30 10

输出

40 100 30 60 15 30 5 15 10

思路（用到的知识点）

1. 哈夫曼树就是最优二叉树（越大的节点越靠近根）
2. 构造哈夫曼树的方法：
   • 每个节点作为只有一个节点的树，所有的节点是一个森林
   • 取出根最小的两个树，他们的根的和作为他们的父节点
   • 把这个父节点加入原来节点的森林
   • 继续循环执行上面两步，直到森林中只有一棵树，这个树就是我们构造的哈夫曼树
3. 中序遍历的顺序（左-中-右）
4. priroty_queue的构造

   [1] 模板三个参数1）元素的类型2) 组织元素的结构体，默认是vector3) 比较大小的函数对象，默认是less（大顶对）
   [2] 模板的第三个参数：1）要么是个仿函数类型2）要么是lambda类型，此时要把lambda对象作为初始化参数传入
   

代码

#include <iostream>
#include <queue>
#include <string>using namespace std;class Node
{
public:int val;Node *left;Node *right;int height;Node(int v) : val(v){}
};// struct Compare
// {
//     bool operator()(const Node *a, const Node *b)
//     {
//         if (a->val != b->val)
//         {
//             return a->val > b->val;
//         }
//         else
//         {
//             return a->height > b->height;
//         }
//     }
// };auto compare = [](const Node *a, const Node *b)
{if (a->val != b->val){return a->val > b->val;}else{return a->height > b->height;}
};void inorder_traversal(Node *root, string &str)
{if (!root){return;}inorder_traversal(root->left, str);str += to_string(root->val);str += ' ';inorder_traversal(root->right, str);
}int main()
{int n;cin >> n;// priority_queue<Node *, vector<Node *>, Compare> pq;priority_queue<Node *, vector<Node *>, decltype(compare)> pq(compare);int item;while (n-- > 0){cin >> item;Node *tmp = new Node(item);pq.push(tmp);}int height = 1;while (pq.size() != 1){Node *pstNode1 = pq.top();pq.pop();Node *pstNode2 = pq.top();pq.pop();Node *parent = new Node(pstNode1->val + pstNode2->val);parent->height = height++;parent->left = pstNode1;parent->right = pstNode2;pq.push(parent);}Node *root = pq.top();string ans;inorder_traversal(root, ans);ans.pop_back();cout << ans << endl;return 0;
}