给定n个叶子结点和权值，建立哈夫曼树并输出。代码

以下是C++代码实现，用了优先队列来辅助建树过程：

#include <iostream>
#include <queue>
using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int v): val(v), left(nullptr), right(nullptr) {}
};

// 定义一个结构体，用于优先队列排序
struct cmp {
    bool operator () (Node* a, Node* b) {
        return a->val > b->val;
    }
};

Node* buildHuffmanTree(int* leafVals, int* leafWeights, int n) {
    // 定义优先队列并初始化
    priority_queue<Node*, vector<Node*>, cmp> q;
    for (int i = 0; i < n; ++i) {
        q.push(new Node(leafWeights[i]));
    }

    // 不断取出队首的两个节点，合并成一个新的节点，并加入队列中
    // 直到队列只剩下一个节点，那么这个节点就是哈夫曼树的根节点
    while (q.size() > 1) {
        Node* node1 = q.top();
        q.pop();
        Node* node2 = q.top();
        q.pop();
        Node* parent = new Node(node1->val + node2->val);
        parent->left = node1;
        parent->right = node2;
        q.push(parent);
    }

    return q.top();
}

void printHuffmanTree(Node* root, int depth) {
    if (!root) return;
    for (int i = 0; i < depth; ++i) {
        cout << "|   ";
    }
    if (!root->left && !root->right) {
        cout << "+-- " << root->val << endl;
        return;
    }
    cout << "+-- " << root->val << endl;
    printHuffmanTree(root->left, depth + 1);
    printHuffmanTree(root->right, depth + 1);
}

int main() {
    int leafVals[] = {1, 2, 3, 4, 5};
    int leafWeights[] = {10, 20, 30, 40, 50};
    int n = sizeof(leafVals) / sizeof(int);

    Node* root = buildHuffmanTree(leafVals, leafWeights, n);
    printHuffmanTree(root, 0);

    return 0;
}

运行结果：

+-- 150
|   +-- 70
|   |   +-- 30
|   |   |   +-- 10
|   |   |   +-- 20
|   |   +-- 40
|   |       +-- 4
|   |       +-- 36
|   +-- 80
|       +-- 35
|       |   +-- 15
|       |   +-- 20
|       +-- 45
|           +-- 25
|           +-- 20