Проблема с указателями при удалении бинарного дерева поиска

Question

Я пытаюсь реализовать бинарные операции с деревом поиска и застрял при удалении.

  11
 /  \
10  14 

Использование обхода inorder в качестве представления начального вывода дерева - 10 11 14.

Удаление узла 10ожидаемый вывод - 11 14, но я получаю 0 11 14.

При удалении узла 14 ожидаемый вывод - только 11, но я получаю 0 11 67837.

Пожалуйста, объясните, почему я ошибаюсьвыход.Я не ищу код:).

typedef struct _node{
  int data;
  struct _node *left;
  struct _node *right;
} Node;

Node* bstree_search(Node *root, int key)
{
  if(root == NULL){
    return root;
  }
  // Based on binary search relation, key can be found in either left,
  // right, or root.
  if(key > root->data)
    return bstree_search(root->right, key);
  else if(key < root->data)
    return bstree_search(root->left, key);
  else
    return root;
}
void bstree_insert(Node **adroot, int value)
{
  // since address of address(root is itself address) is passed we can change root.
  if(*adroot == NULL){
    *adroot = malloc(sizeof(**adroot));
    (*adroot)->data = value;
    (*adroot)->right = (*adroot)->left = NULL;
    return;
  }
  if(value > (*adroot)->data)
    bstree_insert(&(*adroot)->right, value);
  else
    bstree_insert(&(*adroot)->left, value);
}

void bstree_inorder_walk(Node *root)
{
  if(root != NULL){
    bstree_inorder_walk(root->left);
    printf("%d ",root->data);
    bstree_inorder_walk(root->right);
  }
}
void bstree_delete(Node **adnode)
{
  //Node with no children or only one child
  Node *node, *temp;
  node = temp = *adnode;
  if((*adnode)->right == NULL || (*adnode)->left == NULL){
    if((*adnode)->right == NULL){
      *adnode = (*adnode)->left;
    }else{
      *adnode = (*adnode)->right;
    }
  }else{ // Node with two children

  }
  free(temp);
}

int main()
{
  Node *root = NULL;
  Node *needle = NULL;
  int i,elems[] = {11,10,14};

  for(i = 0; i < 3; ++i)
    bstree_insert(&root,elems[i]);

  bstree_inorder_walk(root);
  printf("\n");

  needle = bstree_search(root, 10);
  bstree_delete(&needle);
  bstree_inorder_walk(root);
  printf("\n");

  needle = bstree_search(root, 14);
  bstree_delete(&needle);
  bstree_inorder_walk(root);
  printf("\n");
}

Answer 1

Пожалуйста, объясните, почему я получаю неправильный вывод.

Ваша функция delete также должна изменить родителя удаленного узла.Например, когда вы удаляете узел, содержащий 10, вы должны установить корень Node s left child в NULL.Поскольку вы этого не делаете, когда вы позже пересекаете дерево, вы распечатываете данные, которые уже были освобождены.

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

Answer 2

Несколько вещей очень быстро,

сначала, когда вы выделяете узел, вы действительно должны выполнять malloc для размера типа (т.е. Node).

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

Другие люди уже получили другие очевидные ошибки.

Answer 3

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

Чтобы удалить из бинарного дерева поиска, сначала нужно найти удаляемый узел. Если это листовой узел, вы устанавливаете указатель на него в его родительском узле на NULL и освобождаете узел. Если это , а не листовой узел, вы берете один из двух листовых узлов (либо самый левый дочерний элемент в правом поддереве, либо самый правый дочерний элемент в левом поддереве) и вставляете его вместо узла, который нужно удалить, установите указатель на этот узел в его предыдущем родительском элементе в значение NULL и удалите узел, который вы сейчас «вырезали» из дерева.