Suppose T is a Binary Tree ADT. Assume, as the book does, that T is a proper bin

Question

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.

Explanation / Answer

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

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.