Clear() function in Binary Tree

[akmal4ik]

Hi everybody, help me to finish my programm.
It's all works, except one function.
This function is clear();
This function must fully clear binary tree.
And the constructor Map(char * ch, double val)
doesn't works. I can't understand.

//Binary Search Tree Program

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

class Map
{
	private:
        struct tree_node
        {
           tree_node* left;
           tree_node* right;
           double data;
		   char * key;
        };
        tree_node* root;
		    
    public:
        Map()
        {
           root = NULL;
		}
      
		/*Map(char * key, double val)
		{
			root->key = key;
			root->data = val;
			root->left = NULL;
			root->right = 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 find(char * ch);
		int print_count();
		int count(tree_node * t);
		//void clear_o();
		//void clear_c(tree_node*p);
		void print_s(tree_node ** p);
		void insert(char * ch, double d);
            void remove(char * dkey);
};


// Smaller elements go left
// larger elements go right
void Map::find(char * ch)
{
   //Find code
}


void Map::insert(char * ch, double val)
{
   struct tree_node *curr,*parent;
   if(root == NULL)
   {
      root = (struct tree_node *) malloc(sizeof(struct tree_node)); /* insert the new node as root node*/
      
	  if(root == NULL)
      {
	      printf("Cannot allocate\n");
		  exit(0);
      }
      
	  root->key = ch;
	  root->data = val;
      root->left=root->right=NULL;
   }
   else
   {
      curr = root;
      /* traverse the tree to get a pointer to that node whose child will be the newly created node*/
      while(curr != NULL)
	  {
		 parent = curr;
		 if(strcmp(curr ->key, ch)<0)
			curr = curr->left;

		 else
			curr = curr->right;
	  }

	  if(strcmp(parent->key,ch)<0)
	  {
		  parent->left = (struct tree_node*)malloc(sizeof(struct tree_node));/*inserts the newly created node as left child*/
          parent = parent->left;
          
		  if(parent == NULL)
          {
			 printf("Cannot allocate\n");
			 exit(0);
          }
			 parent->key = ch;	
			 parent->data = val;
			 parent->left=parent->right = NULL;
	  }
	  else
	  {
		  parent->right = (struct tree_node*)malloc(sizeof(struct tree_node));/*inserts the newly created node
			as left child*/
		  parent = parent->right;
		  if(parent == NULL)
          {
			  printf("Cannot allocate\n");
			  exit(0);
          }
		  
		  parent->key = ch;
		  parent->data = val;
		  parent->left=parent->right = NULL;
	  }
   }
}


void Map::remove(char * dkey)
{
    //Locate the element
    bool found = false;
    if(isEmpty())
    {
        cout<<" This Tree is empty! "<<endl;
        return;
    }
    
	tree_node * temp;
    tree_node* curr;
    tree_node* parent;
    curr = root;
    
    while(curr)
    {
         if(strcmp(curr->key,dkey)==0)
         {
			found = true;
            break;
         }
         else
         {
             parent = curr;
             if(strcmp(curr->key, dkey)<0)
				 curr = curr->left;
             else 
				 curr = curr->right;
         }
    }
    if(!found)
	{
        cout<<" Data not found! "<<endl;
        return;
    }

		 // 3 cases :
    // 1. We're removing a leaf node
    // 2. We're removing a node with a single child
    // 3. we're removing a node with 2 children


	
    
	/* this code is for deleting node having both children */
  if( curr->left != NULL && curr->right != NULL)
  {

	/* this code is for deleting root node with both children*/
    if( curr == root)
    {
        temp = curr->left;
        parent = curr->right;
        root = temp;
			
		while(temp->right != NULL)
			temp = temp->right;
		temp->right=parent;
		delete curr;
		root=NULL;
		return;
    }


       if(parent->left == curr)
       {
			temp = curr->left;
			parent->left = curr->left;
			
			while(temp->right != NULL)
				temp = temp->right;
			
			temp->right=curr->right;
			curr->left=NULL;
			curr->right=NULL;
       }
       else
       {
			temp = curr->right;
			parent->right = curr->right;
			
			while(temp->left != NULL)
				temp = temp->left;
			
			temp->left=curr->left;
			curr->left=NULL;
			curr->right=NULL;
       }

	   delete curr;
	   return;
  }


	/* this code is for deleting a node with one child*/
    if(curr->left == NULL && curr->right != NULL)
    {
		if( curr == root)/* this code is for deleting root node with right child*/
		{
			temp = curr->left;
			parent = curr->right;
			root = temp;
			
			while(temp->right != NULL)
				temp = temp->right;
			
			temp->right=parent;
			root=NULL;
			delete curr;
			return;
		}

		if(parent->left == curr)
			parent->left = curr->right;
        else
            parent->right = curr->right;
            curr->right = NULL;
            delete curr;
			return;
    }

	if(curr->left != NULL && curr->right == NULL)
    {
		if( curr == root)/* this code is for deleting root node with left child*/
		{
			temp = curr->left;
			parent = curr->right;
			root = temp;
			
			while(temp->right != NULL)
				temp = temp->right;
			
			temp->right=parent;
			delete curr;
			root=NULL;
			return;
		}

        if(parent->left == curr)
			parent->left = curr->left;
        else
            parent->right = curr->left;
            curr->left = NULL;
            return;
    }
	
    
	//We're looking at a leaf node
	if( curr->left == NULL && curr->right == NULL)
    {
		if(curr == root)/* this code is for deleting root node with no children*/
		{
			delete curr;
			root = NULL;
			return;
		}

        if(parent->left == curr)
			parent->left = NULL;
        else 
			parent->right = NULL;
		delete curr;
		return;
    }

 }
