Проблема на узлах моего двоичного дерева

Question

Я пытаюсь закодировать класс для представления двоичного дерева. У каждого узла есть значение (key), указатель index и Node* для родителя (p), левого ребенка (left) и правого ребенка (right). Проблема в указателях. Проще привести мой пример проблемы, чем объяснить.

Я кодировал print() функцию, которая распечатывает каждый узел в дереве. Здесь - файл заголовка класса. И здесь является основным тестовым файлом.

Проблема в том, что когда я звоню T.print(), он печатает только 10, 5 и 7.

Answer 1

Проблема в том, что вы используете вектор , который внутренне (пере) распределяет хранилище по мере необходимости.

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

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

Например, добавив это в начале ваших конструкторов RootedTree:

T.reserve(64);

Обратите внимание, что это не надежное решение (если вы попытаетесь поместить более 64 узлов в вектор, у вас все еще может возникнуть та же проблема) - но это подтвердит приведенный выше анализ.

Answer 2

Вы должны решить, какую структуру вы хотите представить своим двоичным деревом.

Любой из

• вектор
• указатели

Не оба!

Так что ваши варианты

1. Удаляя все связанные с указателем вещи и придерживаясь вектора, обработайте Node в индексе i как родительский элемент для Nodes в i*2, i*2 + 1. и наоборот для ребенка -> родительские отношения.
2. Прекратить использование вектора. Имейте корневой узел Node * root внутри вашего RootedTree класса.

У этих двух подходов есть свои сильные и слабые стороны, в частности, случай массива позволяет избавиться от всех указателей, в случае указателя вам не нужно беспокоиться о производительности перераспределений, а хитрые манипуляции, такие как удаление, намного проще