题目
题目描述
给定长度为 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
思路（用到的知识点）
- 哈夫曼树就是最优二叉树（越大的节点越靠近根）
- 构造哈夫曼树的方法：
- 每个节点作为只有一个节点的树，所有的节点是一个森林
- 取出根最小的两个树，他们的根的和作为他们的父节点
- 把这个父节点加入原来节点的森林
- 继续循环执行上面两步，直到森林中只有一棵树，这个树就是我们构造的哈夫曼树
- 中序遍历的顺序（左-中-右）
- 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;
}