int Map::print_count(){ //count code }
int Map::count(tree_node * t){//count code}
void Map::print_preorder(){//print_preorder code}
void Map::preorder(tree_node* p){//print_preorder code}
void Map::print_postorder(){//print_postorder}
void Map::postorder(tree_node* p){//print_postorder}
void Map::print_inorder(){//print_inorder}
void Map::inorder(tree_node* p){print_inorder}


int main()
{
    Map salary;
	string temp, ftarget, dtarget;
	int ch,tmp,tmp1,size,c;
	double data;
    while(1)
    {
       cout<<endl<<endl;
       cout<<" Binary Search Tree Operations "<<endl;
       cout<<" ----------------------------- "<<endl;
       cout<<" 1. Insertion/Creation "<<endl;
       cout<<" 2. Print Inorder "<<endl;
	   cout<<" 3. Print Preorder "<<endl;
	   cout<<" 4. Print Postorder "<<endl;
	   cout<<" 5. Find "<<endl;
       cout<<" 6. Removal "<<endl;
	   cout<<" 7. Count of Elements "<<endl;
	   cout<<" 8. Clear "<<endl;
	    
       //cout<<" 6. Exit "<<endl;
       cout<<" Enter your choice : ";
		       cin>>ch;
	   char * pch;
       switch(ch)
       {
           case 1 : cout<<" Enter key: ";
                    cin>>temp;
	                pch = (char *) malloc(sizeof(char)*temp.size()); 			
					strcpy(pch, temp.c_str());
					cout << " Enter data: ";
					cin >> data;
					salary.insert(pch,data); break;
           
		   case 2 : cout<<endl;
				    cout<<" In-Order Traversal "<<endl;
                    cout<<" -------------------"<<endl;
                    salary.print_inorder(); break;
				
           case 3 : cout<<endl;
                    cout<<" Pre-Order Traversal "<<endl;
                    cout<<" -------------------"<<endl;
                    salary.print_preorder(); break;

           case 4 : //Post-Order Traversal 
                    break;

	     case 5:  if(salary.isEmpty())
			      cout<<"\n This Tree is empty! "<<endl;
			  else
			  {
    				cout << "Enter key: ";
				cin >> temp;
				pch = (char *) malloc(sizeof(char)*temp.size()); 			                  strcpy(pch, temp.c_str());
				salary.find(pch);
		        }  break;
			
           case 6 : if(salary.isEmpty())
			     cout<<"\n This Tree is empty! "<<endl;
			  else
			  {   cout<<" Enter key to be deleted : ";
				cin >> temp;
				pch = (char *) malloc(sizeof(char)*temp.size()); 					strcpy(pch, temp.c_str());
				salary.remove(pch);
			  }
		        break;

	      case 7:  if(salary.isEmpty())
				cout<<"\n This Tree is empty! "<<endl;
			   else
			   {
			      c = salary.print_count();
				cout << "\nThere are " << c << " elements. \n";
			   }
			   break;

/*		case 8:  salary.clear_o();
			   break;*/

	   		                              
       }
    }
}

[helios]

The clear function is very simple if you implement it in the nodes:

~tree_node(){
	if (this->left)
		delete this->left;
	if (this->right)
		delete this->right;
	if (this->key)
		delete this->key;
}

Then to clear the tree just delete the root and you're done.
The constructor doesn't work because you're trying to initialize the members of a null pointer.

[akmal4ik]

The constructor doesn't work because you're trying to initialize the members of a null pointer.

How can i do this?

[helios]

Call insert() from inside the constructor with the same parameters. You may need to change the order of declaration.