Data Structure and Algorithm

#include "iostream.h"
#include "conio.h"

Image via Wikipedia

Fig: Binary Search Tree

struct TREE //Structure to represent a tree
{
 int data;
 struct TREE *right,*left,*root;
};

typedef TREE tree;

tree *New;
void create() //Function to create a node of a tree
{
 New = new tree;
 New -> left = NULL;
 New -> right = NULL;
}

Image via Wikipedia

Fig: Binary Search Tree

void insert(tree *&t,int Item) //Function to insert item on a tree
{
 if(t == NULL) //If tree doesn't exist
  {
   t = new tree; //make a node
   t -> data = Item; //insert item
   t -> left = NULL; //initialize left pointer
   t -> right = NULL; //initialize right pointer
   t -> root = t; //initialize root
   return; //return from function
  }

 tree *trav = t; //set trav to root
 if(Item < trav -> data) //if Item to be inserted is less than root item
  {
   if(trav -> left == NULL) //if no Item on left
    {
     create(); //create a node
     New -> data = Item; //insert item
     trav -> left = New; //initialize left
    }
   else
    insert(trav -> left,Item); //else, go to left
  }

 else
  {
   if(trav -> right == NULL) //if no Item on right
    {
     create(); //create a node
     New -> data = Item; //insert item
     trav -> right = New; //initialize right
    }
   else
    insert(trav -> right,Item); //else, go to right
  }
}

void preorder(tree *t) //Function to print tree in preorder
{
 if(t != NULL)
  {
   cout << t -> data << ' ';
   preorder(t -> left);
   preorder(t -> right);
  }
}

void inorder(tree *t) //Function to print tree in inorder
{
 if(t != NULL)
  {
   inorder(t -> left);
   cout << t -> data << ' ';
   inorder(t -> right);
  }
}

void postorder(tree *t) //Function to print tree in postorder
{
 if(t != NULL)
  {
   postorder(t -> left);
   postorder(t -> right);
   cout << t -> data << ' ';
  }
}

int main()
{
 tree *tr1 = NULL;
 int n = 0;
 cout << "Enter Numbers,";
 cout << "\nInput -999 to Stop,\n";
 while(n != -999)
  {
   cin >> n;
   if(n != -999)
     insert(tr1,n); //Insert data to tree
  }

 cout << endl << endl << "Preorder : "; //Print tree in Preorder
 preorder(tr1);
 cout << endl << endl << "Inorder : "; //Print tree in Inorder
 inorder(tr1);
 cout << endl << endl << "Postorder : "; //Print tree in Postorder
 postorder(tr1);
 getch();
 return 0;
}