Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Printing the linear stack of N binary search trees in C?

c

This topic has been archived. This means that you cannot reply to this topic.
No replies to this topic

#1 negru

negru

    CC Newcomer

  • Member
  • PipPip
  • 17 posts

Posted 27 May 2016 - 12:44 AM

Create a linear stack with N binary search trees (data 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.

//Example program:
 
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 //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
 
//I am getting the following output here:
Print stack:
 
6 9
6 9
 
//The last input tree is printed N times.

Could someone point out how to resolve this error?

#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))
  return 0;
  s->arr[++s->tos]=*stackInfo;
  return 1;
}
 
int pop(STACK *s,TREE_NODE *stackInfo)
{
  if(isEmpty(s))
     return 0;
  *stackInfo=s->arr[s->tos--];
  return 1;
}
 
TREE_NODE* emptyTheStack(STACK *s)
{
   if(isEmpty(s))
        return 0;
   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)
        return 0;
    else if(num == root->treeInfo.num)
        return root;
    else if(num <= root->treeInfo.num)
        return searchTree(root->left,num);
    else return 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);
           }
            else if(option == 'P')
            {
                printf("Data about %d. tree: \n",i);
                printTreeInorder(root);
            }
           else if(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);
     
    return 0;
}