Data Structure and Algorithm

/**********************************************************************
 APPLICATION : Program to make a tree (Given Postorder and Inorder)
 CODED BY    : Ankit Pokhrel
 COMPILED ON : Borland Turbo C++ Ver 3.0
 DATE     : 2010 - July - 23
***********************************************************************/

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

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

typedef TREE tree;

tree *New,*trav,*root = NULL;
int post[25],in[25],index;

void create(int Item) //Function to create a node
{
 New = new tree;
 New -> left = NULL;
 New -> right = NULL;
 New -> data = Item;
 if(root == NULL) //if First Node
  {
  root = New; //Set root
   trav = root;
  }
}

int errorCheck(int lenPost,int lenIn)
{
 if(lenPost != lenIn) //If length of Preorder input and Inorder input do not match
   return 1; //return error

  int valid;
  for(int j = 0;j < lenPost;j++) //for every postorder data
   {
    valid = false; //assume that data is not in Inorder
    for(int k = 0;k < lenIn;k++)
     if(in[k] == post[j]) //find in Inorder, If found
      {
       valid = true; //set valid = true
       break; //exit from loop
      }

     if(!valid)
   return 1; //return error
   }

  return 0; //return valid
}

int Find_Index(int len,int Item) //Function to find Index
{
 for(int i = 0;i < len;i++)
  if(in[i] == Item)
   return i;
}

void construct(int Item,int len)
{
 int ind;
 ind = Find_Index(len,trav -> data);
 if(index < ind)
  {
   if(trav -> left == NULL)
    {
     create(Item); //allocate Memory
     trav -> left = New; //Insert Item
    }

   else
    {
     trav = trav -> left; //go to left
     construct(Item,len);
    }
  }

 else
  {
   if(trav -> right == NULL)
    {
     create(Item); //allocate Memory
     trav -> right = New; //Insert Item
    }

   else
    {
     trav = trav -> right; //go to right
     construct(Item,len);
    }
  }
}

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

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

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


int main()
{
 int lenPost,lenIn,i = 0;
 //Scan Preorder and Inorder Datas
 cout << "Enter Postorder and Inorder Data Correctly,\n";
 cout << "Input -999 as last Data,\n\n";
 cout << "Postorder : ";
 do
  {
   cin >> post[i];
   i++;
  }while(post[i-1] != -999);

 lenPost = i - 1;

 cout << "\nInorder : ";
 i = 0;
 do
  {
   cin >> in[i];
   i++;
  }while(in[i-1] != -999);

 lenIn = i - 1;

 int error = errorCheck(lenPost,lenIn); //Check for Errors
 if(error)
  {
   cout << "\nThe Given Expressions are not Valid.";
   getch();
   return 0; //exit from program
  }

 create(post[lenPost - 1]);
 i = lenPost - 2;
 while(i >= 0)
  {
   index = Find_Index(lenPost,post[i]); //find index
   trav = root; //Start from root
   construct(post[i],lenPost); //Insert data in right place
   i--;
  }

 cout << endl << endl << "Inorder : "; //Print tree in Inorder
 inorder(root);
 cout << endl << endl << "Preorder : "; //Print tree in Preorder
 preorder(root);
 cout << endl << endl << "Postorder : "; //print tree in Postorder
 postorder(root);

 getch();
 return 0;
}