Data Structure and Algorithm

#include <iostream.h>
#include <conio.h>

class tree
{
private:
  int data;
  tree *left,*right;
public:
  tree() {left = right = NULL;}
  void insert(tree *&,int);
  void inorder(tree *); //function to print tree in Inorder
  void preorder(tree *); //function to print tree in Preorder
  void postorder(tree *); //function to print tree in Postorder
  int getdata() {return data;}
  ~tree()
  {
   delete left;
   delete right;
  }
};

void tree::insert(tree *&tr,int Item)
{
if(tr == NULL)
  {
   tr = new tree;
   tr -> left = NULL;
   tr -> right = NULL;
   tr -> data = Item;
   return;
  }

tree *New,*temp;
temp = tr;
if(Item < temp -> data) //goto left
{
  if(temp -> left == NULL)
   {
    New = new tree;
    New -> left = NULL;
    New -> right = NULL;
    New -> data = Item;
    temp -> left = New;
   }
  else
   insert(temp -> left,Item);
}

else //goto right
  {
   if(temp -> right == NULL)
    {
     New = new tree;
     New -> left = NULL;
     New -> right = NULL;
     New -> data = Item;
     temp -> right = New;
    }
   else
    insert(temp -> right,Item);
  }
}

void tree::inorder(tree *tr)
{
if(tr != NULL)
{
  inorder(tr -> left); //goto left
  cout << tr -> getdata() << ' '; //print data
  inorder(tr -> right); //goto right
}
}

void tree::preorder(tree *tr)
{
if(tr != NULL)
{
  cout << tr -> getdata() << ' '; //print data
  preorder(tr -> left); //goto left
  preorder(tr -> right); //goto right
}
}

void tree::postorder(tree *tr)
{
if(tr != NULL)
{
  postorder(tr -> left); //goto left
  postorder(tr -> right); //goto right
  cout << tr -> getdata() << ' '; //print data
}
}

int main()
{
tree *t = NULL;
int m,n;
cout << "How many numbers? ";
cin >> n;
cout << "\nEnter " << n << " Numbers\n";
for(int i = 0;i < n;i++)
  {
   cin >> m;
   t -> insert(t,m); //Insert Items to tree
  }

cout << "\nInorder : ";
t -> inorder(t);
cout << "\nPreorder : ";
t -> preorder(t);
cout << "\nPostorder : ";
t -> postorder(t);
getch();
return 0;
}

OUTPUT

How many numbers? 6

Enter 6 Numbers

16 11 19 13 22 14

Inorder : 11 13 14 16 19 22

Preorder : 16 11 13 14 19 22

Postorder : 14 13 11 22 19 16

Download Original File

Tree using C++

/****************************************
APPLICATION : Program to create a Heap
CODED BY    : Ankit Pokhrel
COMPILED ON : Borland C++ Ver 5.02
DATE         : 2010 - October - 26
****************************************/

#include <iostream.h>
#include <conio.h>

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

typedef Node node;

node *New;
void create() //function to create and initialize a node
{
New = new node;
New -> left = NULL;
New -> right = NULL;
}

node *loc;
int n,*key;
void find(node *nd,int Item) //function to find the location of an item
{
if(nd != NULL)
  {
   if(nd -> data == Item)
    loc = nd; //save location
   find(nd -> left,Item);
   find(nd -> right,Item);
  }
}

void swap(int a,int b) //function to swap elements in an array (key)
{
int x = key[a];
int y = key[b];
key[a] = y;
key[b] = x;
}

void arrange() //function to arrange the input array using the property of heap
{
for(int i = 2;i <= n;i++)
  {
   int parent = int(i/2);
   int j = i;
   if(key[j] > key[parent])
   {
    while(parent >= 1)
    {
     if(key[j] > key[parent])
      swap(j,parent);
     j = parent;
     parent = parent/2;
    }
   }
  }
}

void makeHeap(node *&n,int Item,int parent) //function to build a heap from input array
{
if(n == NULL) //if first data
  {
   n = new node;
   n -> data = Item;
   n -> left = NULL;
   n -> right = NULL;
   return;
  }

create(); //create a node
New -> data = Item; //insert data
find(n,parent); //find location of parent of an item
node *p = loc;
if(p -> left == NULL) //if left of parent is empty
  p -> left = New;
else
  p -> right = New;
}

