时间戳

首页 > 解决方案 > 霍夫曼树指针指向意外位置

c++ - 霍夫曼树指针指向意外位置

问题描述

我被困在霍夫曼树问题上。我认为我的代码有一个清晰的逻辑。我首先建立了一个优先级队列来比较Node的权重，并将权重最小的Node放在优先级队列的顶部。

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

struct Node
{
    int weight, depth;
    Node *left, *right;
    Node(int value):weight(value), left(NULL),right(NULL),depth(0){}
    Node(int value, Node* left_leaf_ptr, Node* right_leaf_ptr) : weight(value), left(left_leaf_ptr), right(right_leaf_ptr), depth(0) {}
};

//this struct is used for priority queue
struct Greater
{  
    bool operator () (Node a, Node b){return a.weight > b.weight;}
};

// find whether the node is a leaf
bool isleaf(Node node) { return node.left == NULL && node.right == NULL; }

// update the depth of Huffman Tree
void update_depth(Node& node,int depth)
{
    node.depth=depth;
    if (! isleaf(node))
    {
        depth++;
        update_depth(*node.left,depth);
        update_depth(*node.right, depth);
    }
}

Node build_Huffman_tree(priority_queue<Node, vector<Node>, Greater> weights_queue)
{
    while (weights_queue.size() > 1)
    {
        Node l1=weights_queue.top();
        weights_queue.pop();
        Node l2 = weights_queue.top();
        weights_queue.pop();
        Node l3(l1.weight + l2.weight, &l1, &l2);
        update_depth(l3, 0);
        weights_queue.push(l3);
    }
    return weights_queue.top();
}

int main()
{
    priority_queue<Node, vector<Node>, Greater> weights_queue;
    weights_queue.push(Node(1));
    weights_queue.push(Node(1));
    weights_queue.push(Node(3));
    weights_queue.push(Node(5));
    Node root = build_Huffman_tree(weights_queue);
    return 0;
}

当我在 C++ 11 中运行这个程序时，在函数 build_Huffman_tree 内的第二个 while 循环中，它创建了一个权重为 2、深度为 4700 的节点。更糟糕的是，这个节点似乎无穷无尽。即它的左子树的权重为 2，而这棵子树的左子树的权重为 2，依此类推...

所以请指出我的程序失败的原因并教我如何解决它。

标签： c++pointersdata-structuresout-of-memoryhuffman-code

解决方案

推荐阅读