思路：小根堆/排序+贪心+DFS

首先根据哈夫曼树的定义，可以使用贪心的方式构建哈夫曼树，离根节点的距离越远，则该点的权值需要越小，否则会使得带权路径长度增大，而不是最短带权路径长度了。

我们可以使用排序或者一个小根堆来去构建哈夫曼树，每次取出小根堆的最小权值的两个节点，生成他们的父节点，然后将父节点添加进小根堆中，直到堆中元素为1，构造结束。

最终，最后堆中剩下的那个元素，就是整个哈夫曼树的根节点，然后从根节点开始跑一遍DFS的中序遍历即可

JavaScript

const readline = require('readline');

class Node {
    constructor(val, l, r) {
        this.val = val;  // 记录当前节点的权值
        this.l = l;  // 记录当前节点的左节点编号
        this.r = r;  // 记录当前节点的右节点编号
    }
}

function dfs(u, g, res) {
    // 中序遍历函数
    if (u === -1) {
        return;
    }
    let l = g[u].l;
    let r = g[u].r;
    dfs(l, g, res);  // 遍历左子树
    res.push(g[u].val);  // 将当前节点的权值加入中序遍历结果
    dfs(r, g, res);  // 遍历右子树
}

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

rl.question('', (n) => {
    let heap = [];  // 用于构建哈夫曼树的小根堆
    let g = [];  // 存储哈夫曼树的节点
    let res = [];  // 存储中序遍历结果
    rl.question('', (values) => {
        let nums = values.split(' ').map(x => parseInt(x));  // 输入节点的权值
        for (let i = 0; i < n; i++) {
            let x = nums[i];
            heap.push([x, i]);  // 将节点的权值和编号加入小根堆
            g.push(new Node(x, -1, -1));  // 初始化哈夫曼树的节点，左右节点编号均为 -1
        }

        let cnt = n;  // 新生成的节点编号
        while (heap.length > 1) {  // 模拟生成哈夫曼树的过程
            heap.sort((a, b) => a[0] - b[0]);  // 将小根堆排序
            let [x, idx] = heap.shift();  // 取出小根堆中权值最小的节点
            let [y, idy] = heap.shift();  // 取出小根堆中权值次小的节点
            let z = x + y;
            let idz = cnt++;
            heap.push([z, idz]);  // 将新节点的权值和编号加入小根堆
            g.push(new Node(z, idx, idy));  // 将新节点加入哈夫曼树，左右节点编号分别为第一个节点和第二个节点的编号
        }

        dfs(cnt - 1, g, res);  // 从根节点开始中序遍历哈夫曼树
        console.log(res.join(' '));  // 输出中序遍历结果
        rl.close();
    });
});

Python代码

import heapq

def dfs(u, g, res):
    # 递归函数，用于中序遍历哈夫曼树
    if u == -1:
        return
    l, r = g[u][1], g[u][2]
    dfs(l, g, res)  # 遍历左子树
    res.append(g[u][0])  # 将当前节点的权值加入中序遍历结果
    dfs(r, g, res)  # 遍历右子树

n = int(input())  # 输入节点数
heap = []  # 用于构建哈夫曼树的小根堆
g = []  # 存储哈夫曼树的节点
res = []  # 存储中序遍历结果
for i, x in enumerate(map(int, input().split())):
    heapq.heappush(heap, (x, i))  # 将节点的权值和编号加入小根堆
    g.append((x, -1, -1))  # 初始化哈夫曼树的节点，左右节点编号均为 -1

cnt = n  # 新生成的节点编号
while len(heap) > 1:  # 模拟生成哈夫曼树的过程
    x, idx = heapq.heappop(heap)  # 取出小根堆中权值最小的节点
    y, idy = heapq.heappop(heap)  # 取出小根堆中权值次小的节点
    z, idz = x + y, cnt  # 新节点的权值和编号
    cnt += 1
    heapq.heappush(heap, (z, idz))  # 将新节点的权值和编号加入小根堆
    g.append((z, idx, idy))  # 将新节点加入哈夫曼树，左右节点编号分别为第一个节点和第二个节点的编号

dfs(cnt - 1, g, res)  # 从根节点开始中序遍历哈夫曼树
print(*res)  # 输出中序遍历结果

Java代码

import java.util.PriorityQueue;
import java.util.Scanner;

class Node implements Comparable<Node> {
    long weight;       // 权值
    int height;        // 树高度
    Node left, right;  // 左右子树

    public Node() {
        this.height = 1;
        this.left = null;
        this.right = null;
    }

    // 重载小于运算符，用于定义小顶堆中的比较规则
    @Override
    public int compareTo(Node other) {
        if (this.weight != other.weight) {
            return Long.compare(this.weight, other.weight);  // 小顶堆，按照权值升序排列
        } else {
            return Integer.compare(this.height, other.height);  // 权值相同，则树高度升序排序
        }
    }
}

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        PriorityQueue<Node> minHeap = new PriorityQueue<>();

        for (int i = 0; i < n; i++) {
            Node node = new Node();
            node.weight = scanner.nextLong();
            minHeap.offer(node);
        }

        // 生成哈夫曼树，使用小顶堆，每次取出两个最小的节点，合并为一个新节点，再放回去，直到只剩一个节点为止。
        while (minHeap.size() > 1) {
            Node left = minHeap.poll();
            Node right = minHeap.poll();

            Node pnode = new Node();
            pnode.weight = left.weight + right.weight;
            pnode.height = Math.max(left.height, right.height) + 1;
            pnode.left = left;
            pnode.right = right;

            minHeap.offer(pnode);
        }

        Node root = minHeap.poll();
        inorder(root);
    }

    // 中序遍历
    static void inorder(Node node) {
        if (node == null) return;
        inorder(node.left);
        System.out.print(node.weight + " ");
        inorder(node.right);
    }
}

C++代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<long long,long long>PII;
#define x first
#define y second
const int N=1e5+10;
int n,cnt;
struct node{
    long long val,l,r;  //记录当前节点的左节点和右节点，以及当前节点的权值
};
vector<long long>res;  ///记录中序遍历结果
vector<node>g;
void dfs(long long u){  //中序遍历
    if(u==-1)return;
    long long l=g[u].l,r=g[u].r;
    dfs(l);
    res.push_back(g[u].val);
    dfs(r);
}
int main(){
    cin>>n;
    priority_queue<PII,vector<PII>,greater<PII>>heap; //小根堆
    g.resize(n);
    for(long long i=0;i<n;i++){
        long long x;
        cin>>x;
        heap.push({x,i});
        g[i].l=g[i].r=-1;
        g[i].val=x;
    }
    cnt=n;  //新生成的节点编号
    while(heap.size()>1){   //模拟生成哈夫曼树的过程
        auto [x,idx]=heap.top();heap.pop();
        auto [y,idy]=heap.top();heap.pop();
        long long z=x+y,idz=cnt++;
        heap.push({z,idz});
        g.push_back({z,idx,idy});
    }
    dfs(cnt-1);  //从根节点跑一遍中序遍历
    
    for(long long &x:res)cout<<x<<" ";
    return 0;
}

}

题目描述

给定长度为 $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

说明

根据输入，生成哈夫曼树，按照中序遍历返回。所有节点中，左节点权值小于等于右节点权值之和。当左右节点权值相同时左子树高度小于右子树。结果如上图所示。