void display() //display the data of heap
{
for(int i = 1;i <= n;i++)
  cout << key[i] << ' ';
}

int main()
{
node *nd = NULL;
cout << "How many numbers? ";
cin >> n;
key = new int[n+1]; //allocate memory
cout << endl << "Enter " << n << " elements\n";
for(int i = 1;i <= n;i++)
  cin >> key[i];
arrange(); //arrange input array
for(int i = 1;i <= n;i++)
  {
   int parent = int(i/2);
   makeHeap(nd,key[i],key[parent]);
  }

cout << "\nHeap Created";
cout << "\n------------\n";
display();
getch();
return 0;
}

OUTPUT

How many numbers? 8

Enter 8 elements
44 30 50 22 60 55 77 55

Heap Created
77 55 60 50 30 44 55 22

DESCRIPTION

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) = key(B). This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap. (Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a min-heap.)

The binary heap data structures is an array that can be viewed as a complete binary tree. Each node of the binary tree corresponds to an element of the array. The array is completely filled on all levels except possibly lowest.

The root of the tree A[1] and given index i of a node, the indices of its parent, left child and right child can be computed

PARENT (i)
  return floor(i/2)
LEFT (i)
  return 2i
RIGHT (i)
  return 2i + 1

Let's try these out on a heap to make sure we believe they are correct. Take this heap,

which is represented by the array [20, 14, 17, 8, 6, 9, 4, 1].

We'll go from the 20 to the 6 first. The index of the 20 is 1. To find the index of the left child, we calculate 1 * 2 = 2. This takes us (correctly) to the 14. Now, we go right, so we calculate 2 * 2 + 1 = 5. This takes us (again, correctly) to the 6.

Now let's try going from the 4 to the 20. 4's index is 7. We want to go to the parent, so we calculate 7 / 2 = 3, which takes us to the 17. Now, to get 17's parent, we calculate 3 / 2 = 1, which takes us to the 20.

Download Original File

Heap.cpp

/***************************************************************************
 Postfix -> Infix
 The following algorithm works for the expressions whose infix form does
 not require parenthesis to override conventional precedence of operators.
 1) Create the Expression Tree from the postfix expression
 2) Run in-order traversal on the tree.

 Postfix -> Prefix
 1) Create the Expression Tree from the postfix expression
 2) Run pre-order traversal on the tree.

 ----------------------------------------------------------------------------------------------
 ALGORITHM FOR CREATING EXPRESSION TREE FROM POSTFIX EXPRESSION
 ----------------------------------------------------------------------------------------------
 1) Examine the next element in the input.
 2) If it is operand then
  i) create a leaf node i.e. node having no child
  ii) copy the operand in data part
  iii) PUSH node's address on stack
 3) If it is an operator, then
   i) create a node
  ii) copy the operator in data part
  iii) POP address of node from stack and assign it to node->right_child
   iv) POP address of node from stack and assign it to node->left_child
   v) PUSH node's address on stack
 5) If there is more input go to step 2
 6) If there is no more input, POP the address from stack,
    which is the address of the ROOT node of Expression Tree.
 ----------------------------------------------------------------------------------------

 Evaluating an expression involves two phases:
 1) Create an expression tree for given expression
 2) Evaluate the tree recursively

 ---------------------------------------------------------------------------------------
 ALGORITHM TO EVALUATE THE EXPRESSION FROM EXPRESSION TREE
 ---------------------------------------------------------------------------------------
 1)if root != NULL
 2)if current node contains an operator
    a) x = Evaluate Tree(root -> left_child)
    b) y = Evaluate Tree(root -> right_child)
    c) perform operation on x and y, specified by the operator
       and store result in a variable
    d) Return variable
 3)else, Return root->data
 ----------------------------------------------------------------------------------------
****************************************************************************/

