Рекурсивная структура без указателей? (Хаффман)

Question

Я определил бинарное дерево таким образом:

struct btree { 
    int x; 
    btree* left_child = nullptr; 
    btree* right_child = nullptr; 
}; 

Тогда у меня есть вектор поплавков (prob_distr) и я поворачиваю каждый поплавок в лист, и я положил все листы в приоритетную очередь (с пользовательская функция сортировки, но здесь это неважно).

auto comp = [] (btree &a, btree &b) -> bool { return a.x > b.x; }; 
priority_queue<btree, vector<btree>, decltype(comp)> q(comp); 

for(auto t: prob_distr) 
{ 
    btree leaf; 
    leaf.x = t; 
    q.push(leaf); 
} 

Для алгоритма Хаффмана, я затем цикл на приоритетной очереди пока он имеет только один элемент слева: я беру 2 узла в верхней из очереди, создать новый узел с этими двумя узлами, как дети и я помещаем эти новые узлы в очередь.

while(q.size() >= 2) 
{ 
    btree left = q.top(); q.pop(); 
    btree right = q.top(); q.pop(); 

    btree root; 
    root.x = left.x + right.x; 
    root.left_child = &left; 
    root.right_child = &right; 

    q.push(root); 
} 

Проблема заключается в том, что у меня есть указатели на left и right бинарных деревьев, и эти деревья удаляются при выходе из цикла. Тогда у меня есть указатели, указывающие Ничто. Есть ли способ решить эту проблему, например, имея структуру, в которой хранятся дочерние деревья, а не только указатели, или путем хранения узлов в другом месте без него становится слишком сложным?

Answer 1

Здесь необходимо использовать указатели, поскольку размер структуры должен быть известен во время компиляции. Если бы у вас было бы struct как переменная-член, потребность в памяти рекурсивно переходила бы к бесконечности.

Вам необходимо динамически выделить память new. Память, выделенная new, выделяется до тех пор, пока вы явно не освободите ее, используя delete. Просто напишите

root.left_child = new btree(left); 
root.right_child = new btree(right); 

Как уже было сказано, вы также должны использовать delete, чтобы освободить память детей. Будьте осторожны, чтобы не делать копии детей, которые не удаляются, а не удалять детей, которые все еще используются где-то в другом месте. Рассмотрите возможность использования интеллектуальных указателей.