BST中的删除节点函数

Question

我有二叉搜索树的基本实现。我在尝试删除树中的节点时遇到问题。

在下面的示例中，我唯一可以删除的值是 80。我首先在没有用户输入的情况下在 BST 中插入了一些值，这部分工作正常。我使用中序遍历来遍历二叉树，它也可以正常工作。但是当我尝试删除值为 14 的节点时，它失败了。

我的错误在哪里？

#include<stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


struct bst {
    int data ;
    struct bst *left ;
    struct bst *right ;
};
 
 
struct bst *findmax(struct bst *root){
    if(root==NULL){
        return NULL ;
    }
    else if(root->right==NULL){
         return root ;
    }
    else return(findmax(root->right)) ;
}
 
struct bst *insertnode(struct bst *root,int data){
    if(root==NULL){
        root = (struct bst*)malloc(sizeof(struct bst)) ;
        if(root==NULL){
            printf("memory error") ;
        }
        else{
            root->data = data ;
            root->left = NULL ;
            root->right= NULL ;
        }
    }
    else{
        if(data < root->data){
            root->left = insertnode(root->left,data) ;
        }
        else if(data > root->data){
            root->right = insertnode(root->right,data) ;
        }
    }
    return root ; 
}
 
struct bst *deletenode(struct bst *root,int data){
    struct bst *temp ;
    if(root==NULL){
        printf("empty") ; 
    }
    else if(data < root->data){
        root->left = deletenode(root->left,data) ;
    }
    else if(data > root->data){
        root->right = deletenode(root->right,data);
    }
    else{
        if(root->left && root->right){
            temp = findmax(root->left) ;
            root->data = temp->data ;
            root->left = deletenode(root->left,root->data) ;
        }
        else{
            temp = root ;
            if(root->left==NULL){
                root = root->right ;
            }
            if(root->right==NULL){
                root = root->left ;
            }
            free(temp) ;
        }
    }
    return(root) ;
}
 
 
void traversebst(struct bst *root){
    if(root){
        traversebst(root->left);
        printf("\n%d",root->data) ;
        traversebst(root->right);
    }
}
 
 
int main()
{
    printf("Hello World"); 
    struct bst *root = NULL;
    root = insertnode(root,5) ;
    insertnode(root,14) ;
    insertnode(root,80) ;
    insertnode(root,60) ;
    insertnode(root,6) ;
    traversebst(root);
    deletenode(root,14);   //delete not working ??
    printf("....\n") ;
    traversebst(root) ;
    return 0;
}

Answer 1

错误在deletenode的最后几行：

if(root->left==NULL){
    root = root->right ;
}
if(root->right==NULL){
    root = root->left ;
}

如果第一个条件为真，则 root 可能会得到值 NULL。那么下一个 if 条件将是一个无效引用。所以你需要把它变成 else if:

if(root->left==NULL){
    root = root->right ;
}
else if(root->right==NULL){
    root = root->left ;
}

BST中的删除节点函数

Delete Node Function in BST

c

data-structures

tree

binary-search-tree