/***************************************************************************
 APPLICATION : Conversion from Postfix to Infix and Prefix (using Expression Tree)
               and Evaluation of Expression Tree
 CODED BY    : Ankit Pokhrel
 COMPILED ON : Borland C++ Ver 5.02
 DATE     : 2010 - August - 04
***************************************************************************/

#include "iostream.h"
#include "conio.h"
#include "stdio.h"
#include "stdlib.h"
#include "math.h"

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

typedef TREE tree;

/********* Stack Using Linked List **********/

struct Stack //Structure to represent Stack
{
 struct TREE *data;
 struct Stack *next,*head,*top; //Pointers to next node,head and top
};

typedef struct Stack node;

node *Nw; //Global Variable to represent node

void initialize(node *&n)
{
 n = new node;
 n -> next = n -> head = n -> top = NULL;
}

void create(node *n)
{
 Nw = new node; //Create a new node
 Nw -> next = NULL; //Initialize next pointer field
 if(n -> head == NULL) //if first node
  {
  n -> head = Nw; //Initialize head
   n -> top = Nw; //Update top
  }
}

void push(node *n,tree *ITEM)
{
 node *temp = n -> head;
 if(n -> head == NULL) //if First Item is Pushed to Stack
  {
   create(n); //Create a Node
  n -> head -> data = ITEM; //Insert Item to head of List
   n -> head = Nw;
   return; //Exit from Function
  }

 create(n); //Create a new Node
 Nw -> data = ITEM; //Insert Item
 while(temp -> next != NULL)
    temp = temp -> next; //Go to Last Node

 temp -> next = Nw; //Point New node
 n -> top = Nw; //Update top
}

node* pop(node *n)
{
 node *temp = n -> head,*deleted;
 if(n -> top == NULL) //If the Stack is Empty
  {
    return NULL;
   }

 if(n -> top == n -> head) //If only one Item
  {
    deleted = n -> head;
    n -> head = n -> top = NULL; //Set head and top to Null
    return deleted; //Return deleted node
   }

 while(temp -> next != n -> top)
  temp = temp -> next; //move pointer temp to second last node

 temp -> next = NULL; //Second last node points to NULL
 deleted = n -> top; //Save topmost node
 n -> top = temp; //Update top
 return deleted; //Return deleted node
}

int Empty(node *nd) //function to check if the stack is empty or not
{
 if(nd -> top == NULL)
  return 1; //empty
 else
  return 0;
}

/*********** Tree Section ************/

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

void insert(tree *&t,char Item,int pass) //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
   if(pass)
   t -> root = t; //initialize root
   return; //return from function
  }

 create();
 New -> data = Item;
}

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);
  }
}

/*************** Main Program Section *************/

int isOperator(char ch)
{
 if(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '$')
  return 1;
 else
  return 0;
}

bool check(node *nd)
{
 if(nd != NULL)
  return true;
 else
  return false;
}

float calculate(float opr1,float opr2,char oprator)
{
 float value;
 if(oprator == '+')
  value = opr1 + opr2;
 if(oprator == '-')
  value = opr1 - opr2;
 if(oprator == '*')
  value = opr1 * opr2;
 if(oprator == '/')
  if(opr2 != 0)
   value = opr1 / opr2;
 if(oprator == '$')
  value = pow(opr1,opr2);

 return value;
}

float evaluate(tree *t)
{
 float x,y,result;
 char ch[3];
 if(t != NULL)
 {
  if(isOperator(t -> data))
   {
    x = evaluate(t -> left); //go to left
    y = evaluate(t -> right); //go to right
    result = calculate(x,y,t -> data); //calculate
    return result;
   }

  else
   {
    ch[0] = t -> data;
    ch[1] = '\0';
    result = atof(ch); //convert to float
    return result;
   }
 }
}

