一次删除整个二叉搜索树

Question

我一直在尝试实现delete BST功能，但不知道为什么它不起作用，我认为它在逻辑上是正确的。任何机构都可以告诉我，为什么我会收到运行时错误以及我应该如何纠正它。

  #include <iostream>
  using namespace std;

class node{
public:
int data;
node *right;
node *left;
node(){
    data=0;
    right=NULL;
    left=NULL;
      }
};

class tree{
node *head;
int maxheight;
     public:
tree(){head=0;maxheight=-1;}
bool deletenode(int key,node* root);
int get_height(){return maxheight;}
void insert(int key);
void pre_display(node* root);
     void delete_tree(node *root);
     node* get_head(){return head;}
         };

void tree::insert(int key){
     node *current=head;
    node *newnode=new node;

    if(newnode==NULL)
    throw(key);

    newnode->data=key;
    int height=0;

if(head==0){
head=newnode;
     }
else
{
    while(1){
    if(current->right==NULL && current->data < newnode->data)
    {
        current->right=newnode;
        height++;
        break;
    }
    else if(current->left==NULL && current->data > newnode->data)
    {
        current->left=newnode;
        height++;
        break;
    }
    else if(current->right!=NULL && current->data < newnode->data)
    {
         current=current->right;
         height++;
   }
    else if(current->left!=NULL && current->data > newnode->data)
    {
               current=current->left;
          height++;
    }
         }
 }
 if(height>maxheight)
 maxheight=height;
 }

 void tree::pre_display(node *root){
 if(root!=NULL)
 {
 cout<<root->data<<" ";
 pre_display(root->left);
 pre_display(root->right);
 }
 }

 void tree::delete_tree(node *root){
  if(root!=NULL)
 {
 delete_tree(root->left);
 delete_tree(root->right);
 delete(root);
 if(root->left!=NULL)
 root->left=NULL;
 if(root->right!=NULL)
 root->right=NULL;
 root=NULL;
 }
 }

int main(){
tree BST;
int arr[9]={17,9,23,5,11,21,27,20,22},i=0;

for(i=0;i<9;i++)
BST.insert(arr[i]);

BST.pre_display(BST.get_head());
cout<<endl;
BST.delete_tree(BST.get_head());
BST.pre_display(BST.get_head());
cout<<endl;

system("pause");
return 0;
}

所有其他功能都正常工作，您只需要检查该delete_tree功能，其他代码提供了我的BST结构的想法。

Answer 1

在您的 delete_tree 中

void tree::delete_tree(node *root){
    if(root!=NULL)
    {
        delete_tree(root->left);
        delete_tree(root->right);
        delete(root);
        if(root->left!=NULL)
            root->left=NULL;
        if(root->right!=NULL)
            root->right=NULL;
        root=NULL;
    }
}

您在删除根变量后正在访问它

你也叫

    BST.delete_tree(BST.get_head());
BST.pre_display(BST.get_head());

删除树后的 pre_display。delete_tree删除树后也应该设置 BST.head 为 NULL

也是一种批判。BST 是树类型。它已经有一个指示根节点的头成员变量。所以 delete_tree/pre_display 根本不需要任何参数。