- #1
gruba
- 206
- 1
Homework Statement
Create a linear stack with N binary search trees (data of a tree node is an integer). Read N trees, push them on the stack. Then, empty the stack and store trees in the new array and print the content of the stack.
2. The attempt at a solution
The following code gives unexpected output (stack content is not printed correctly - look at the printing stack loop at the line [itex]\sim[/itex] 215):
Code:
#include<stdio.h>
#include<stdlib.h>
#define N 2
typedef struct
{
int num;
}TREE_INFO;
typedef struct tree_node
{
TREE_INFO treeInfo;
struct tree_node *left,*right;
}TREE_NODE;
typedef struct stack
{
TREE_NODE arr[N];
int tos;
}STACK;
int isFull(STACK *s)
{
return s->tos == N-1;
}
int isEmpty(STACK *s)
{
return s->tos ==-1;
}
int push(STACK *s,TREE_NODE *stackInfo)
{
if(isFull(s))
return0;
s->arr[++s->tos]=*stackInfo;
return1;
}
int pop(STACK *s,TREE_NODE *stackInfo)
{
if(isEmpty(s))
return0;
*stackInfo=s->arr[s->tos--];
return1;
}
TREE_NODE* emptyTheStack(STACK *s)
{
if(isEmpty(s))
return0;
int i=0;
TREE_NODE *arr=(TREE_NODE*)malloc(((s->tos+1)*sizeof(TREE_NODE))*N *1000);
while(!isEmpty(s))
arr[i++]=s->arr[s->tos--];
return arr;
}
void readTree(TREE_INFO *treeInfo)
{
do
{
printf("Enter positive integer: ");
scanf("%d",&treeInfo->num);
}
while(treeInfo->num <0);
}
TREE_NODE* searchTree(TREE_NODE *root,int num)
{
if(root ==0)
return0;
elseif(num == root->treeInfo.num)
return root;
elseif(num <= root->treeInfo.num)
return searchTree(root->left,num);
elsereturn searchTree(root->right,num);
}
TREE_NODE* formNode(TREE_INFO *treeInfo)
{
TREE_NODE*newNode=(TREE_NODE*)malloc(sizeof(TREE_NODE));
newNode->left=newNode->right=0;
newNode->treeInfo=*treeInfo;
return newNode;
}
TREE_NODE* addNodeTree(TREE_NODE *root,TREE_INFO *treeInfo)
{
if(root ==0)
return formNode(treeInfo);
if(treeInfo->num <= root->treeInfo.num)
root->left=addNodeTree(root->left,treeInfo);
else root->right=addNodeTree(root->right,treeInfo);
return root;
}
void deleteTree(TREE_NODE *root)
{
if(root !=0)
{
deleteTree(root->left);
deleteTree(root->right);
free(root);
}
}
void printTreeInorder(TREE_NODE *root)
{
if(root !=0)
{
printTreeInorder(root->left);
printf("%d ",root->treeInfo.num);
printTreeInorder(root->right);
}
}
int main()
{
int i;
TREE_INFO treeInfo;
char option;
TREE_NODE *srch,*root,*arr;
STACK st;
st.tos=-1;
i=1;
root=0;
printf("Adding N trees on the stack: \n");
while(i<=N)
{
do
{
fflush(stdin);
printf("\nEnter option: ");
scanf("%c",&option);
if(option =='A')
{
fflush(stdin);
printf("Enter data about %d. tree: \n",i);
readTree(&treeInfo);
srch=searchTree(root,treeInfo.num);
if(srch)
srch->treeInfo=treeInfo;
else
root=addNodeTree(root,&treeInfo);
}
elseif(option =='P')
{
printf("Data about %d. tree: \n",i);
printTreeInorder(root);
}
elseif(option !='0')
printf("Unknown option.\n");
}
while(option !='0');
if(push(&st,root))
printf("%d. tree is pushed on the stack.\n",i);
if(isFull(&st))
printf("Stack is full.\n");
root=0;
srch=0;
i++;
}
arr=emptyTheStack(&st);
i=1;
printf("Printing stack: \n");
while(i<=N)
{
printTreeInorder(arr);
i++;
}
if(isEmpty(&st))
printf("Stack is empty.\n");
free(arr);
return0;
}
Example program:
Code:
Enter option: A
Add node to 1. tree:10
Enter option: A
Add node to 1. tree:8
Enter option: A
Add node to 1. tree:10
Enter option: P //print a tree
Data about 1. tree:8 10//note: inorder traversal without duplicate values
Enter option:0
1. tree is pushed on the stack.
Enter option: A
Add node to 2. tree:6
Enter option: A
Add node to 2. tree:9
Enter option: P
Data about 2. tree:6 9
Enter option:0
2. tree is pushed on the stack.
Stack is full.
Print stack:
6 9
8 10
For the same input, I am getting the following output:
Code:
Print stack:
6 9
6 9
This means that the last input tree is printed N times.
Could someone point out how to resolve this error?
Thanks for replies.