Указатель дерева Хаффмана указывает на неожиданное местоположение - PullRequest
Новая
       30

Указатель дерева Хаффмана указывает на неожиданное местоположение

0 голосов
/ 21 мая 2018

Я застрял в проблеме дерева Хаффмана.Я думаю, что мой код имеет четкую логику.Сначала я построил очередь с приоритетами для сравнения веса узла и поместил узел с минимальным весом в верхнюю часть очереди с приоритетом. 

#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, во втором цикле whileвнутри функции build_Huffman_tree он создает узел с весом 2, глубиной 4700. Что еще хуже, этот узел кажется бесконечным.то есть его левое дочернее дерево имеет вес 2, а это дочернее дерево имеет левое дочернее дерево с весом 2 и т. д. ...

Поэтому, пожалуйста, укажите причину сбоя моей программы и научите меня, как ее исправить.это.

...