霍夫曼树中的左节点和右节点指针不指向任何内容

Question

struct Node{
    int freq;
    string character;
    struct Node *left;
    struct Node *right;
};

我已经解析了一个文件并创建了节点的优先级队列。每个节点都有一个频率的整数，一个用于节点中表示的字符的字符串。以及用于左右分支的两个 Node 指针。

以下代码位于主函数中。

priority_queue<Node, vector<Node>, CompareNodes> pq;
// Build Tree //
while( pq.size() > 1 )
{
    Node * l = new Node;
    Node * r = new Node;
    Node r1 = pq.top();
    r->character = r1.character;
    r->freq = r1.freq;
    pq.pop();
    Node l1 = pq.top();
    l->character = l1.character;
    l->freq = l1.freq;
    pq.pop();

    Node * combined = new Node;
    combined->character = l1.character + r1.character;
    combined->freq = l1.freq + r1.freq;
    combined->left = l;
    combined->right = r;
    pq.push(*combined);
}

运行上面的代码并检查每个左右指针后，超出第一级的所有左右指针均为 NULL。

从

本质上讲，从根部向上移动是不可能的。只有第一个左右指针指向节点。所有其他子项左/右指针都无处可去。

我有一种感觉，我没有正确分配空间。每次传递后的位置 *l 和 *r 应该仍然可以访问并包含一个节点，对吗？或者它们是 while 循环的本地内容，并在每次传递后被删除？

Answer 1

答案正如Mike Vine所解释的那样。

您正在使用队列。当您在节点进入和退出队列时复制节点时，您将丢失信息。一个"简单"的解决方法是使用队列节点*，并在首次输入节点时更新节点。这与上述删除 l 和 r 变量的修复相结合将使这项工作(您还需要将 CompareNode 比较器更改为按指针获取。更正确的解决方法是将队列unique_ptr节点之类的东西，这样您就可以拥有更好的生命周期管理，但随后您将需要进行更多更改。

谢谢你，迈克。