int main()
{
 char postfix[60];
 cout << "Enter a valid Postfix Expression\n";
 cout << "(in a single line, without spaces)\n";
 int i = 0;
 while(postfix[i - 1] != '\n')
  postfix[i++] = getchar();
 int len = i - 1,pass = true,valid = true;

 node *stk,*nd; //create a stack
 initialize(stk);
 tree *tr = NULL,*value;

 i = 0;
 while(i < len) //while there is data
  {
   if(!isOperator(postfix[i])) //if operand
    {
     create();
     New -> data = postfix[i];
     push(stk,New); //push address of tree node to stack
    }

   else //if operator
    {
     insert(tr,postfix[i],pass); //create a node of tree and insert operator
     if(pass) //if first pass
     {
      nd = pop(stk);
      valid = check(nd);
      if(!valid)
       break;
      value = nd -> data; //pop address
      tr -> right = value; //assign to left child
      nd = pop(stk);
      valid = check(nd);
      if(!valid)
       break;
      value = nd -> data; //pop address
      tr -> left = value; //assign to right child
      pass = false; //reset pass
      push(stk,tr); //push address to stack
     }

     else
      {
       nd = pop(stk);
       valid = check(nd);
       if(!valid)
         break;
       value = nd -> data; //pop address
       New -> right = value; //assign to left child
       nd = pop(stk);
       valid = check(nd);
       if(!valid)
        break;
       value = nd -> data; //pop stack
       New -> left = value; //assign to right child
       push(stk,New); //push address to stack
      }
    }

   i++; //update i
  }

 if(!Empty(stk))
 {
  tr -> root = pop(stk) -> data; //Last data of stack is root of tree
  tr = tr -> root;
 }

 if(!Empty(stk)) //if stack is not empty
  valid = false;

 if(!valid)
  {
   cout << "\nThe Given Postfix Expression is not Valid";
   cout << "\nCheck above Expression and try again...";
   getch();
   return 0; //exit from program
  }

 cout << "\nInfix : ";
 inorder(tr); //Inorder traversal gives Infix of expression
 cout << "\n\nPrefix : ";
 preorder(tr); //Postorder traversal gives Postfix of expression

 float result = evaluate(tr);
 cout << endl << "\nSolution : " << result;
 getch();
 return 0;
}

/****************************************************************************
 ------------
 LIMITATIONS
 ------------
 1)Above Alogorithm Works only for the expressions whose infix form does
   not require parenthesis to override conventional precedence of operators.
 2)This Program doesn't work for Operand greater than 9.
 3)Above Algorithm Works only for Binary Operators.
 4)This Program Works only for operators +,-,*,/ and $(Power).
****************************************************************************/

/***************************************************************************
 Prefix -> Infix
 The following algorithm works for the expressions whose infix form does
 not require parenthesis to override conventional precedence of operators.
 1) Create the Expression Tree from the prefix expression
 2) Run in-order traversal on the tree.

 Prefix -> Postfix
 1) Create the Expression Tree from the prefix expression
 2) Run post-order traversal on the tree.

 --------------------------------------------------------------------------------------------
 ALGORITHM FOR CREATING EXPRESSION TREE FROM PREFIX EXPRESSION
 --------------------------------------------------------------------------------------------
 1) Reverse the prefix expression
 2) Examine the next element in the input.
 3) If it is operand then
  i) create a leaf node i.e. node having no child
  ii) copy the operand in data part
  iii) PUSH node's address on stack
 4) If it is an operator, then
   i) create a node
  ii) copy the operator in data part
  iii) POP address of node from stack and assign it to node->left_child
   iv) POP address of node from stack and assign it to node->right_child
   v) PUSH node's address on stack
 5) If there is more input go to step 2
 6) If there is no more input, POP the address from stack,
    which is the address of the ROOT node of Expression Tree.
 --------------------------------------------------------------------------------------

 Evaluating an expression involves two phases:
 1) Create an expression tree for given expression
 2) Evaluate the tree recursively

 ---------------------------------------------------------------------------------------
 ALGORITHM TO EVALUATE THE EXPRESSION FROM EXPRESSION TREE
 ---------------------------------------------------------------------------------------
 1)if root != NULL
 2)if current node contains an operator
    a) x = Evaluate Tree(root -> left_child)
    b) y = Evaluate Tree(root -> right_child)
    c) perform operation on x and y, specified by the operator
       and store result in a variable
    d) Return variable
 3)else, Return root->data
 ---------------------------------------------------------------
  (Above Algorithms are from programmersheaven.com)
****************************************************************************/

