#c
Вопрос:
как правильно создать двоичное дерево? у меня ошибка в работе AddNode . дерево не заполнено. root =НОЛЬ
у меня есть класс Tree с полем root типа Node . затем я вызываю AddNode рекурсивное создание узлов.
и дескриптор не работает для Node s.
#include lt;iostreamgt; #include lt;stringgt; class Node { public: Node() { std::cout lt;lt; "Node Constructorn"; left = NULL; right = NULL; parent = NULL; }; virtual ~Node() { std::cout lt;lt; "Node Destructorn"; Destroy(); }; void SetEngWord(std::string eng) { engWord = eng; } void SetRusWord(std::string rus) { rusWord = rus; } std::string GetEngWord() { return engWord; } std::string GetRusWord() { return rusWord; } Node* GetLeft() { return left; } Node* GetRight() { return right; } Node* GetParent() { return parent; } void SetLeft(Node* l) { left = l; } void SetRight(Node* r) { right = r; } void SetParent(Node* p) { parent = p; } void PrintWord() { std::cout lt;lt; engWord lt;lt; " - " lt;lt; rusWord lt;lt; std::endl; } void Destroy(); private: std::string engWord; std::string rusWord; Node* left; Node* right; Node* parent; }; void Node::Destroy() { if (left != NULL) { left-gt;Destroy(); delete left; } if (right != NULL) { right-gt;Destroy(); delete right; } delete this; } class Tree { public: Tree() { std::cout lt;lt; "Tree Constructorn"; root = NULL; }; virtual ~Tree() { std::cout lt;lt; "Tree Destructorn"; root-gt;Destroy(); }; void Add(std::string eng, std::string rus); void AddNode(Node* src, Node* parent, Node* n, bool left); Node* Search(std::string s); private: Node* root; }; void Tree::Add(std::string eng, std::string rus) { Node* n = new Node; n-gt;SetEngWord(eng); n-gt;SetRusWord(rus); AddNode(root,NULL,n,true); } void Tree::AddNode(Node* src, Node* parent, Node* n, bool left) { if (src == NULL) { src = n; if (src-gt;GetParent() == NULL amp;amp; parent != NULL) { src-gt;SetParent(parent); if (left) src-gt;GetParent()-gt;SetLeft(n); else src-gt;GetParent()-gt;SetRight(n); } return; } if (n-gt;GetEngWord() lt; src-gt;GetEngWord()) { AddNode(src-gt;GetLeft(), src, n, true); } else { AddNode(src-gt;GetRight(), src, n, false); } } Node* Tree::Search(std::string s) { Node* n; n = root; while(true) { if (n == NULL) break; if (n-gt;GetEngWord() lt; s) n = n-gt;GetLeft(); if (n-gt;GetEngWord() gt; s) n = n-gt;GetRight(); if (n-gt;GetEngWord() == s) break; } return n; } int main() { Tree tree; tree.Add("a","aa"); tree.Add("b","bb"); tree.Add("c","cc"); Node* n = tree.Search("b"); if (n != NULL) n-gt;PrintWord(); else std::cout lt;lt; "NULL" lt;lt; std::endl; return 0; } Комментарии:
1. Вызов
deleteвызывает деструктор для этого объекта. Таким образом, Разрушение и деструктор вызывают друг друга в бесконечном рекурсивном цикле.2. Похоже, вы переходите
rootкAddNodeзначению по , чтобы оно не обновлялосьroot, поэтому вы ничего не создаете. Вы пробовали писать более простые программы, такие как связанный список?3. Если вы изменяете переменную src внутри
Tree::AddNode, вы не изменяете переменную вызывающего абонента (напримерroot). Вероятно, вам лучше не пытаться передать это с помощью переменных и получить доступ к корневому каталогу непосредственно внутри AddNode.4.
gdbДумаю, пришло время начать и посмотреть, что происходит. Перед этим (или в дополнение к этому) запустите его подvalgrindи убедитесь, что он сообщает об отсутствии ошибок.
Ответ №1:
Ладно, я вижу несколько проблем.
Я бы немного переписал этот метод:
void Tree::Add(std::string eng, std::string rus) { Node* n = new Node; n-gt;SetEngWord(eng); n-gt;SetRusWord(rus); if (root == nullptr) { root = n; } else { AddNode(root,NULL,n,true); } } Это исправит вставку первого элемента (когда корень равен нулю). Теперь вы разрушители:
virtual ~Tree() { std::cout lt;lt; "Tree Destructorn"; delete node; }; Ваш код на самом деле не удалял узел. Просто позвольте деструктору узла выполнить всю работу.
Это действительно плохая идея:
void Node::Destroy() { if (left != NULL) { left-gt;Destroy(); delete left; } if (right != NULL) { right-gt;Destroy(); delete right; } delete this; } Объекты не должны удаляться сами по себе. Это не вызывает никаких проблем. Это может быть намного, намного проще.
virtual ~Node() { delete left; delete right; }; Это работает, потому что, если значение left равно нулю, это ничего не повредит. Если это указывает на что-то, мы уничтожим это, что рекурсивно будет продолжаться до тех пор, пока это не будет сделано.
Ответ №2:
void Tree::AddNode(Node*amp; src, Node* parent, Node* n, bool left) { if (src == NULL) { src = n; if (src-gt;GetParent() == NULL amp;amp; parent != NULL) { src-gt;SetParent(parent); if (left) src-gt;GetParent()-gt;SetLeft(n); else src-gt;GetParent()-gt;SetRight(n); } return; } if (n-gt;GetEngWord() lt; src-gt;GetEngWord()) { Node* nn = src-gt;GetLeft(); AddNode(nn, src, n, true); } else { Node* nn = src-gt;GetRight(); AddNode(nn, src, n, false); } }