1. We have moved from vBulletin to XenForo and you are viewing the site in the middle of the move. Though the functional aspect of everything is working fine, we are still working on other changes including the new design on Xenforo.
    Dismiss Notice

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,276
    Likes Received:
    364
    Trophy Points:
    83
  3. shabbir

    shabbir Administrator Staff Member

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

Share This Page