BST Delete Leaf Node

[javi3r]

Hi all, i have problem with my code.
When i delete child node there isn't problem, but when i delete leaf node doesn't work, why???

Thanks all :)

#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
using namespace std;

class tree_node
{
    private:
        tree_node *left;
		tree_node *right;
		tree_node *root;
		string data;

    public:
        tree_node()
        {
           root = NULL;
        }

        bool isEmpty() const { return root==NULL; }
        void print_inorder();
        void inorder(tree_node*);
        void print_preorder();
        void preorder(tree_node*);
        void print_postorder();
        void postorder(tree_node*);
        void insert(string);
        void remove(string);


};

// Il più piccolo elemento va a sinitra
// L'elemento più grande va a destra
void tree_node::insert(string d)
{
    tree_node* t = new tree_node;
    tree_node* parent;
    t->data = d;
    t->left = NULL;
    t->right = NULL;
    parent = NULL;

    // E' un nuovo nodo?
    if(isEmpty()) root = t;
    else
    {
        //Nota: tutti gli inserimenti avvengono come foglia
        tree_node* curr;
        curr = root;
        // Trova il genitore del nodo
        while(curr)
        {
            parent = curr;
            if(t->data > curr->data) curr = curr->right;
            else curr = curr->left;
        }

        if(t->data < parent->data)
           parent->left = t;
        else
           parent->right = t;
    }
}

void tree_node::remove(string d)
{
    //Localizza l'elemento
    bool found = false;
    if(isEmpty())
    {
        cout<<" Quest'albero è vuoto! "<<endl;
        return;
    }

    tree_node* curr;
    tree_node* parent;
    curr = root;

    while(curr != NULL)
    {
         if(curr->data == d)
         {
            found = true;
            break;
         }
         else
         {
             parent = curr;
             if(d>curr->data) curr = curr->right;
             else curr = curr->left;
         }
    }
    if(!found)
		 {
        cout<<" Campo non trovato! "<<endl;
        return;
    }


		 // 3 casi :
    // 1. Rimoviamo un nodo foglia
    // 2. Rimoviamo un nodo con un singolo figlio
    // 3. Rimoviamo un nodo con due figli

    // Nodo con singolo figlio
    if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
&& curr->right == NULL))
    {
       if(curr->left == NULL && curr->right != NULL)
       {
           if(parent->left == curr)
           {
             parent->left = curr->right;
             delete curr;
           }
           else
           {
             parent->right = curr->right;
             delete curr;
           }
       }
       else // figlio sinistro presente mentre il destro no
       {
          if(parent->left == curr)
           {
             parent->left = curr->left;
             delete curr;
           }
           else
           {
             parent->right = curr->left;
             delete curr;
           }
       }
     return;
    }

		 //Cerchiamo un nodo foglia
		 if( curr->left == NULL && curr->right == NULL)
    {
        if(parent->left == curr) parent->left = NULL;
        else parent->right = NULL;
		 		 delete curr;
		 		 return;
    }


    //Nodo con 2 figli
    //Riposiziona il nodo con il più piccolo valore nel sotto-albero destro
    if (curr->left != NULL && curr->right != NULL)
    {
        tree_node* chkr;
        chkr = curr->right;
        if((chkr->left == NULL) && (chkr->right == NULL))
        {
            curr = chkr;
            delete chkr;
            curr->right = NULL;
        }
        else //figlio destro ha figli
        {
            //se il figlio del nodo destro ha figli
            //ci muoviamo verso sinistra per localizzare il più piccolo elemento

            if((curr->right)->left != NULL)
            {
                tree_node* lcurr;
                tree_node* lcurrp;
                lcurrp = curr->right;
                lcurr = (curr->right)->left;
                while(lcurr->left != NULL)
                {
                   lcurrp = lcurr;
                   lcurr = lcurr->left;
                }
		curr->data = lcurr->data;
                delete lcurr;
                lcurrp->left = NULL;
           }
           else
           {
               tree_node* tmp;
               tmp = curr->right;
               curr->data = tmp->data;
	       curr->right = tmp->right;
               delete tmp;
           }

        }
		 return;
    }

}

void tree_node::print_inorder()
{
  inorder(root);
}

void tree_node::inorder(tree_node* p)
{
    if(p != NULL)
    {
        if(p->left) inorder(p->left);
        cout<<" "<<p->data<<" ";
        if(p->right) inorder(p->right);
    }
    else return;
}

void tree_node::print_preorder()
{
    preorder(root);
}

void tree_node::preorder(tree_node* p)
{
    if(p != NULL)
    {
        cout<<" "<<p->data<<" ";
        if(p->left) preorder(p->left);
        if(p->right) preorder(p->right);
    }
    else return;
}

void tree_node::print_postorder()
{
    postorder(root);
}

void tree_node::postorder(tree_node* p)
{
    if(p != NULL)
    {
        if(p->left) postorder(p->left);
        if(p->right) postorder(p->right);
        cout<<" "<<p->data<<" ";
    }
    else return;
}

int main()
{
    tree_node b;
    int ch;
	string tmp,tmp1;
    while(1)
    {
       cout<<endl<<endl;
       cout<<" Operazioni su Alberi Binari Di Ricerca "<<endl;
       cout<<" ----------------------------- "<<endl;
       cout<<" 1. Inserimento "<<endl;
       cout<<" 2. In-Order  "<<endl;
       cout<<" 3. Pre-Order  "<<endl;
       cout<<" 4. Post-Order  "<<endl;
       cout<<" 5. Rimozione "<<endl;
       cout<<" 6. Exit "<<endl;
       cout<<" Inserisci la tua scelta : ";
       cin>>ch;
       switch(ch)
       {
           case 1 : cout<<" Inserisci la stringa : ";
                    cin>>tmp;
                    b.insert(tmp);
                    break;
           case 2 : cout<<endl;
                    cout<<" In-Order  "<<endl;
                    cout<<" -------------------"<<endl;
                    b.print_inorder();
                    break;
           case 3 : cout<<endl;
                    cout<<" Pre-Order  "<<endl;
                    cout<<" -------------------"<<endl;
                    b.print_preorder();
                    break;
           case 4 : cout<<endl;
                    cout<<" Post-Order  "<<endl;
                    cout<<" --------------------"<<endl;
                    b.print_postorder();
                    break;
           case 5 : cout<<" Scegli la stringa da cancellare : ";
                    cin>>tmp1;
                    b.remove(tmp1);
                    break;
           case 6 :
                    return 0;

       }
    }
}

[dhayden]

It looks to me like the code to remove a leaf is at lines 141-146 and that code looks okay to me.

However, it does appear that the code will fail if you remove the root node.

The constructor at line 16 sets root, but not left or right. Although your code always sets them, it's bad form to allow for the possibility of having them uninitialized. It would be handy to have a constructor that takes a string:

tree_node::tree_node(const string &s) :
    data(s), root(NULL), left(NULL), right(NULL)
    {;}

It's a little harder to understand, but the code can be greatly simplified if you use a pointer to the pointer to the current node. For example, the insert method can look like this (using the new constructor too):

void tree_node::insert(string d)
{
    tree_node* t = new tree_node(d)
    tree_node **ptr;
    tree_node *curr;

    for (ptr = &root; *ptr;) {
        curr = *ptr;
        if(t->data > curr->data) ptr = &curr->right;
        else ptr = &curr->left;
    }
    *ptr = t;
}

Note that ptr points to one of 3 possibilities: the root pointer, a left pointer or a right pointer. The assignment at line 12 thus changes the right pointer in all 3 cases.