霍夫曼编码 - 段错误 11

Question

好的，我已经尝试着自己制作Huffman编码，但是当我试图使用递归方法打印每个字母对应的编码时出现了问题。

(到这一步，我已经创建了一个二叉树，并且根节点不为空) 每个节点都有一个值，如果它是一个叶子节点，它还有一个字母，所以我开始逐个节点向下遍历树，但在递归方法中，似乎节点忘记了自己是谁，我也不知道怎么回事，我尝试了很多次。:S

递归方法是createCode(Node* actual, string actualCode);

代码如下：

#include <iostream>
#include <fstream>
#include <stdio.h>
#include <string>
#include <queue>
using namespace std;

#define MAX_VALUE 256
int frequencies[MAX_VALUE] = {0};

struct Node {
    int value;
    char letter;
    struct Node *Left, *Right;
}*root=NULL, *temp, *left_temp, *right_temp;

struct CompareNode : public std::binary_function<Node*, Node*, bool> {
    bool operator()(const Node* lhs, const Node* rhs) const {
        if (lhs->value == rhs->value)
            return lhs->letter > rhs->letter;
        else
            return lhs->value > rhs->value;
    }
};

void createCode(Node* actual,string actualCode) {
    if (actual->Left == NULL && actual->Right == NULL) {
        cout << "For: " << actual->letter << " is " << actualCode << endl;
    }
    else {
        if (actual->Left) {
            createCode(actual->Left, actualCode + "0");
        }
        if (actual->Right) {
            createCode(actual->Right, actualCode + "1");
        }
    }
}

void createTree() {
    priority_queue<Node*, vector<Node*>, CompareNode> que;

    for (int x = 0; x < MAX_VALUE; x++) {
        if (frequencies[x] > 0) {
            temp = new Node;
            temp->value = frequencies[x];
            temp->letter = char(x);
            que.push(temp);
        }
    }

    while (que.size() > 1) {
        temp = new Node();
        temp->Left = que.top();
        que.pop();
        temp->Right = que.top();
        que.pop();
        temp->value = temp->Left->value + temp->Right->value;
        temp->letter = NULL;
        que.push(temp);
    }

    root = que.top();
    que.pop();
}

void fillArray(int argc, char *argv[]) {
    string line;
    const char* ptr;

    ifstream myFile(argv[argc - 1]);
    if (myFile.is_open()) {
        while (myFile.good()) {
            getline(myFile,line);

            if (line.length() != 0) {
                ptr = &line.at(0);

                while (*ptr != '\0')
                    ++frequencies[*ptr++];
            }
        }
    }
    else
        cout << "The file could not be open.";
}

int main(int argc, char *argv[]) {
    fillArray(argc, argv);

    createTree();

    createCode(root, "");
    return 0;
}

这是示例树（我尝试上传图像，但由于我是新用户，无法实现）： 二叉树图像 以下是输出结果：

For: a is 0
For:   is 10
Segmentation fault: 11

请帮忙 :(

- Jordan Cortes Guzman

---

如果一个节点只有一个子节点（这在Huffmann树中“不应该”发生），createChild会崩溃，并尝试访问另一个子节点。 - John Dvorak

@JanDvorak: 很好的发现。关键在于，在这种情况下，崩溃会发生在createCode函数中，而actual将为NULL。 - David Schwartz

@EdS。（到这一步，我已经创建了一个二叉树，而且根节点不为空） - John Dvorak

@JanDvorak：没错，但由于OP无法推断问题的原因，我对接受该声明持谨慎态度。通常人们认为他们正在做正确的事情，但当然他们并没有，这就是为什么他们来到这里的原因。示例不应省略可能相关的细节。此外，再次强调，那段代码甚至无法编译。 - Ed S.

@EdS。我可以写一个“错误在你的其他代码中”的答案。 - John Dvorak

Answer 1

在创建推入队列的Node时，您需要将Left和Right指针初始化为NULL：

if (frequencies[x] > 0) {
    temp = new Node;
    temp->Left = NULL;
    temp->Right = NULL;
    temp->value = frequencies[x];
    temp->letter = char(x);
    que.push(temp);
}

如果没有明确的初始化，这些指针将具有不确定的值，并且通常不是NULL，因此在createCode中，您正在取消引用无效的指针。

- Daniel Fischer