/***************************************************************************
 APPLICATION : Conversion from Prefix to Infix and Postfix (using Expression Tree)
               and Evaluation of Expression Tree
 CODED BY    : Ankit Pokhrel
 COMPILED ON : Borland C++ Ver 5.02
 DATE     : 2010 - July - 30
***************************************************************************/

#include "iostream.h"
#include "conio.h"
#include "stdio.h"
#include "stdlib.h"
#include "math.h"

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

typedef TREE tree;

/********* Stack Using Linked List **********/

struct Stack //Structure to represent Stack
{
 struct TREE *data;
 struct Stack *next,*head,*top; //Pointers to next node,head and top
};

typedef struct Stack node;

node *Nw; //Global Variable to represent node

void initialize(node *&n)
{
 n = new node;
 n -> next = n -> head = n -> top = NULL;
}

void create(node *n)
{
 Nw = new node; //Create a new node
 Nw -> next = NULL; //Initialize next pointer field
 if(n -> head == NULL) //if first node
  {
  n -> head = Nw; //Initialize head
   n -> top = Nw; //Update top
  }
}

void push(node *n,tree *ITEM)
{
 node *temp = n -> head;
 if(n -> head == NULL) //if First Item is Pushed to Stack
  {
   create(n); //Create a Node
  n -> head -> data = ITEM; //Insert Item to head of List
   n -> head = Nw;
   return; //Exit from Function
  }

 create(n); //Create a new Node
 Nw -> data = ITEM; //Insert Item
 while(temp -> next != NULL)
    temp = temp -> next; //Go to Last Node

 temp -> next = Nw; //Point New node
 n -> top = Nw; //Update top
}

node* pop(node *n)
{
 node *temp = n -> head,*deleted;
 if(n -> top == NULL) //If the Stack is Empty
  {
    return NULL;
   }

 if(n -> top == n -> head) //If only one Item
  {
    deleted = n -> head;
    n -> head = n -> top = NULL; //Set head and top to Null
    return deleted; //Return deleted node
   }

 while(temp -> next != n -> top)
  temp = temp -> next; //move pointer temp to second last node

 temp -> next = NULL; //Second last node points to NULL
 deleted = n -> top; //Save topmost node
 n -> top = temp; //Update top
 return deleted; //Return deleted node
}

int Empty(node *nd) //function to check if the stack is empty or not
{
 if(nd -> top == NULL)
  return 1; //empty
 else
  return 0;
}

/*********** Tree Section ************/

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

void insert(tree *&t,char Item,int pass) //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
   if(pass)
   t -> root = t; //initialize root
   return; //return from function
  }

 create();
 New -> data = Item;
}

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 << ' ';
  }
}

/*************** Main Program Section *************/

void reverse(char ch[],int len)
{
 char temp[60];
 int j = 0;
 for(int i = len - 1;i >= 0;i--)
   temp[j++] = ch[i];

 for(int i = 0;i < len;i++)
  ch[i] = temp[i];
}

int isOperator(char ch)
{
 if(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '$')
  return 1;
 else
  return 0;
}

bool check(node *nd)
{
 if(nd != NULL)
  return true;
 else
  return false;
}

float calculate(float opr1,float opr2,char oprator)
{
 float value;
 if(oprator == '+')
  value = opr1 + opr2;
 if(oprator == '-')
  value = opr1 - opr2;
 if(oprator == '*')
  value = opr1 * opr2;
 if(oprator == '/')
  if(opr2 != 0)
   value = opr1 / opr2;
 if(oprator == '$')
  value = pow(opr1,opr2);

 return value;
}

float evaluate(tree *t)
{
 float x,y,result;
 char ch[3];
 if(t != NULL)
 {
  if(isOperator(t -> data))
   {
    x = evaluate(t -> left); //go to left
    y = evaluate(t -> right); //go to right
    result = calculate(x,y,t -> data); //calculate
    return result;
   }

  else
   {
    ch[0] = t -> data;
    ch[1] = '\0';
    result = atof(ch); //convert to float
    return result;
   }
 }
}

