Missing the lines in the tree but hopfully you get the point of the diagram. Com
ID: 3533338 • Letter: M
Question
Missing the lines in the tree but hopfully you get the point of the diagram.
Complete the trace of the nonrecursive inorder traversal algorithm diagram. Implement in C++ the nonrecursive inorder traversal algorithm for the completed trace of the nonrecursive inorder traversal algorithm binary tree<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />
Stack: Null Null
10 10 10 10 10
20 20 20 20 20 20 20
60 60 60 60 60 Visit 10 60 60 60 Visit 20
Step 1 2 3 4 5 6 7 8 9
<?xml:namespace prefix = v ns = "urn:schemas-microsoft-com:vml" />
treePtr at Step 1 60
treePtr is Null at Steps 4 and 7
30 50
Explanation / Answer
#include<stdio.h>
#include<stdlib.h>
#define iterations 20
#define UL 0
#define UR 1
#define DL 2
#define DR 3
struct node
{
int val;
node *left,*right;
};
void print_inorder(node *root)
{
node *p,*q,*temp;
int state=DL;
p=root;
q=NULL;
while(1)
{
if(state==DL)
{
if(p->left!=NULL)
{
temp=p->left;
p->left=q;
q=p;
p=temp;
}
else
{
printf("%d ",p->val);
state=DR;
}
continue;
}
else if(state==DR)
{
if(p->right!=NULL)
{
temp=p->right;
p->right=q;
q=p;
p=temp;
state=DL;
}
else
{
if(q==NULL)
break;
else
{
if(p->val<q->val)
state=UL;
else
state=UR;
}
}
continue;
}
else if(state==UL)
{
temp=q->left;
q->left = p;
p=q;
q=temp;
printf("%d ", p->val);
state=DR;
continue;
}
else if(state==UR)
{
temp=q->right;
q->right=p;
p=q;
q=temp;
if(!q)
break;
if(p->val<q->val)
state=UL;
}
}
}
void insert(node *tree,int key)
{
int flag;
node *curr;
curr=tree;
while(1)
{
if(key<curr->val)
{
if(curr->left!=NULL)
curr=curr->left;
else
{
flag=1;
break;
}
}
else
{
if(curr->right!=NULL)
curr=curr->right;
else
{
flag=2;
break;
}
}
}
if(flag==1)
{
curr->left =(node *)malloc(sizeof(node));
curr=curr->left;
curr->left=NULL;
curr->right=NULL;
curr->val=key;
}
else
{
curr->right =(node *)malloc(sizeof(node));
curr=curr->right;
curr->left=NULL;
curr->right=NULL;
curr->val=key;
}
}
int main()
{
int i,key,flag;
node *tree;
tree =(node *)malloc(sizeof(node));
tree->left=NULL;
tree->right=NULL;
printf("Initializing the tree T = () ");
key= rand()? + 1;
printf("Inserting %d ",key);
tree->val=key;
for(i=1 ; i < iterations ; i++)
{
key= rand()? + 1;
printf("Inserting %d ",key);
insert(tree,key);
}
printf("T=(");
print_inorder(tree);
printf(") ");
}