Я опубликовал об этом в прошлом году, потому что какой-то университетский проект, и теперь я должен сделать это снова (я никогда не заканчивал то, что мне нужно было сделать в последний раз год). Я уже посмотрел на меня, предыдущий код, все вы, ребята, отвечаете на эти вопросы, но все же я не могу понять это.Я не могу удалить простейший случай в двоичном дереве поиска в C
Я не собираюсь ставить все свои вопросы в один длинный пост, это просто делает все более запутанным, и мне нужно понять это раз и навсегда.
Я работаю с самым простым BST возможным (просто целое число для элемента), и я пытаюсь удалить узел из дерева в его простейшем литье, удалив лист.
дерева элементов я тестирую с вставлены в следующем порядке: 7 3 10 2 5 1 6 9 4 8
И выходе из печати в заказе, конечно: 1 2 3 4 5 6 7 8 9 10
Это моя структура дерева:
typedef int TreeElement;
typedef struct sTree {
TreeElement item;
struct sTree *left;
struct sTree *right;
} Tree;
И это моя функция удаления:
int delete(Tree **tree, TreeElement item) {
if(!*tree) return 1;
Tree *currPtr = *tree;
Tree *prevPtr = NULL;
while(currPtr) {
if(item < currPtr->item) {
prevPtr = currPtr;
currPtr = currPtr->left;
} else if(item > currPtr->item) {
prevPtr = currPtr;
currPtr = currPtr->right;
} else {
if(!currPtr->left && !currPtr->right) {
currPtr = NULL;
}
free(currPtr);
return 0;
}
}
return 1;
}
Я не могу понять, почему, но это не работает ... Насколько я понимаю, я ищу элемент для удаления правильно. Когда я нахожу его, я проверяю, является ли этот узел листом, проверяя, что левый и правый дочерние элементы «пусты». Что они для моего теста (попытка удалить узел 1).
При попытке удалить узел 1 с приведенным выше кодом, я все равно получаю печать в порядке, указанную выше. Если я удалю currPtr = NULL
из блока if(!currPtr->left && !currPtr->right)
, я получу следующее для печати в порядке: 0 2 3 4 5 6 7 8 9 10
.
Я не понимая ничего из этого ...
Что я пропускаю в коде выше, так что я могу правильно удалить узел, который является листом? Это самый простой случай удаления узла в BST, но у меня так много проблем с этим, это сводит меня с ума.
Добавлен "C" языка тегов. – 2010-02-18 00:10:02
Извините, я всегда забываю тег языка :( –