c++ - BST 删除/删除节点 - root

Question

我在删除根节点时遇到问题，例如，如果我添加到树 2、1、3 并删除 2(根)，当我想按顺序查看我的树时出现问题并且程序失败。

你能解释一下哪里出了问题吗？

#include <iostream>
#include <string>
using namespace std;
struct BST {
    int data;
    BST* left;
    BST* right;
};

BST* GetNewNode (int data)
{
    BST* newNode = new BST ();
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

//******************************BST******************************************************
BST * insertBST (BST * root, int data);
BST * search (BST* root , int data);
BST* FindMin(BST* root);
BST* Delete (BST* root, int data);
BST* DeleteAll(BST* root);
void Inorder(BST *root);
void Preorder(BST *root);
void Postorder(BST *root);

//****************************MAIN***********************************
int main()
{
    BST* root = NULL;
    string  menu= " ";
    int f ;
    while(menu!="k")
    {
        cout<<"Chose function (i, r, in ,pre, post, del, f)"<<endl
        <<"Want to quit tap k"<<endl;
        cin>>menu;
        if(menu== "i" )
        {
            cout<<"If you want to end inserting write 0"<<endl;
            cin>>f;
            while(f)
            {
            root = insertBST (root,f );
            cin>>f; 
            }
        }
        else if(menu == "r" )
        {
            cout<<"Insert data of node to delete"<<endl;
            cin>>f;
            Delete(root , f);
        }
        else if(menu == "in")
        Inorder (root);
        else if(menu == "pre")
        Preorder (root);
        else if(menu == "post")
        Postorder (root);
        else if(menu == "del")
        root = DeleteAll(root);
        else if(menu == "find")
        {
            cin>> f;
            search(root , f);
        }   

    }
DeleteAll (root);
return 0;
}
///---------------------------------------


BST* insertBST (BST* root, int data)
{
    if (root == NULL)
    {
        root = GetNewNode (data);   
    }
    else if (data <= root->data)
    {
        root->left = insertBST (root->left, data);
    }
    else
    {
        root->right = insertBST (root->right, data);
    }
    return root;
}
BST* search (BST* root , int data)
{
    if (root == NULL) {cout <<"Not found "<<endl;   return  NULL;}
    else if (root->data == data){   cout<<"Found "<<root->data  <<endl ;return root;}
    else if (data<= root->data) return search (root->left, data);
    else return search (root->right, data);
}

BST* Delete (BST* root, int data)
{   
    if(root == NULL) return root;
  else if(data < root->data) root->left = Delete(root->left,data);
  else if(data > root->data) root->right = Delete(root->right, data);
  else
  {
    if(root->left == NULL && root->right == NULL)
    {
      delete root;
      root = NULL;

    } else if(root->left == NULL)
    {
      struct BST *temp = root;
      root = root->right;
      delete temp;
    } else if(root->right == NULL)
    {
      struct BST *temp = root;
      root = root->left;
      delete temp;
    } else{
      struct BST *temp = FindMin(root->right);
      root->data = temp->data;
      root->right = Delete(root->right, temp->data);
    }
  }
  return root;
}

    void Inorder(BST *root)
{
    if(root == NULL) return;

    Inorder(root->left);      
    cout<<root->data<<" ";  
    Inorder(root->right);      
}

void Preorder(BST *root)
{
    if (root != NULL)
    {
    cout<< root->data<<" ";
    Preorder (root->left);
    Preorder (root->right);
    }
    else if (root == NULL)
    return;
}

void Postorder(BST *root)
{
    if (root == NULL)
    return;
    Postorder (root->left);
    Postorder (root->right);
    cout<< root->data<<" ";
}
BST* FindMin(BST* root)
{
    while(root->left != NULL) root = root->left;
    return root;
}
BST* DeleteAll(BST* root)
{

    if (root!=NULL)
    {
        DeleteAll(root->left);
        DeleteAll(root->right);
        delete(root);
        root = NULL;

    }
    return root;
}

Answer 1

你所做的叫做inorder。您可以在下方查看preorder

预购:

do stuff with the node // pre means before
recurse left
recurse right


void Preorder(BST *root)
{
    if (root == NULL)
        return;

    cout<< root->data<<" ";
    Preorder (root->left);
    Preorder (root->right);
}