c++实现哈夫曼树建树

可以使用贪心算法实现哈夫曼树建树。具体步骤如下：

1. 将所有权值存储在一个数组中，并将数组按照权值从小到大排序。

2. 取出权值最小的两个元素，建立一个新节点，将这两个元素作为新节点的左右子节点，并将新节点的权值设为这两个元素权值之和。

3. 将新节点插入到数组中，并将原来的两个元素从数组中删除。

4. 重复2、3步骤，直到数组中只剩下一个节点，该节点即为哈夫曼树的根节点。

需要注意的是，在插入新节点时，需要按照权值从小到大的顺序插入，并且如果有多个节点具有相同的权值，应该按照它们在数组中的顺序插入。这样可以保证建立的哈夫曼树是唯一的。

相关问题

请给出哈夫曼树的建树代码

以下是哈夫曼树的 C++ 代码：

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

// 哈夫曼树节点
struct HuffmanNode
{
    int weight;          // 权值
    int parent;          // 父节点下标
    int leftChild;       // 左子节点下标
    int rightChild;      // 右子节点下标
};

// 根据权值比较大小的仿函数
struct HuffmanCmp
{
    bool operator() (HuffmanNode a, HuffmanNode b)
    {
        return a.weight > b.weight;
    }
};

// 建立哈夫曼树
void BuildHuffmanTree(int* weight, int n, HuffmanNode* nodes)
{
    // 创建权值最小的优先队列
    priority_queue<HuffmanNode, vector<HuffmanNode>, HuffmanCmp> q;
    for(int i = 0; i < n; ++i)
    {
        nodes[i].weight = weight[i];
        nodes[i].parent = -1;
        nodes[i].leftChild = -1;
        nodes[i].rightChild = -1;
        q.push(nodes[i]);
    }
    
    // 构建哈夫曼树
    for(int i = 0; i < n-1; ++i)
    {
        // 取出权值最小的2个节点
        HuffmanNode node1 = q.top(); q.pop();
        HuffmanNode node2 = q.top(); q.pop();
        
        // 创建新节点，左右指针分别指向取出的2个节点
        HuffmanNode newNode = {node1.weight + node2.weight, -1, node1.weight < node2.weight ? node1 : node2, node1.weight < node2.weight ? node2 : node1};
        // 设置取出的2个节点的父节点指针
        node1.parent = i + n;
        node2.parent = i + n;
        // 将新节点加入队列
        q.push(newNode);
        
        // 新节点指向父节点
        nodes[i+n] = newNode;
    }
}

int main()
{
    int n = 5;
    int weight[5] = {5, 2, 4, 7, 1};
    HuffmanNode nodes[2*n-1];
    BuildHuffmanTree(weight, n, nodes);

    return 0;
}

给定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