c-删除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 ;
}

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

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