如何遍历哈夫曼树（通过代码）并打印出每个字母的编码？

Question

我想从我对堆和Huffman代码的了解开始。

在这个项目中，我们使用的是最小堆。倒立的树的顶部部分（或根）存放着最小元素。每当有东西被添加到数组中，所有的东西都会被移动，所以根部总是最小值元素。每当一个元素被删除时，所有的东西都会被重新配置，顶部的元素再次保持最小值。在课堂上，我们学习了一个叫MaxHeap的（模板）类，我把它转换成了MinHeap，没有模板的东西。

我的教授讲解了Huffman编码，但我用这个可视化工具理解得最好。https:/people.ok.ubc.caylucetDSHuffman.html。其思路是使用最小堆，如下：1. 删除两个节点2. 以删除的节点为子节点创建一个新节点。这个节点的频率是两个子节点频率之和.3.将这个新节点添加到最小堆中这个过程重复进行，直到堆中只剩下一个节点（根节点）。接下来，我们找到每个字母的编码。要做到这一点，沿着树向下移动，左移为0，右移为1。向右移动两次，然后向左移动一次，在我的树上，字母 "c "的编码为110（图片链接可以在我的文章底部找到）。

一切都很顺利，直到我需要从根部穿越。我不知道如何通过代码来完成这个任务，所以我试着上网搜索答案，发现了这两个网站。https:/www.geeksforgeeks.orghuffman-coding-greedy-algo-3https:/www.programiz.comdsahuffman-coding

我复制了他们的功能 printCodes() 到我的代码中，但我没有看到它的工作。

当我试着手动往下走时，我得到了两个结果。例如，我试着从根部向左下行，然后用 cout 来查看数值。我以为会看到40, !, e, d; 但当我尝试时，我得到的是乱七八糟的数字和字符（希腊字母，如theta, sigma等）。它变得非常奇怪，因为在207行。yourRoot->left->freq 给我40，但同样的东西在代码的208行给我一个大数。当我向右行驶时，我得到了。Exception thrown: read access violation. yourRoot->right->right->letter was 0xCCCCCCCC.

重申一下 cout << yourRoot->left->freq << endl; 会给我40，但第二次我得到的是一个随机数。我希望连续两次得到相同的输出。我是否应该保留一个指针或指针到指针的地址，以便让 yourRoot 还是什么？

另一个问题是在 createHuffmanTree()如果我把 return root; 在while循环之外，我得到了这个错误，代码根本无法运行。potentially uninitialized local pointer variable 'root' used

这两件事都是奇怪的问题 我认为这与我使用& 和*符号的方式有关。我试着使用这样的东西。

    MinHeap yourHeap = MinHeap(6);
    node *item = newNode(30, 'f');
    yourHeap.Insert(*item);
    item = newNode(20, 'e');
    yourHeap.Insert(*item);
    item = newNode(20, 'd');
    yourHeap.Insert(*item);
    item = newNode(15, 'c');
    yourHeap.Insert(*item);
    item = newNode(10, 'b');
    yourHeap.Insert(*item);
    item = newNode(5, 'a');
    yourHeap.Insert(*item);
    delete item;

这和我用&和*符号一样 yourList[] 我的代码 main()但我想 "保持简单，愚蠢"，避免使用指针，因为我显然有一些问题。

我上传了一个没有任何错误代码的输出，以及一个我希望我的树的样子和我想使用的值的图画 (https:/imgur.comaVpx7Eif). 如果链接不起作用，请告诉我，以便我修复。

到目前为止，我的代码是。

#include <iostream>
using namespace std;
#define MAX_TREE_HEIGHT 20

//exception is thrown if wrong input
class NoMem
{
public:
    NoMem() { cout << "Heap is full\n"; }
};

class OutOfBounds
{
public:
    OutOfBounds() { cout << "Heap is empty\n"; }
};

struct node
{
    int freq;
    char letter;
    struct node *left, *right;
};

// initialize node with frequency and letter
node* newNode(int freq, char letter)
{
    node *temp = new node;
    temp->freq = freq;
    temp->letter = letter;
    temp->left = nullptr;
    temp->right = nullptr;
    return temp;
}

// initialize node using two nodes as children
node* newNode(node& a, node& b)
{
    node *temp = new node;
    temp->freq = a.freq + b.freq;
    temp->letter = '!';
    temp->left = &a;
    temp->right = &b;
    return temp;
}

class MinHeap {
public:
    MinHeap(int MSize)
    {
        MaxSize = MSize;
        heap = new node[MaxSize + 1];
        Size = 0;
    }
    ~MinHeap() { delete[] heap; }
    MinHeap& Insert(node& x);
    MinHeap& Delete(node& x);
    void Display();
    int Size;
private:
    int MaxSize;
    node *heap;
};

MinHeap& MinHeap::Insert(node& x)
{

    if (Size == MaxSize) throw NoMem();
    else
    {
        printf("Inserting '%c' with frequency of %d. ", x.letter, x.freq);
        int i = ++Size;
        while (i != 1 && x.freq < heap[i / 2].freq)
        {
            heap[i] = heap[i / 2];
            i /= 2;
        }
        heap[i] = x;
        Display();
        return *this;
    }
}

