1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C: Stack with binary search trees

  1. May 27, 2016 #1
    1. The problem statement, all variables and given/known data
    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 (Text):

    #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 (Text):

    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 (Text):

    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.
     
  2. jcsd
  3. May 28, 2016 #2

    Mark44

    Staff: Mentor

    No one else has posted in this thread all day. I can't speak for the others, but for myself, I don't feel like responding. Too often, others and I have made suggestions on how you could fix your code, but with no response from you, either that the reponse was helpful or that it was way out in left field.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: C: Stack with binary search trees
  1. Binary Search tree (Replies: 5)

Loading...