Implementing Binary Tree in Data Structure Using C++

Introducing Binary Tree in Data Structure

Much similar to the green and lush trees you see in the real world, the binary tree in data structures also consists of roots and leaves, but with a few modifications. Unlike the root being the bottom-most part of the tree in the real world, the root of a binary tree is the topmost component. In this data structure, you also have other terminologies such as the parent, child, left child, right child, and the leaf.

Let me give you a brief illustration of what they are through the image below:

representation of binary tree in data structure

 

Implementation of Binary Tree in Data Structure Using C++

1. Creating a Binary Tree in C++

As a hierarchical data structure, the binary tree has three main components when it’s represented in C++. They are data and pointers to the parent and left and right children. So, to create a binary tree, we would have to declare a class first.

For our better understanding, let us consider that our structure is called a node. Then, we would have to declare an integer type called data which would store the values. We shall then also declare pointers to the parent and left and right children nodes.

So, our code would look like this:

class node
{
	node *left;
	node *right;
	int data;
	public:
	node(int n)
	{
		data=n;
		left=NULL;
		right=NULL;
	}
	friend class tree;
};

2. Inserting A New Node in An Existing Binary Tree in C++

When you insert a new node into a “binary search tree”, you need to compare it with the root to check whether the node to be inserted precedes or succeeds the root. Therefore, if the node to be inserted is greater than the current highest node, then assign it to the right subtree. Similarly, if it is lesser than the current highest node, assign the new node to the left subtree.

But here we are talking about the Binary Tree, so there’s no need to compare the values with the root node.

// Function To Insert A Node Into Binary Tree
void tree::create()
{
	node *temp,*newnode;
	int c;
	char ans,choice;
	do
	{
		cout<<"Enter the element to be attached\n";
		cin>>c;
		newnode=new node(c);
		if(root==NULL)
		{
			root=newnode;
		}
		else
		{
			temp=root;
			while(1)
			{
				cout<<"Left or right(l/r) of  "<<temp->data;
				cout<<"\n";
				cin>>ans;
				if(ans=='l')
				{
					if(temp->left==NULL)
					{
						temp->left=newnode;
						break;
					}
					else
					{
						temp=temp->left;
					}
				}
              else
			  {
			  	if(temp->right==NULL)
			  	{
			  	temp->right=newnode;
				  break;	
				  }
				  else
				  {
				  	temp=temp->right;
				  }
				}				
			}
		}
			cout<<"Any more nodes? y for yes"<<endl;
			cin>>choice;
			cout<<"\n\n";
		}
	while(choice=='y'||choice=='Y');
}

3. Displaying the Nodes of a Binary Tree in C++

There are basically three ways for traversing binary trees.

(a) Pre-Order Traversal

In pre-order traversal, we first visit the root node, then we traverse the left sub-tree and then we traverse the right sub-tree recursively. By pre-order traversal, you can create a copy of the tree and also get the prefix expression of an expression binary tree.

Traversing steps: Root -> Left -> Right

Example:

preorder traversal of binary tree in data structure

Output: 1 2 4 5 3

Here in this example, we are first visiting the root node, printing its value in the output.

Now we are moving to its left sub-tree. Printing the values in pre-order traversal [2(root) – 4(left-child) – 5(right-child)].

Since, we have traversed the left sub-tree, we will now move to right sub-tree. The only node which is not traversed yet is 3.

void tree::preordertraversal(node *currentnode)
{
	if(currentnode!=NULL)
	{
	   cout<<currentnode->data;
		preordertraversal(currentnode->left);
		preordertraversal(currentnode->right);	
	}
}

(b) Post-Order Traversal

In post-order traversal, we first traverse the left sub-tree, then traverse the right sub-tree and at last we visit the root node. It is also used the get the postfix expression of an expression binary tree.

Traversing steps: Left -> Right -> Root

Example:

postorder traversal of binary tree in data structure

Output: 4 5 2 3 1

In this example, you can see we are first traversing the left sub-tree of root node 1 i.e [4(left-child) – 5(right-child) – 2(root)]

Then we are traversing the right sub-tree which consist of only one node which is 3.

At last, we are visiting the root node 1.

void tree::postordertraversal(node *currentnode)
{
	if(currentnode!=NULL)
	{   
		preordertraversal(currentnode->left);
		postordertraversal(currentnode->right);
		cout<<currentnode->data;
	}
}

(c) Inorder Traversal

In case of Inorder traversal, we first traverse the left sub-tree. Then we visit the root node and at last we traverse the right sub-tree. Inorder traversal is very useful for Binary Search Trees, because it gives nodes in a non-decreasing order.

Traversing steps: Left -> Root -> Right

Example:

inorder traversal of binary tree in data structure

Output: 4 2 5 1 3

Here, we traversed the left sub-tree first i.e [4(left-child) – 2(root) – 5(right-child)]

Then we visited the root node i.e 1

And then traversed the right sub-tree, printing the value 3.

void tree::inorder(node *currentnode)
{
	if(currentnode!=NULL)
	{
		inorder(currentnode->left);
		cout<<currentnode->data;
		inorder(currentnode->right);
	}
}

 4. Mirroring A Binary Tree in C++

In the diagram above, we see that B is the mirror tree of the binary tree A. Note that the mirror tree has the interchanged nodes of the leaves, left and right children of the binary tree. While writing the code, we need to first call the mirror function for the left sub-tree followed by the right sub-tree. Then when we swap the left and right sub-trees, we would have generated the mirror tree.

mirror of binary tree in data structure

