Operations of Binary Trees

Operations of Binary Trees

Various operations that can be performed on the binary trees are,

1. Creation of binary tree.

2. Insertion of a node in the tree.

3. Display of a binary tree.

 

1. Creation of simple binary tree

Now we will understand the concept of binary tree by creating a simple binary tree. When the data will be entered by the user, the first element will form the root node. For all the next elements user has to enter whether that element has to be inserted as a left child or a right child of previous node. For the sake of understanding, let us build the simple binary tree for some elements.

Let us take value 10. Now root node will be formed for 10.

If next element is say 12 then user will be asked for his choice, I mean, he will be asked if 12 is attached to the left or right of 10. If user answers l or L (that means left) then tree will be

Then if the next element is 8 then again user has to give his choice, whether it is L(left) or R(right). That means first whether user want to attach 8 left or right of 10 will be asked, if user answers L then again whether user want to attach 8 to left or right of 12 will be asked, if he answer R then the node 8 will be attached as a right child of 12.

If the next element is 17 and user want to attach it as a right child of 10 then,

Thus a simple binary tree will be generated. The principle idea behind this creation is always ask the user where he wants to attach the next node and always start scanning the tree from root. Now let us see the C program for it.

The C structure for node of a binary tree can be represented as

typedef struct bin

{

   int data;

   struct bin *left;

   struct bin *right;

}node;

The insertion of a node in the binary tree can be done using following function.

void TREE_ CLASS::insert(node *root, node *New)

{

char ch;

cout<<"\n Where to insert left/right of "<<root‒>data<<": ";

ch=getche();

if((ch= ='r') | | (ch= ='R'))

{

   if(root‒>right= = NULL)

   {

      root‒>right=New;

   }

   else

      insert(root‒>right,New);

   }

   else

   {

      if (root‒>left= = NULL)

      {

         root‒>left = New;

      }

      else

         insert(root‒>left,New);

   }

}

Initially root = NULL

Then we will create a node containing a value 10 as follows

As root = NULL, we will call New node as root,

Now onward if we want to insert any node in the tree we will call insert function. Now suppose we want to insert 12 then there are two cases.

i) Insertion of a node as a left child

if(root→left = = NULL)

root→left =New

ii) Insertion of a node as a right child

if(root→right = = NULL)

root→right = New

Suppose we want to insert 17 as a right child of node 10 then,

Now further if we want to insert node 8 as a right child of node 12 then

insert (root → left, New);

by this we will reach at left node of 10 and then attach 8 as a right child of 12.

After creation of tree it can be traversed using inorder, preorder and postorder traversals.

The implementation of above routines is illustrated by following programs.

C++ Program

/**************************************************************************

Program for creation of a binary tree and display the tree using recursive inorder, preorder and postorder traversals.

**************************************************************************/

#include<iostream>

using namespace std;

class TREE _ CLASS

{

private:

typedef struct bin

{

    int data;

    struct bin *left;

    struct bin *right;

}node;/*Binary tree structure*/

public:

node *New,*root;

TREE _CLASS();

void create();

void insert(node *, node *);

void inorder(node *);

void preorder(node *);

void postorder(node *);

};

TREE _CLASS::TREE_CLASS()

{

root=NULL;

void TREE _CLASS::create()

{

   char ans='y';

   do

   {

      New = new node;

      cout<<"\n Enter The Element: ";

      cin>>New‒>data;

      New‒>left=NULL;

      New‒>right=NULL;

      if(root= = NULL)

          root=New;

      else

          insert(root,New);

      cout<<"\n Do You want To Enter More elements?(y/n): ";

      ans=getche();

   }while(ans= ='y' || ans = = 'Y');

clrscr();

}

void TREE _CLASS::insert(node *root, node *New)

{

char ch;

cout<<"\n Where to insert left/right of "<<root‒>data<<": ";

ch=getche();

if((ch= ='r') || (ch= ='R'))

{

   if(root‒>right = = NULL)

   {

      root‒>right = New;

   }

   else

   insert(root‒>right,New);

}

else

{

   if (root‒>left= = NULL)

   {

      root‒>left=New;

   }

   else

      insert(root‒>left,New);

   }

}

void TREE_ CLASS::inorder(node *temp)

{

if(temp!= NULL)

{

   inorder(temp‒>left);

   cout<<" "<<temp‒>data;

   inorder(temp‒>right);

}

}

void TREE _ CLASS::preorder(node *temp)

{

if(temp!=NULL)

{

   cout<<" "<<temp‒>data;

   preorder(temp‒>left);

   preorder(temp‒>right);

}

}

void TREE _CLASS::postorder(node *temp)

if(temp!=NULL)

{

   postorder(temp‒>left);

   postorder(temp‒>right);

   cout<<" "<<<temp‒>data;

}

}

void main()

{

int choice;

TREE_ CLASS obj;

clrscr();

do

{

   cout<<"\n Program For Implementing Simple Binary Tree";

   cout<<"\n 1.Create";

   cout<<"\n 2.Inorder";

   cout<<"\n 3.Preorder";

   cout<<"\n 4.Postorder";

   cout<<"\n 5.Exit";

   cout<<"\n\t Enter Your Choice: ";

   cin>>choice;

   switch(choice)

   {

      case 1:obj.create();

          break;

      case 2:if(obj.root = = NULL)

          cout<<"Tree Is not Created!";

          else

          obj.inorder(obj.root);

          break;

      case 3:if(obj.root= = NULL)

          cout<<"Tree Is Not Created!";

          else

          obj.preorder(obj.root);

          break;

      case 4.if(obj.root= = NULL)

          cout<<"Tree Is Not Created!";

          else

          obj.postorder(obj.root);

          break;

   }

}while(choice!=5);

}

Output

Program For Implementing Simple Binary Tree

1.Create

2.Inorder

3.Preorder

4.Postorder

5.Exit

Enter Your Choice: 1

Enter The Element: 10

Do You want To Enter More elements? (y/n): y

Enter The Element: 8

Where to insert left/right of 10: 1

Do You want To Enter More elements?(y/n): y

Enter The Element: 7

Where to insert left/right of 10: 1

Where to insert left/right of 8: 1

Do You want To Enter More elements?(y/n); y

Enter The Element: 9

Where to insert left/right of 10: 1

Where to insert left/right of 8: r

Do You want To Enter More elements?(y/n): y

Enter The Element: 12

Where to insert left/right of 10: r

Do You want To Enter More elements? (y/n): y

Enter The Element: 11

Where to insert left/right of 10: r

Where to insert left/right of 12: 1

Do You want To Enter More elements?(y/n): y

Enter The Element: 13

Where to insert left/right of 10: r

Where to insert left/right of 12: r

Do You want To Enter More elements?(y/n):

Program For Implementing Simple Binary Tree

1.Create

2.Inorder

3.Preorder

4.Postorder

5.Exit

Enter Your Choice: 2

7 8 9 10 11 12 13

Program For Implementing Simple Binary Tree

1.Create

2.Inorder

3.Preorder

4.Postorder

5.Exit

Enter Your Choice: 3

10 8 7 9 12 11 13

Program For Implementing Simple Binary Tree

1.Create

2.Inorder

3.Preorder

4.Postorder

5.Exit

Enter Your Choice: 4

7 9 8 11 13 12 10

Program For Implementing Simple Binary Tree

1.Create

2.Inorder

3.Preorder

4.Postorder

5.Exit

Enter Your Choice: 5

 

Review Question

1. Explain binary tree traversal with syntax.