我有一个二进制搜索树的基本实现。尝试删除树中的节点时遇到问题。
在下面的示例中,我唯一可以删除的值是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;
}
错误出现在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 ;
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句