Удалить двоичное дерево

Question

Удалить двоичное дерево

Я пытаюсь закончить функцию удаления

Вот псевдокод, обратите внимание на конец.

Я не знаю, если псевдокод неправильный, хотя.

Вот как я это интерпретировал:

Node* minNode = Minimum(toDelete->right);

int tmp = 0;
tmp = minNode->val;
// delete(&tmp);
free(minNode);
minNode=NULL;
toDelete->val=tmp;

За исключением случаев, когда он удаляет его, он начинает заполнять триллион нулей при печати.

Имеет ли смысл то, что я делаю?
Остальная часть кода, который у меня есть, верна, или я так думаю. Это только облажается в этом сценарии.

Вот и минимальная функция

Node* BST::Minimum(Node *curr) {

// if (curr->left != NULL) {
//      return(Minimum(curr->left));
//  }
//  return curr;
Node* node = curr;
while (node->left != NULL) {
node = node->left;
}
return node;

}

0

binary-tree c++

Решение

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

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

Источник

Accepted Answer

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

если он есть, вы хотите проверить три корпуса:

1: когда вы хотите удалить узел, у которого нет дочернего элемента.
: в этом случае вы просто удаляете указанный узел, так как у него нет дочернего узла.

2: когда вы хотите удалить узел, который имеет левый или правый дочерний узел
: в этом случае вы устанавливаете левого или правого потомка на родительский узел узла, который хотите удалить

3: когда вы хотите удалить узел с двумя детьми
: в этом случае вам нужно найти преемника узла, который вы хотите удалить, затем поменяйте местами преемника с узлом удаления.

public Boolean delete(int key)
{
Node current = root;
Node parent = root;

//search for node here
while(current->key != key)
{
parent = current; //save the parent the nodes as you loop through it
if(key < current->key)
current = current->left
else
current = current->right

//if you do not find the key return false
if(current==null)
return false;
}
//case 1 start here:
//check if the said node has no child. in this case we are looking at current
if(current->left ==null && current->right == null)
{
//check if the node you want to delete is the root
if(current == root)
root = current
else
{
if(parent.key > current->key)
parent-left = null;
else
parent->right = null;
}
}//case 2 here:
//check to see if the node has either left or right child
else if(statement for checking left here)
{
//check for the case where your delete a root

//set the the parent of the current->left to be current->parent
}
else if(statement for checking right here)
{

//check for the case where your delete a root

//set the the parent of the current->right to be current->parent
}
else
{
//create a node successor and give it the successor you found
Node successor = findSuccessor(Node NodeToDel);

//check for root being the node you want to delete

if(root == successor)
root =  successor;
else
{
//navigate left, set parent->left = successor

//navigate right, set parent->right = successor

//with the nature of the findSuccessor() algorithm i have,
//i will have to code one more line:

// give succeccor->left = current->left;
}}

}

Я надеюсь, что это поможет в некотором роде.

0