2010-02-18 1 views
0

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

+0

Добавлен "C" языка тегов. – 2010-02-18 00:10:02

+0

Извините, я всегда забываю тег языка :( –

ответ

5

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

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; 
} 
+0

Я думал об этом, но потом я нашел это: http://e-hon.blogspot.com/2009/01/binary-tree-with-c.html И в этом коде (который я скопировал/скомпилировал и, казалось, работал), нет переменной from fromLeft и даже не указателем для родителя, как у меня в 'prevPtr'. Как работает этот код? –

+1

Он использует оригинал tree ** для отслеживания активного узла и разыменования для сравнения.Поэтому он фактически меняет родительский узел подлым способом. – Joel

+0

Что не рекомендуется? –

0

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

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

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; 
    } 
    } 
} 
+0

Typo: "=" vs "==" – bk1e