MinHeap& MinHeap::Delete(node& x)
{
    if (Size == 0) throw OutOfBounds();
    x.freq = heap[1].freq;  // root has the smallest key
    x.letter = heap[1].letter;
    printf("Deleting '%c' with frequency of %d. ", x.letter, x.freq);
    node y = heap[Size--]; // last element
    int vacant = 1;
    int child = 2; //make child = left child
    while (child <= Size)
    {
        if (child < Size && heap[child].freq > heap[child + 1].freq) ++child;
        // right child < left child
        if (y.freq <= heap[child].freq) break;
        heap[vacant] = heap[child]; // move smaller child
        vacant = child; // new vacant
        child = child * 2; // new child of vacant
    }
    heap[vacant] = y;
    Display();
    return *this;
}

void MinHeap::Display()
{
    printf("Your heap contains: ");
    for (int i = 1; i <= Size; i++)
        printf("'%c' = %d, ", heap[i].letter, heap[i].freq);
    printf("\n");
}

 node* createHuffmanTree(MinHeap& yourHeap)
{
     cout << "--- Creating Huffman Tree ---\n";
    node left, right, *root;
    while (yourHeap.Size > 1)
    {
        yourHeap.Delete(left);
        yourHeap.Delete(right);
        root = newNode(left, right);
        cout << "-> New Node: freq = " << root->freq << ", letter = " << root->letter << ", left: " << root->left->letter << ", right: " << root->right->letter << endl;
        yourHeap.Insert(*root);
        if (yourHeap.Size < 2)
        {
            return root;
        }
    }
    //return root; // potentially uninitialized local pointer variable 'root' used
}

void outputHuffmanCode(node* root, int arr[], int top)
{
    // left movement is 0
    if (root->left)
    {
        arr[top] = 0;
        outputHuffmanCode(root->left, arr, top + 1);
    }
    // right movement is 1
    if (root->right)
    {
        arr[top] = 1;
        outputHuffmanCode(root->right, arr, top + 1);
    }
    // if reached leaf node, must print character as well
    if (!(root->left) && !(root->right))
    {
        cout << "'" << root->letter << "' = ";
        for (int i = 0; i < top; ++i)
            cout << arr[i];
        cout << endl;
    }
}

int main()
{
    node yourList[6];
    yourList[0].freq = 5;
    yourList[0].letter = 'a';
    yourList[1].freq = 10;
    yourList[1].letter = 'b';
    yourList[2].freq = 15;
    yourList[2].letter = 'c';
    yourList[3].freq = 20;
    yourList[3].letter = 'd';
    yourList[4].freq = 20;
    yourList[4].letter = 'e';
    yourList[5].freq = 30;
    yourList[5].letter = 'f';
    cout << "Here is your list: ";
    for (int i = 0; i < 6; i++)
    {
        cout << "'" << yourList[i].letter << "' = " << yourList[i].freq;
        if (i < 5) cout << ", ";
    } cout << endl;

    MinHeap yourHeap(6);
    yourHeap.Insert(yourList[5]);
    yourHeap.Insert(yourList[4]);
    yourHeap.Insert(yourList[3]);
    yourHeap.Insert(yourList[2]);
    yourHeap.Insert(yourList[1]);
    yourHeap.Insert(yourList[0]);

    /*
    MinHeap yourHeap = MinHeap(6);
    node *item = newNode(30, 'f');
    yourHeap.Insert(*item);
    item = newNode(20, 'e');
    yourHeap.Insert(*item);
    item = newNode(20, 'd');
    yourHeap.Insert(*item);
    item = newNode(15, 'c');
    yourHeap.Insert(*item);
    item = newNode(10, 'b');
    yourHeap.Insert(*item);
    item = newNode(5, 'a');
    yourHeap.Insert(*item);
    delete item;
    */

    node *yourRoot = newNode(0, NULL);
    yourRoot = createHuffmanTree(yourHeap);
    // same cout twice in a row, different results
    //cout << yourRoot->left->freq << endl;
    //cout << yourRoot->left->freq << endl;
    cout << "L0 Root: freq = " << yourRoot->freq << ", letter = " << yourRoot->letter << ", left freq: " << yourRoot->left->freq << ", right freq: " << yourRoot->right->freq << endl;
    cout << "L11 Left: freq = " << yourRoot->left->freq << ", letter = " << yourRoot->left->letter << ", left: " << yourRoot->left->left->letter << ", right: " << yourRoot->left->right->letter << endl;
    //cout << "R11 Left: freq = " << yourRoot->right->freq << ", letter = " << yourRoot->right->letter << ", left: \n";
        //<< yourRoot->right->left->letter << ", right: " << yourRoot->right->right->letter << endl;

    //int arr[MAX_TREE_HEIGHT], top = 0;
    //outputHuffmanCode(yourRoot, arr, top);

    system("pause");
    return 0;
}

我想提前感谢那些阅读并回复这个帖子的人 I'd like to thank whoever reads and replies to this post in advance. 我想我已经提供了尽可能多的信息。如果我做了任何违反社区规则的事情，请让我知道，以便我可以修正我的错误。

Answer 1

在你的createHuffmanTree函数中，你创建了节点的左边和右边...用root = newNode(left, right); 你让你的结构的leftright成员指向你在createHuffmanTree中创建的（临时）节点的地址（这意味着在

node* newNode(node& a, node& b)

a和b的地址总是一样的......而且节点在离开createHuffmanTree函数后就离开了范围--我想这就是你的问题所在。你知道我的意思吗？