Проблема удаления двоичного дерева с копированием (улучшенное объяснение)
Я создал Raw BinaryTree. В этом дереве вставка не похожа на BST, это вот так::
- Если дерево пусто, добавьте значение & сделать это корнем. (предположим, 30)
- Если дерево не пустое, то введите значение отца (30) & добавьте новое значение (20) к его левому поддереву.
- Если левое поддерево не пустое, вставьте значение (20) в правое поддерево.
- Для следующей вставки снова возьмите значение отца, чтобы определить, куда следует добавить значение.
& скоро..
Работает нормально, кроме случаев, когда я пытаюсь удалить узел с двумя дочерними элементами. Метод, который я использую, чтобы удалить это deleteWithCopy.
Как сказал мой инструктор, deletewithcopy — это:
1. Найдите отца узла (temp), который нужно удалить.
2. Если temp (удаляемый узел) является правильным потомком «отца», найдите непосредственного преемника temp
3. Если temp (удаляемый узел) — левый потомок «отца», найдите непосредственного предшественника temp
4. Поменяйте значение temp с его предшественником / последователем
5. Удалите темп (который теперь является листом дерева).
СЕЙЧАС Как найти Преемника & Предшественник.
Преемник = логический преемник узла — его самый правый дочерний элемент в левом поддереве
Предшественник = логический предшественник узла — его самый левый дочерний элемент в правом поддереве
В соответствии с алгоритмом я создал функцию, но после удаления, когда я пересекаю (или печатаю) дерево, он показывает ошибку времени выполнения,
Необработанное исключение в 0x008B5853 в binarytree.exe: 0xC0000005: Место чтения нарушения доступа 0xFEEEFEEE.
что является ошибкой для «0xFEEEFEEE используется для маркировки свободной памяти в Visual C ++».
Я снова прогнал эту штуку & опять же, в памяти нет ничего, что я пытаюсь получить, я исправил каждый свободный конец, но все же 🙁
Вот функция:
void BinaryTree<mytype>::deletewithTwoChild(BTNode<mytype> *temp)
{
BTNode<mytype> *father = findfather(temp, root); //found address of father of temp node & stored it in pointer
BTNode<mytype> *leaf = temp; //created a copy of temp node
/////CASE 1 (for predecessor)
if(temp==root || father->left==temp) //if temp is left child of its father then
{
leaf = leaf->left; //move leaf 1 time left
while(leaf->right!=0 ) //until leaf reaches the right most node of left subtree
{
leaf = leaf->right; //move leaf 1 time to right
}
//swapping values
mytype var = leaf->key_value; //created a template variable to store leaf's key
leaf->key_value = temp->key_value; //assigning temp's key to leaf
temp->key_value = var; //assigning leaf's key to temp
if(leaf->right!=0) //if leaf has right child then call deletewithOneChild function
{
deletewithOneChild(leaf); //call to respective function
}
else if(leaf->left==0 && leaf->right==0) //if leaf has no children then
{
deleteWithNoChild(leaf); //call to respective function
}
}
/////CASE 2 (for successor)
else if(father->right==temp) //if temp is right child of its father, then
{
leaf = leaf->right; //move leaf 1 time right
while(leaf->left!=0) //until leaf reaches the last node of tree which has no child
{
leaf = leaf->left; //move leaf 1 time to left
}
//swapping values
mytype var = leaf->key_value; //created a template variable to store leaf's key
leaf->key_value = temp->key_value; //assigning temp's key to leaf
temp->key_value = var; //assigning leaf's key to temp
if(leaf->right!=0) //if leaf has right child then call deletewithOneChild function
{
deletewithOneChild(leaf); //call to respective function
}
else if(leaf->left==0 && leaf->right==0) //if leaf has no children then
{
deleteWithNoChild(leaf); //call to respective function
}
}
}
Набор данных, который я использую:
30
/ \
20 80
/ / \
10 40 120
\ / \
60 100 140
/ \ / \
50 70 130 150
Я пытаюсь удалить узел 80, 60, 120, 140, когда появляется ошибка времени выполнения. Пожалуйста, помогите: ((Также мне нужно знать, как обрабатывать дерево, если 30 удалено.
Решение
Как я знаю, определения преемника и предшественника различны.
правопреемник : минимальный узел правого поддерева, то есть самый левый узел правого поддерева.
предок : максимальный узел левого поддерева, то есть самый правый узел левого поддерева.
Вернуться к Выпуск 1. Я заметил if-else условие после замены значений в случае 1. Так как, в случае 1, вы находите самый правый узел поддерева, leaf->right всегда быть null а также leaf->left может не быть null, В результате ни одна из функций удаления не будет вызываться в случае после замены значений. Это вызовет проблему неправильного BST или, что еще хуже, сбой программы. Следовательно if-else Условие на случай, если будет:
// leaf->right always be null, only need to verify leaf->left.
if (leaf->left != 0)
{
deleteWithOneNode(leaf);
}
else
{
deleteWithNoChild(leaf);
}
Выпуск 2. Как я знаю, удаление одного узла в BST не имеет правила выбора предшественника или преемника, и родительский (родительский) узел удаленного узла используется только при замене всего узла, а не при замене значения только узла. Поэтому моя функция удаления будет:
void BinaryTree<myType>::delete(BTNode<myType>* node, BTNode<myType>* parent)
{
if (node->right) // find successor first
{
BTNode* ptrParent = node;
BTNode* ptr = node->right;
while (ptr->left)
{
ptrParnet = ptr;
ptr = ptr->left;
}
// Since the ptr will be delete, we only assign the value of ptr to the value node
node->key_value = ptr->key_value;
if (node == ptrParent)
{
ptrParnet->right = ptr->right;
}
else
{
ptrParent->left = ptr->right;
}
delete ptr;
}
else if (node->left) // find predecessor
{
BTNode* ptrParent = node;
BTNode* ptr = node->left;
while (ptr->right)
{
ptrParent = ptr;
ptr = ptr->right;
}
// Since the ptr will be delete, we only assign the value of ptr to the value node
node->key_value = ptr->key_value;
if (node == ptrParent)
{
ptrParent->left = ptr->left;
}
else
{
ptrParent->right = ptr->left;
}
delete ptr;
}
else
{
if (node->key_value > parent->key_value)
{
parent->right = NULL;
}
else
{
parent->left = NULL;
}
delete node;
}
}
Используя функцию, дерево после удаления 30 будет
40
/ \
20 80
/ / \
10 60 120
/ \ / \
50 70 100 140
/ \
130 150
Другие решения
Других решений пока нет …
detector