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

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

请解释为什么我收到错误 输出。

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

我没有看到除delete以外的任何代码，因此一旦进行此更改，我无法对其进行任何保证。

Answer 2

因为你的删除代码有问题（好的，也许这就是明显的），你会得到错误的输出。

要从二叉搜索树中删除，首先找到要删除的节点。如果它是叶节点，则将其父节点中的指针设置为NULL，并释放该节点。如果它是而不是叶节点，则取两个叶节点之一（或者是右子树中最左边的子节点，或者是左子树中最右边的子节点），然后插入该节点以代替您需要删除的节点，将指向其上一个父节点的指针设置为NULL，并删除您现在“拼接出”树的节点。

Answer 3

几件事情的真快，

当你分配节点首先，你真的应该做对的sizeof的类型的malloc（即节点）。第二，如果你有两个孩子，看起来你并没有真的删除这个节点，并且通过宣传一个孩子来重建搜索树。

其他人已经让你其他明显的错误。