1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Binary Tree Program

Discussion in 'C++' started by coderzone, Aug 14, 2010.

  1. coderzone

    coderzone Super Moderator

    Joined:
    Jul 25, 2004
    Messages:
    734
    Likes Received:
    37
    Trophy Points:
    0
    Complete Binary tree program done in C++ including Inorder, Preorder and Postorder Traversal.

    Code:
    #include <iostream.h>
    #include <stdlib.h>
    
    enum {TRUE = 1,FALSE = 0};
    
    typedef struct _node
    {
    	int info;
    	struct _node *left;
    	struct _node *right;
    }node;
    class btree
    {
    private:
    	node *root;
    	void InsertLeft(node* & ,node*);
    	void InsertRight(node* &,node*);
    	void deltree(node*);
    public:
    	btree();
    	~btree();
    	node* GetRoot(void);
    	void MakeTree(void);
    	void DeleteNode(node *,node *,int);
    	int Searchnode(node*,int);
    	void DisplayTree(node*,int);
    	void Inorder(node* );
    	void Preorder(node*);
    	void Postorder(node*);
    };	
    
    btree::btree()
    {
    	char create='Y';
    	root = new node;
    	cout<<"Enter a number which will become a root"<<endl;
    	cin>>root->info;
    	root->left = NULL;
    	root->right = NULL;
    }
    
    btree::~btree()
    {
    	deltree(root);
    }
    
    void btree::deltree(node *root)
    {
    	if(root)
    	{
    		deltree(root->left);
    		deltree(root->right);
    		delete root;
    	}
    }
    
    node* btree::GetRoot(void)
    {
    	return(root);
    }
    
    void btree::MakeTree(void)
    {  
    	node *newnode;
    	char create;
    
    	do
    	{
    		newnode = new node;
    		cout<<"Enter a number"<<endl;
    		cin>>newnode->info;
    
    		newnode->left=NULL;
    		newnode->right=NULL;
    		if(newnode->info < root->info)
    			InsertLeft(newnode,root);
    		else
    			InsertRight(newnode,root);
    		cout<<"Create another node[y/n]"<<endl;
    		cin>>create;
    	}while(create=='Y' || create=='y');
    }
    
    void btree::InsertLeft(node* &newnode,node* current)
    {
    	if(current->left==NULL)
    		current->left=newnode;
    	else
    	{
    		current = current->left;
    		if(newnode->info < current->info)
    			InsertLeft(newnode,current);
    		else
    			InsertRight(newnode,current);
    	}
    }
    
    void btree::InsertRight(node* &newnode,node* current)
    {
    	if(current->right==NULL)
    		current->right=newnode;
    	else
    	{
    		current = current->right;
    		if(newnode->info < current->info)
    			InsertLeft(newnode,current);
    		else
    			InsertRight(newnode,current);
    	}
    }
    
    void btree::DeleteNode(node *current,node *parent,int delnode)
    {
    	if(delnode < current->info)
    		DeleteNode(current->left,current,delnode);
    	else if(delnode > current->info)
    		DeleteNode(current->right,current,delnode);
    	else if(delnode == current->info)
    	{
    		if(current->left == NULL)
    		{
    			if(parent->info > current->info)
    				parent->left = current->right;
    			else
    				parent->right = current->right;
    		}
    		else if(current->right == NULL)
    		{
    			if(parent->info > current->info)
    				parent->left = current->left;
    			else
    				parent->right = current->left;
    		}
    		else
    		{
    			node *temp;
    			int flag = 0;
    
    			parent = current;
    			current = current->left;
    			temp = current;
    			while(current->right != NULL)
    			{
    				current = current->right;
    				if(flag == 0)
    					flag = 1;
    				else
    					temp = temp->right;
    			}
    			parent->info = current->info;
    			if(flag == 0)
    				// No right child
    				parent->left = current->left;
    			else
    				temp->right = current->left;
    		}
    		delete current;
    	}
    }
    
    int btree::Searchnode(node *current,int num)
    {
    	if(num<current->info && current->left!=NULL)
    		Searchnode(current->left,num);
    	else if(num>current->info && current->right!=NULL)
    		Searchnode(current->right,num);
    	else
    	{
    		if(num==current->info)
    			return TRUE;
    		else
    			return FALSE;
    	}
    	return FALSE;
    }
    
    void btree::DisplayTree(node *current,int Level)
    {
    	if(current)
    	{
    		DisplayTree(current->right,Level+1);
    		cout<<endl;
    		for(int i=0;i<Level;i++)
    			cout<<"  ";
    		cout<<current->info;
    		DisplayTree(current->left,Level+1);
    	}
    }
    
    void btree::Inorder(node *current)
    {
    	if(current!=NULL)
    	{
    		Inorder(current->left);
    		cout<<current->info;
    		Inorder(current->right);
    	}
    }
    
    void btree::Preorder(node *current)
    {
    	if(current!=NULL)
    	{
    		cout<<current->info;
    		Preorder(current->left);
    		Preorder(current->right);
    	}
    }
    
    void btree::Postorder(node *current)
    {
    	if(current!=NULL)
    	{
    		Postorder(current->left);
    		Postorder(current->right);
    		cout<<current->info;
    	}
    }
    
    void main()
    {
    	int opt;
    	int num;
    	char ch='y';
    	btree bt;
    	do
    	{
    		cout<<"\nEnter your option\n";
    		cout<<"1. Make a Tree\n";
    		cout<<"2. Delete a node\n";
    		cout<<"3. search a node\n";
    		cout<<"4. display the tree\n";
    		cout<<"5. Inorder traversal\n";
    		cout<<"6. preorder traversal\n";
    		cout<<"7. postorder traversal\n";
    		cout<<"8. Exit\n";
    		cin>>opt;
    		switch(opt)
    		{
    		case 1:
    			bt.MakeTree();
    			break;
    		case 2:
    			int delnode;
    			cout<<"\nEnter an information to be deleted\n";
    			cin>>delnode;
    			bt.DeleteNode(bt.GetRoot(),NULL,delnode);
    			break;
    		case 3:
    			cout<<"\nEnter a number to search in the tree\n";
    			cin>>num;
    			if(bt.Searchnode(bt.GetRoot(),num))
    				cout<<"The number is present"<<endl;
    			else
    				cout<<"The number is not present"<<endl;
    			break;
    		case 4:
    			bt.DisplayTree(bt.GetRoot(),1);
    			break;
    		case 5:
    			bt.Inorder(bt.GetRoot());
    			break;
    		case 6:
    			bt.Preorder(bt.GetRoot());
    			break;
    		case 7:
    			bt.Postorder(bt.GetRoot());
    			break;
    		case 8:
    			exit(0);
    		default:
    			cout<<"\nInvalid Entry\n";
    		}
    	}while(ch=='Y' || ch=='y');
    }
    
    
     
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,283
    Likes Received:
    364
    Trophy Points:
    83
  3. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,283
    Likes Received:
    364
    Trophy Points:
    83

Share This Page