BST削除/削除ノード - ルート

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); 
}