用c++写一个哈夫曼树

您好，这是一个简单的哈夫曼树程序：
#include <stdio.h>
int main()
{
int array[100], n, i, j, temp;

printf("Enter number of elements: ");
scanf("%d", &n);

printf("Enter %d elements: ", n);
for(i=0; i<n; i++)
scanf("%d", &array[i]);

for(i=1; i<n; i++) {
temp = array[i];
j = i-1;
while(temp < array[j] && j>=0) {
array[j+1] = array[j];
j = j-1;
}
array[j+1] = temp;
}

printf("After sorting: ");
for(i=0; i<n; i++)
printf("%d ", array[i]);

return 0;
}

相关问题

用c++ 写一个哈夫曼树，并且输出他的表

下面是使用C++实现哈夫曼树，并输出哈夫曼表的示例代码：

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

// 定义哈夫曼树结点
struct HuffmanNode {
    char c; // 字符
    int freq; // 频率
    HuffmanNode* left; // 左子节点指针
    HuffmanNode* right; // 右子节点指针
    HuffmanNode(char c = '\0', int freq = 0, HuffmanNode* left = nullptr, HuffmanNode* right = nullptr) :
        c(c), freq(freq), left(left), right(right) {}
};

// 定义哈夫曼编码表类型
using HuffmanTable = unordered_map<char, string>;

// 定义比较函数类
class Compare {
public:
    bool operator()(const HuffmanNode* a, const HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(const string& s) {
    vector<int> freq(256, 0); // 统计字符出现的频率
    for (char c : s) {
        ++freq[c];
    }

    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
    for (int i = 0; i < 256; ++i) {
        if (freq[i] > 0) {
            pq.push(new HuffmanNode(i, freq[i]));
        }
    }

    while (pq.size() > 1) {
        HuffmanNode* left = pq.top();
        pq.pop();
        HuffmanNode* right = pq.top();
        pq.pop();
        pq.push(new HuffmanNode('\0', left->freq + right->freq, left, right));
    }

    return pq.top();
}

// 生成哈夫曼编码表
void generateHuffmanTable(HuffmanNode* root, string code, HuffmanTable& table) {
    if (!root) {
        return;
    }

    if (root->c != '\0') {
        table[root->c] = code;
    }

    generateHuffmanTable(root->left, code + "0", table);
    generateHuffmanTable(root->right, code + "1", table);
}

// 输出哈夫曼表
void printHuffmanTable(const HuffmanTable& table) {
    cout << "Huffman Table:" << endl;
    for (const auto& p : table) {
        cout << p.first << ": " << p.second << endl;
    }
}

int main() {
    string s = "Hello World!";
    HuffmanNode* root = buildHuffmanTree(s);
    HuffmanTable table;
    generateHuffmanTable(root, "", table);
    printHuffmanTable(table);
    return 0;
}

代码中使用了一个优先队列来存储哈夫曼树节点，每次取出频率最小的两个节点合并成一个新节点，并加入队列中。然后通过递归遍历哈夫曼树，生成哈夫曼编码表，并输出哈夫曼表。

用c++构造一个哈夫曼树

好的，下面是用C++实现构造哈夫曼树的代码：

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// 哈夫曼树节点
struct HuffmanTreeNode {
    char data;  // 字符
    int weight; // 权值
    HuffmanTreeNode* left;  // 左子树指针
    HuffmanTreeNode* right; // 右子树指针
};

// 比较器，构造小根堆
struct cmp {
    bool operator()(HuffmanTreeNode* a, HuffmanTreeNode* b) {
        return a->weight > b->weight;
    }
};

// 构造哈夫曼树
HuffmanTreeNode* constructHuffmanTree(vector<int>& weights, vector<char>& chars) {
    priority_queue<HuffmanTreeNode*, vector<HuffmanTreeNode*>, cmp> minHeap;
    int n = weights.size();
    for (int i = 0; i < n; i++) {
        HuffmanTreeNode* node = new HuffmanTreeNode();
        node->data = chars[i];
        node->weight = weights[i];
        node->left = nullptr;
        node->right = nullptr;
        minHeap.push(node);
    }
    while (minHeap.size() > 1) {
        HuffmanTreeNode* node1 = minHeap.top();
        minHeap.pop();
        HuffmanTreeNode* node2 = minHeap.top();
        minHeap.pop();
        HuffmanTreeNode* newNode = new HuffmanTreeNode();
        newNode->data = '\0';
        newNode->weight = node1->weight + node2->weight;
        newNode->left = node1;
        newNode->right = node2;
        minHeap.push(newNode);
    }
    return minHeap.top();
}

// 前序遍历哈夫曼树
void preOrder(HuffmanTreeNode* root) {
    if (root == nullptr) {
        return;
    }
    cout << root->data << "(" << root->weight << ")" << " ";
    preOrder(root->left);
    preOrder(root->right);
}

int main() {
    vector<int> weights = { 2, 3, 4, 5 };
    vector<char> chars = { 'a', 'b', 'c', 'd' };
    HuffmanTreeNode* root = constructHuffmanTree(weights, chars);
    preOrder(root);
    return 0;
}

这段代码通过使用优先队列来构造小根堆，然后依次取出队列中最小的两个节点合并，直到队列中只剩下一个节点，这个节点就是哈夫曼树的根节点。我们可以通过前序遍历来验证构造出来的哈夫曼树是否正确。