Я не могу удалить самый простой случай в дереве двоичного поиска в C

Question

Я писал об этом в прошлом году, потому что какой-то университетский проект, и теперь я должен сделать это снова (я так и не закончил то, что должен был сделать в прошлом году).Я уже посмотрел предыдущий код, все вы, ребята, отвечаете на эти вопросы, но все же я не могу этого понять.

Я не собираюсь помещать все свои вопросы в один длинный пост, это только делает все более запутанным, и мне нужно понять это раз и навсегда.

Я работаю с самым простым из возможных 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, но у меня столько проблем с этим, это сводит меня с ума.

Answer 1

В этом случае вы меняете значение, содержащее текущий указатель, а не значение в узле, указывающем на него.То, что вы на самом деле хотите, это что-то вроде

int delete(Tree **tree, TreeElement item) {
if(!*tree) return 1;

Tree *currPtr = *tree;
Tree *prevPtr = NULL;
bool fromLeft = false;

while(currPtr) {
    if(item < currPtr->item) {
        prevPtr = currPtr;
        currPtr = currPtr->left;
        fromLeft = true;
    } else if(item > currPtr->item) {
        prevPtr = currPtr;
        currPtr = currPtr->right;
        fromLeft = false;
    } else {            
        if(!currPtr->left && !currPtr->right) {
            if( fromLeft )
               prevPtr->left = NULL;
            else
               prevPtr->right = NULL;
        }

        free(currPtr);

        return 0;
    }
}

return 1;
}

Answer 2

Бинарное дерево - это рекурсивно определенный тип данных, и удаление намного проще с рекурсивной функцией. Я даже не хочу пытаться отладить ваше хитрое итеративное решение; ошибка, которую вы делаете, не является незначительной ошибкой кода; ошибка в том, что вы используете неправильные идеи для работы.

Вот некоторые полностью непроверенные код:

Tree *delete(item, tree) {
   if (tree == NULL)
     return tree;
   else if (item < tree->item)
     tree->left = delete(item, tree->left);
   else if (item > tree->item)
     tree->right = delete(item, tree->right);
   else { // here comes the only interesting case
     // if one child is NULL, move the other up
     // otherwise grab an item from one child and recurse
     Tree *answer;
     if (tree->right = NULL) {
       answer = tree->left;
       free(tree);
       return answer;
     } else if (tree->left == NULL) {
       answer = tree->right;
       free(tree);
       return answer;
     } else {
       tree->item = tree->left->item; // choice of left/right is     arbitrary
       tree->left = delete(tree->left->item, tree->left);
       return tree;
     }
   }
}