int main()
{
 char prefix[60];
 cout << "Enter a valid Prefix Expression\n";
 cout << "(in a single line, without spaces)\n";
 int i = 0;
 while(prefix[i - 1] != '\n')
  prefix[i++] = getchar();
 int len = i - 1,pass = true,valid = true;
 reverse(prefix,len); //reverse the prefix expression

 node *stk,*nd; //create a stack
 initialize(stk);
 tree *tr = NULL,*value;

 i = 0;
 while(i < len) //while there is data
  {
   if(!isOperator(prefix[i])) //if operand
    {
     create();
     New -> data = prefix[i];
     push(stk,New); //push address of tree node to stack
    }

   else //if operator
    {
     insert(tr,prefix[i],pass); //create a node of tree and insert operator
     if(pass) //if first pass
     {
      nd = pop(stk);
      valid = check(nd);
      if(!valid)
       break;
      value = nd -> data; //pop address
      tr -> left = value; //assign to left child
      nd = pop(stk);
      valid = check(nd);
      if(!valid)
       break;
      value = nd -> data; //pop address
      tr -> right = value; //assign to right child
      pass = false; //reset pass
      push(stk,tr); //push address to stack
     }

     else
      {
       nd = pop(stk);
       valid = check(nd);
       if(!valid)
         break;
       value = nd -> data; //pop address
       New -> left = value; //assign to left child
       nd = pop(stk);
       valid = check(nd);
       if(!valid)
        break;
       value = nd -> data; //pop stack
       New -> right = value; //assign to right child
       push(stk,New); //push address to stack
      }
    }

   i++; //update i
  }

 if(!Empty(stk))
 {
  tr -> root = pop(stk) -> data; //Last data of stack is root of tree
  tr = tr -> root;
 }

 if(!Empty(stk)) //if stack is not empty
  valid = false;

 if(!valid)
  {
   cout << "\nThe Given Prefix Expression is not Valid";
   cout << "\nCheck above Expression and try again...";
   getch();
   return 0; //exit from program
  }

 cout << "\nInfix : ";
 inorder(tr); //Inorder traversal gives Infix of expression
 cout << "\n\nPostfix : ";
 postorder(tr); //Postorder traversal gives Postfix of expression

 float result = evaluate(tr);
 cout << endl << "\nSolution : " << result;
 getch();
 return 0;
}

/****************************************************************************
 ------------
 LIMITATIONS
 ------------
 1)Above Alogorithm Works only for the expressions whose infix form does
   not require parenthesis to override conventional precedence of operators.
 2)This Program doesn't work for Operand greater than 9.
 3)Above Algorithm Works only for Binary Operators.
 4)This Program Works only for operators +,-,*,/ and $(Power).
****************************************************************************/

/***************************************
 APPLICATION : A Complete Tree Program
 CODED BY    : Ankit Pokhrel
 COMPILED ON : Borland C++ Ver 5.02
 DATE     : 2010 - July - 27
***************************************/

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

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
{
 New = new tree;
 New -> left = NULL;
 New -> right = NULL;
}

tree *par; //parent node
tree* find(tree *t,int item)
{
 tree *loc,*ptr,*save;
 if(t == NULL) //tree doesn't exist
  {
   loc = NULL;
   par = NULL;
   return loc;
  }

 if(t -> data == item) //if root node
  {
   loc = t -> root; //set loc to root
   par = NULL; //no parent
   return loc; //return location
  }

  if(item < t -> data)
   {
    ptr = t -> left; //move to left
    save = t -> root; //save parent node
   }

  else
   {
    ptr = t -> right; //move to right
    save = t -> root; //save parent node
   }

 while(ptr != NULL)
  {
   if(item == ptr -> data)
    {
     loc = ptr; //set loc
     par = save; //set parent
     return loc; //return location
    }

   if(item < ptr -> data)
    {
     save = ptr; //save parent
     ptr = ptr -> left; //move to left
    }

   else
    {
     save = ptr; //save parent
     ptr = ptr -> right; //move to right
    }
  }

 loc = NULL; //data not found
 par = save; //save parent
 return loc; //return location
}

void caseA(int Item,tree *&tr) //if node has no or one child
{
 tree *child;
 tree *loc = find(tr,Item); //find location of the item
 if(loc -> left == NULL && loc -> right == NULL) //if no children
  child = NULL;
 else if(loc -> left != NULL) //if left child
  child = loc -> left;
 else
  child = loc -> right;

 if(par != NULL)
  {
   if(loc == par -> left) //if node to be deleted is left of parent
    par -> left = child;
   else
    par -> right = child;
  }

 else
  {
   tr -> root = child; //replace root
   tr = child;
  }
}

void caseB(int Item,tree *&tr) //if node has both children
{
 tree *suc,*loc,*parTemp;
 loc = find(tr,Item); //find location of item
 parTemp = par; //save parent of Item
 suc = loc -> right; //go to right

 while(suc -> left != NULL)
  suc = suc -> left; //go to left

 caseA(suc -> data,tr); //Delete successor using caseA
 par = parTemp; //set parent
 if(par != NULL)
  {
   if(loc == par -> left) //if node to be deleted is left of parent
    par -> left = suc;
   else
    par -> right = suc;
  }

 else
  {
   tr -> root = suc; //replace root
   tr = suc;
  }

 suc -> left = loc -> left; //set left of successor
 suc -> right = loc -> right; //set right of successor
}

tree* remove(int Item,tree *&t)
{
 tree *loc = find(t,Item); //find location
 if(loc == NULL)
  {
   cout << "Item not Found.";
   return loc;
  }

 if(loc -> right != NULL && loc -> left != NULL) //if node has both child
  caseB(Item,t); //call caseB
 else
  caseA(Item,t); //call caseA

 return loc;
}

void insert(tree *&t,int Item)
{
 if(t == NULL) //if tree doesn't exists
  {
   t = new tree; //create a tree
   t -> data = Item; //insert data
   t -> left = NULL;
   t -> right = NULL;
   t -> root = t; //initialize root
   return;
  }

 tree *trav = t;
 if(Item < trav -> data)
  {
   if(trav -> left == NULL)
    {
     create();
     New -> data = Item;
     trav -> left = New;
    }
   else
    insert(trav -> left,Item); //go to left
  }

 else
  {
   if(trav -> right == NULL)
    {
     create();
     New -> data = Item;
     trav -> right = New;
    }
   else
    insert(trav -> right,Item); //go to right
  }
}

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()
{
 tree *tr1 = NULL;
 int n = 0;
 cout << "Enter Numbers :\n";
 while(n != -999) //create a tree
  {
   cin >> n;
   if(n != -999)
     insert(tr1,n);
  }

 inorder(tr1);

 cout << "\nDelete : ";
 cin >> n;
 tree *temp = remove(n,tr1);
 cout << endl;
 inorder(tr1);
 if(temp != NULL)
  cout << "\nDeleted Item : " << temp -> data;
 getch();
 return 0;
}

/**********************************************************************
 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;
}

/**********************************************************************
 APPLICATION : Program to make a tree (Given Preorder 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 pre[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 lenPre,int lenIn)
{
 if(lenPre != lenIn) //If length of Preorder input and Inorder input do not match
   return 1; //return error

  int valid;
  for(int j = 0;j < lenPre;j++) //for every preorder data
   {
    valid = false; //assume that data is not in Inorder
    for(int k = 0;k < lenIn;k++)
     if(in[k] == pre[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;
    }

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

 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 lenPre,lenIn,i = 0;
 //Scan Preorder and Inorder Datas
 cout << "Enter Preorder and Inorder Data Correctly,\n";
 cout << "Input -999 as last Data,\n\n";
 cout << "Preorder : ";
 do
  {
   cin >> pre[i];
   i++;
  }while(pre[i-1] != -999);

 lenPre = i - 1;

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

 lenIn = i - 1;

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

 create(pre[0]);
 i = 1;
 while(i < lenPre)
  {
   index = Find_Index(lenPre,pre[i]); //find index
   trav = root; //Start from root
   construct(pre[i],lenPre); //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;
}

#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;
}