Как добавить детей в BST

Question

Как добавить детей в BST

Я пытаюсь сделать / создать BST, но, похоже, он не работает должным образом. Я буквально сидел здесь часами, пытаясь понять, что происходит. Дошло до того, что я нарисовал миллион диаграмм, чтобы понять это, но мой код провалился. Мне нужно передать корневой узел в функцию. Затем мне нужно пройти по дереву, пока не обнаружу, что параметр родительской строки функции совпадает со строкой родительского узла дерева. Если я найду его, я должен вставить строку в родительский элемент и создать двух новых дочерних элементов из этого родительского элемента. Если я не могу найти родительскую строку, тогда я возвращаю false.

 bool insertNode(BSTNode *n, char* parentQ, char* leftQ, char* rightQ)
{
if(n->Q == parentQ)
{
n->left = new BSTNode(leftQ);
n->right = new BSTNode(rightQ);
return true;
}
else if(n->Q != parent)
{
insertNode(n->left,parentQ,leftQ,rightQ);
insertNode(n->right,parentQ,leftQ,rightQ);
}
else
return false;
}

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

bool changeNode(BSTNode *n,char* parentQ, char* leftQ, char* rightQ)
{
if(n->Q == leftQ)
{
n->Q = parentQ;
n->left = new BSTNode(leftQ);
n->right = new BSTNode(rightQ);
return true;
}
else if(n->Q == rightQ)
{
n->Q = parentQ;
n->left = new BSTNode(leftQ);
n->right = new BSTNode(rightQ);
return true;
}
else if(n->Q != leftQ)
{
changeNode(n->left,parentQ,leftQ, rightQ);
}
else if(n->Q != rightQ)
{
changeNode(n->right,parentQ,leftQ,rightQ);
}
return false;
}

0

addchild binary-search-tree c++recursion

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Вы даже не упомянули, в чем заключалась ошибка, например, ввод / ожидаемый вывод, но не следует ли вам проверить, действительно ли у текущего узла есть левый и правый дочерний элемент, прежде чем вызывать функцию с этими дочерними элементами?

else if(n->Q != parentQ) // <--- you have a typo in this line, "parent"{                      //      (and you don't even need the 'if')
insertNode(n->left,parentQ,leftQ,rightQ);
insertNode(n->right,parentQ,leftQ,rightQ);
// in this case you return nothing! corrupted return value
}

^ это кажется очень подверженным ошибкам, особенно нулевой указатель. Вы должны превратить это во что-то вроде:

    else
{
if(n->left != NULL) // take a look at nullptr if you have C++11
if(insertNode(n->left,parentQ,leftQ,rightQ)) return true;
if(n->right != NULL)
if(insertNode(n->right,parentQ,leftQ,rightQ)) return true;
return false;
}

В противном случае ваш true возвращение никогда не распространяется за пределы первого returnзначит, ты всегда возвращаешься false если только в единственном случае, когда корнем дерева является фактически узел, который вы искали.

Кроме того, не сравнивайте два char использование массивов ==если n->Q на самом деле std::string, Вы должны использовать if(strcmp(n->Q, parentQ) == 0) иначе.

Ваш второй кусок кода, однако, просто беспорядок. Вы должны лучше взглянуть на то, что именно будет происходить на вашем else ifи посмотрите, действительно ли он выполняет то, что вы хотите (подсказка: это не так), поскольку в настоящее время вы выполняете не более 1 из блоков кода, даже если выполняется более одного условия.

1