5. Counting the Total Number of Nodes in a Binary Tree in C++

To determine the total number of nodes in a binary tree we need to traverse the entire tree at least once. We can make use of any of the aforementioned traversing techniques to do so.

The logic here is quite simple, as we can simply declare a variable called count’, initialized at zero and continue to increase its value as we pass every node. Take a look at the binary tree below. Here, the total number of nodes is 7.

total number of nodes in binary tree in data structure

 

//Function To Count Total Number Of Nodes In A Binary Tree
int tree::countnodes(node *currentnode)
        {
            if(currentnode != NULL)
            {
                countnodes(currentnode->left);
                count++;
                countnodes(currentnode->right);
                
            }
            return count;
            
        }

6. Counting the Total Number of Leaf Nodes in a Binary Tree in C++

To deduce the count of the total number of leaf nodes we shall first check if the node is null. If so, there are no leaves. Then, we shall check if the left and right children nodes are null. If they are so, then the count of the leaf would be one.

Now, using the formula below, you can recursively traverse the leaf to deduct its count.

Total leaf count = Left sub-tree’s leaf count + Right sub-tree’s 

//Function For Counting Total Number Of Leaf Nodes
int tree::countleafnodes(node *currentnode)
        {
            if(currentnode != NULL)
            {
                countleafnodes(currentnode->left);
                if((currentnode->left == NULL) && (currentnode->right == NULL))
                {
                    count++;
                }
                countleafnodes(currentnode->right);
            }
            return count;
        }

C++ Program For Implementing Binary Tree In Data Structure

#include<iostream>
#include<cstdlib>
#include<cstdlib>
#include<cstdio>
using namespace std;
static int count=0;
class node
{
	node *left;
	node *right;
	int data;
	public:
	node(int n)
	{
		data=n;
		left=NULL;
		right=NULL;
	}
	friend class tree;
};
class tree
{
	public:
	node *root;
	tree()
	{
	 root=NULL;
	}
	void create();
	void inorder(node *currentnode);
	void preordertraversal(node *currentnode);
	void postordertraversal(node *currentnode);
	int countnodes(node *currentnode);
	int countleafnodes(node *currentnode);
};
void tree::create()
{
	node *temp,*newnode;
	int c;
	char ans,choice;
	do
	{
		cout<<"Enter the element to be attached\n";
		cin>>c;
		newnode=new node(c);
		if(root==NULL)
		{
			root=newnode;
		}
		else
		{
			temp=root;
			while(1)
			{
				cout<<"Left or right(l/r) of  "<<temp->data;
				cout<<"\n";
				cin>>ans;
				if(ans=='l')
				{
					if(temp->left==NULL)
					{
						temp->left=newnode;
						break;
					}
					else
					{
						temp=temp->left;
					}
				}
              else
			  {
			  	if(temp->right==NULL)
			  	{
			  	temp->right=newnode;
				  break;	
				  }
				  else
				  {
				  	temp=temp->right;
				  }
				}				
			}
		}
			cout<<"Any more nodes? y for yes"<<endl;
			cin>>choice;
			cout<<"\n\n";
		}
	while(choice=='y'||choice=='Y');
}
void tree::inorder(node *currentnode)
{
	if(currentnode!=NULL)
	{
		inorder(currentnode->left);
		cout<<currentnode->data;
		inorder(currentnode->right);
	}
}

void tree::preordertraversal(node *currentnode)
{
	if(currentnode!=NULL)
	{
	   cout<<currentnode->data;
		preordertraversal(currentnode->left);
		preordertraversal(currentnode->right);	
	}
}

void tree::postordertraversal(node *currentnode)
{
	if(currentnode!=NULL)
	{   
		preordertraversal(currentnode->left);
		postordertraversal(currentnode->right);
		cout<<currentnode->data;
	}
}

int tree::countnodes(node *currentnode)
        {
            if(currentnode != NULL)
            {
                countnodes(currentnode->left);
                count++;
                countnodes(currentnode->right);
                
            }
            return count;
            
        }
        
		
int tree::countleafnodes(node *currentnode)
        {
            if(currentnode != NULL)
            {
                countleafnodes(currentnode->left);
                if((currentnode->left == NULL) && (currentnode->right == NULL))
                {
                    count++;
                }
                countleafnodes(currentnode->right);
            }
            return count;
        }
        



int main()
{
int ch,n;
tree tr;
do
{
cout<<"What do you want to perform\n\n";
cout<<"1.Create a binary tree\n";
cout<<"2.In Order Traversal\n";
cout<<"3.Pre Order Traversal\n";
cout<<"4.Post Order Traversal\n";
cout<<"5. Count Total Number Of Nodes \n";
cout<<"6.Count Leaf Nodes\n";
cout<<"7.Exit\n\n";
cout<<"Enter your choice\n";
cin>>ch;
switch(ch)
{
	case 1 :tr.create();
	        break;
	case 2 :tr.inorder(tr.root);  
	        break;
	case 3 :tr.preordertraversal(tr.root);
	        break;  
	case 4 :tr.postordertraversal(tr.root);
	        break;		      
	
	case 5:cout<<"Number of nodes in tree = "<<tr.countnodes(tr.root);
	       cout<<"\n";
		   break;   
	case 6:cout<<"Total Number Of Leaf Nodes in tree ="<<tr.countleafnodes(tr.root);
	       cout<<"\n";
		   break;	   
	case 7:cout<<"Bye\n";
	       return 0;
	       break;   
	default:cout<<"Wrong Choice\n";
            break; 
}
}
while(ch!=3);
}

Leave a Comment