Удалить и найти узел из двоичного дерева

Question

Удалить и найти узел из двоичного дерева

Я работаю над созданием функций «найти» и «удалить» для обычного двоичного дерева (не поиска). Ниже приведен код для функции поиска:

bool Find_Node(FileItem * item, Node *current )  //function starts with root
{
if (current->getNameItem() == item->getName() )  //getNameItem() retrieves the data name in node.
{
currentItem = current;   //I have set currentItem as an attribute ( pointer to a Node ) in the tree class. I created it to point to the node I want to find.
return true;
}
Node* child [2];

child[0] = current->getLeft();
child[1] = current->getRight();

bool res = false;

for (int i = 0; res == false && i < 2 ; i++)
{
if(child[i] != NULL)
res = Find_Node(item, child[i]);
}
return res;
}

Есть ли лучший способ найти узел? и может кто-нибудь, пожалуйста, помогите мне с функцией удаления.

2

binary-tree c++treenode

Решение

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

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

Источник

Accepted Answer

Добавьте базовый вариант для NULL сделать логику простой.

bool Find_Node(FileItem * item, Node *current )
{
if(current == NULL ) return false;
if (current->getNameItem() == item->getName() ) {
currentItem = current;
return true;
}
return Find_Node(current->getLeft()) || Find_Node(current->getRight());
}

void Delete_Node(Node*& current)
{
if(current == NULL) return;
Delete_Node(current->getRight());
Delete_Node(current->getLeft());
delete current;
current = NULL;
}

Если я смогу увидеть реализацию Node, я мог бы рассказать вам, как реализовать swap функция вам понадобится

Если дерево действительно большое, это может вызвать переполнение стека. Но эту проблему можно решить, изменив решение с рекурсивного на итеративное.

2