我编写了代码来删除二叉搜索树中的一个节点。 代码:
#include<iostream>
using namespace std;
struct Node {
int value;
Node* left;
Node* right;
};
Node* GetNewNode(int data) {
Node* newNode = new Node();
newNode->value = data;
newNode->left = newNode->right = NULL;
return newNode;
}
void Insert(Node* &root,int x)
{
if(root==NULL) root=GetNewNode(x);
else if(x>root->value) Insert(root->right,x);
else Insert(root->left,x);
}
Node* Search(Node* root,int x)
{
if(root->value==x) return root ;
else if(root->value>x) Search(root->left,x);
else if(root->value<x) Search(root->right,x);
}
Node* Searchmin(Node* root)
{
if(root==NULL) cout<<"Empty tree"<<endl;
if(root->left==NULL) return root;
else Searchmin(root->left);
}
void Inorder(Node* root)
{
if(root==NULL) return;
else {
Inorder(root->left);
cout<<root->value<<endl;
Inorder(root->right);
}
}
Node* deleteNode(Node* root, int x)
{
Node* nodeptr;
nodeptr=Search(root,x);
if(nodeptr->left==NULL && nodeptr->right==NULL) return nodeptr;
else if(nodeptr->left==NULL && nodeptr->right!=NULL)
{
nodeptr->value=nodeptr->right->value;
nodeptr=nodeptr->right;
return nodeptr;
}
else if(nodeptr->right==NULL && nodeptr->left!=NULL)
{
nodeptr->value=nodeptr->left->value;
nodeptr=nodeptr->left;
return nodeptr;
}
else{
nodeptr->value=Searchmin(nodeptr->right)->value;
deleteNode(nodeptr->right,nodeptr->value);
return nodeptr;}
}
int main()
{
Node* root=NULL;
Insert(root,20);
Insert(root,15);
Insert(root,25);
Insert(root,10);
Insert(root,16);
Insert(root,7);
Inorder(root);
Node* x=deleteNode(root,7);
delete x;
Inorder(root);
}
编译器也没有显示任何语法错误。该程序正在崩溃。它甚至没有删除叶节点。我找不到错误。请帮忙。 (这些行只是为了延长问题的长度,因为 stackoverflow 不接受在长代码行和简短描述行上生成有问题的错误。)
最佳答案
删除函数做的第一件事是调用搜索,搜索做的第一件事是什么?
Node* Search(Node* root,int x)
{
if(root->value==x) return root ;
搜索立即取消引用 root
。它从不检查空指针。这意味着如果树中没有要找到的节点,则可以保证您的搜索函数将取消引用空指针。
关于c++ - 删除二叉搜索树中的节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47874657/