Binary Tree Program

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

  1. coderzone

    coderzone Super Moderator

    Joined:
    Jul 25, 2004
    Messages:
    736
    Likes Received:
    38
    Trophy Points:
    28
    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,367
    Likes Received:
    386
    Trophy Points:
    83
  3. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,367
    Likes Received:
    386
    Trophy Points:
    83

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice