Suppose T is a Binary Tree ADT Assume as the book does that

Suppose T is a Binary Tree ADT. Assume, as the book does, that T is a proper binary tree. That is, if y is an internal node, then v has a left and a right child. Design algorithms for the following methods: postorderBefore(v): returns the node visited before v in a postorder traversal of T. postorderNext(v): returns the node visited after v in a postorder traversal of T. For example, consider the binary tree in .Figure 2.34 of your hook. Let v be the left child of the root node (the one containing \"/\" and labeled \'2\'). Then postorderBefore(v) returns the node containing + and labeled \"r while postorderNext(v) returns the node containing 3 and labeled \'12\'. Explain why your algorithms are correct and determine their running times.

Solution

//EXAMPLE PROGRAM FOR BINARY TREE
# include <iostream.h>
# include <alloc.h>
# include <stdlib.h>
# include <conio.h>
struct tree_element
{
struct tree_element *left;
int item;
struct tree_element *right;
};
typedef struct tree_element node;
void create(node *record,int n)
{
if(n > record->item)
{
   if(record->right==NULL)
   {
   record->right=(node *)malloc(sizeof(node));
   record=record->right;
   record->item=n;
   record->left=NULL;
   record->right=NULL;
   }
   else
   create(record->right,n);
}
else
{
   if(n<record->item)
   {
   if(record->left==NULL)
   {
       record->left=(node *)malloc(sizeof(node));
       record=record->left;
       record->item=n;
       record->left=NULL;
       record->right=NULL;
   }
   else
   create(record->left,n);
   }
   else
   cout<<\" No. is duplicate \";
   return;
}
}
void inorder(node *record)
{
if(record!=NULL)
{
inorder(record->left);
cout<<record->item;
inorder(record->right);
}
return;
}
void preorder(node *record)
{
if(record!=NULL)
{
   cout<<record->item;
   preorder(record->left);
   preorder(record->right);
}
return;
}
void postorder(node *record)
{
if(record!=NULL)
{
   postorder(record->left);
   postorder(record->right);
   cout<<record->item;
}
}
void main()
{
node *tree;
int num,choice;
clrscr();
tree=(node *)malloc(sizeof(node));
cout<<\"\ BINARY TREE TRAVERSAL \";
cout<<\"\ 1. INORDER \";
cout<<\"\ 2. PREORDER \";
cout<<\"\ 3. POSTORDER \";
cout<<\"\ 4. EXIT \";
cout<<\'\ First enter the nos at last enter -999 \ \";
cin>>num;
tree->item=num;
tree->left=NULL;
tree->right=NULL;
while(num!=-999)
{
   cin>>num;
   if(num==-999)
   break;
   create(tree,num);
}
do
   {
   cout<<\"\ Enter your choice \";
   cin<<choice;
   switch(choice)
   {
   case 1:
       cout<<\"\ Inorder Traversal \";
       inorder(tree);
       continue;
   case 2:
       cout<<\"\ Preorder Traversal \";
       preorder(tree);
       continue;
   case 3:
       cout<<\"\ Postorder Traversal \";
       postorder(tree);
       continue;
   }
}
while(choice!=4);
}