c - 二叉搜索树删除中的指针问题

Question

我正在尝试实现二叉搜索树操作，但在删除时卡住了。

  11
 /  \
10  14 

用中序遍历表示树，初始输出为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

Please explain why I am getting wrong output.

您的delete 函数还必须更改已删除节点的父节点。例如，当您删除持有 10 的节点时，您必须将根 Node 的 left 子节点设置为 NULL。由于您不这样做，当您稍后遍历树时，您打印出已经被释放的数据。

除了 delete 之外，我没有查看任何代码，因此我无法保证在进行此更改后它会正常工作。