Binary tree question

This is a discussion on Binary tree question within the C Programming forums, part of the General Programming Boards category; I've been working on this for many hours now. Maybe a good night of rest will help clear my head ...

  1. #1
    Registered User
    Join Date
    Feb 2012
    Posts
    117

    Binary tree question

    I've been working on this for many hours now. Maybe a good night of rest will help clear my head and help me out.
    But I'm going to post this here tonight in hope to see something tomorrow that can help me out.

    The link to my homework is below...

    http://omega.uta.edu/~darin/CSE1320/1320-hw10.pdf

    I need to construct a binary tree and print the values out in pre-order, inorder and post-order.

    Everything is working fine except that I am getting a random 0 in each of the outputs.

    Can anyone see any problems I'm having?

    Here's the main code...

    Code:
    /* Geoff Graham   4/23/12
       Cse 1320
       Homework 10
    */
    
    
    #include <stdio.h>
    #include <stdlib.h>
    #include "binary-lib.h"
    
    
    
    
    int main(void)
    {
        struct node *root = NULL;
        int *array_of_numbers;
        int i;
        int Max_lines = 0;
        
        
        array_of_numbers = numbers(&Max_lines);
        printf("\nunsorted:  ");
        for(i = 0; i < Max_lines; i++)
              printf(" %3d,  ", array_of_numbers[i]);
        
        array_of_numbers = sort_array(array_of_numbers, Max_lines);    
    
    
        root = add_and_balance(array_of_numbers, 0, Max_lines);
        free(array_of_numbers);
    
    
        printf("\n\npreorder:  ");
        preorder( root );
    
    
        printf("\ninorder:  ");
        inorder( root );
    
    
        printf("\npostorder:  ");
        postorder( root );
        printf("\n");
    
    
        freeMemory( root );
    getchar();    
    return 0;
    }
    Here's the header code.....

    Code:
    struct node {    int value;
        struct node *left;
        struct node *right;
    };
    
    
    void preorder(struct node* leaf);
    void inorder(struct node* leaf);
    void postorder(struct node* leaf);
    void freeMemory(struct node* leaf);
    int *numbers(int *Max_lines);
    int *sort_array(int *array_of_numbers, int Max_lines);
    struct node* add_and_balance(int *array, int first_index, int last_index);

    And here is the binary-lib.c code which has the functions. (somewhere in here is where I think the problem is. I'm thinking somewhere in my add_and_balance array)

    Code:
    #include "binary-lib.h"#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    
    int *numbers(int *Max_lines)
    {
        int *array_of_numbers, *temp;
        char buffer[50];
        FILE *fp;
        int counter;
        int n;
        n = 5;
        counter = 0;
        
        array_of_numbers = (int*)malloc(n * sizeof(int));
        
        printf("Initial array size is %d words\n", n); 
        if ( (fp = fopen("numbers.txt", "r" )) == NULL )
        {
         printf("Couldn't open file\n");
         exit(1); 
        }
        
        while( fgets(buffer, sizeof(buffer), fp))
        {
           array_of_numbers[counter] = atoi(strtok(buffer, "\n"));    
             if ( (counter+1) == n )
               {
                  n = n*2;
                  temp = (int*)realloc(array_of_numbers, n * sizeof(int));
                  if(temp != NULL)
                          array_of_numbers = temp;
                  else
                  {
                      printf("unable to reallocate\n");
                      exit(1);
                  }
                  printf("Reached limit...increasing array to %d words\n", n);
               }      
         counter++;  
        }
        fclose(fp);
        
    *Max_lines = counter; 
    return array_of_numbers;     
    }
    
    
    
    
    int *sort_array(int *array_of_numbers, int Max_lines)
    {
        int temp;
        int i;
        int swaps = 1;
          
        while(swaps)
        {
           swaps = 0;
           for(i = 0; i < Max_lines; i++)
           {
                 if( array_of_numbers[i] > array_of_numbers[i+1] )
                 {
                     temp = array_of_numbers[i];
                     array_of_numbers[i] = array_of_numbers[i+1];
                     array_of_numbers[i+1] = temp;
                     
                     swaps = 1;
                 }  
           }
        }
    return array_of_numbers;
    }
    
    
    struct node* add_and_balance(int *array, int first_index, int last_index)
    {
           int middle_index;
           struct node *new_node;
           if (first_index <= last_index)
              {
               middle_index = first_index + (last_index - first_index)/2;
               new_node = (struct node*) malloc( sizeof(struct node) );
               new_node->value = array[middle_index];
               new_node->left = add_and_balance(array, first_index, middle_index - 1);
               new_node->right = add_and_balance(array, middle_index + 1, last_index);
               return new_node;
               }
           else
           return NULL;
    }
    
    
    
    
    void preorder(struct node* leaf)
    {
        if(leaf != NULL)
        {
            printf(" %3d,  ", leaf->value);
            preorder(leaf->left);
            preorder(leaf->right);
        }
    }
    
    
    void inorder(struct node* leaf)
    {
        if(leaf != NULL)
        {
            inorder(leaf->left);
            printf("  %3d, ", leaf->value);
            inorder(leaf->right);
        }
    }
    
    
    void postorder(struct node* leaf)
    {
        if(leaf != NULL)
        {
            postorder(leaf->left);
            postorder(leaf->right);
            printf("%3d,   ", leaf->value);
        }
    }
    
    
    
    
    void freeMemory(struct node* leaf)
    {
        if(leaf != NULL)
        {
            freeMemory(leaf->left);
            freeMemory(leaf->right);
            free( leaf );
        }
    }

    Thanks for any help. I'm thinking it's either a logic problem or some silly mistake I've made. Hopefully I can finish it up tomorrow.

  2. #2
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    3,801
    O_o

    Most regulars kind of expect, or hope for the realistic among us, for newbies to give back to the community.

    Posting a problem only to go "LOLS! NVMD!" isn't the sort of behavior we like.

    And as the moderators have told you, don't start new threads just because you've discovered you have a new problem with the same source. As often as not the regulars will see your problem and will want the progression to stay in one place so that everything can be referred to within a single thread.

    Soma

    confused on binary tree.

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,337
    > for(i = 0; i < Max_lines; i++)
    > if( array_of_numbers[i] > array_of_numbers[i+1] )
    What elements of the array are you accessing when you reach the limit of the for loop?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Registered User
    Join Date
    Feb 2012
    Posts
    117
    Quote Originally Posted by phantomotap View Post
    O_o

    Most regulars kind of expect, or hope for the realistic among us, for newbies to give back to the community.

    Posting a problem only to go "LOLS! NVMD!" isn't the sort of behavior we like.

    And as the moderators have told you, don't start new threads just because you've discovered you have a new problem with the same source. As often as not the regulars will see your problem and will want the progression to stay in one place so that everything can be referred to within a single thread.

    Soma

    confused on binary tree.

    Sorry about that. I just posted what I changed in the other one. I didn't mean to offend anyone. I won't post the new thread for the same problem either.

    And as for Salem...
    I'm not sure on that.

    I did however change my code a little to make it easier on me. I changed it to two for loops instead of the while loop because I can follow that logic better.

    I changed sort to look like this to make sure it ends at the last variable and doesn't try to go on after.
    Code:
    int *sort_array(int *array_of_numbers, int Max_lines){
        int temp;
        int i, j;        
        
     for(i=0;i<Max_lines-1;i++) 
       {
          for(j = i+1; j < Max_lines; j++)                                   
          {
             if(array_of_numbers[i] > array_of_numbers[j]) 
             {
                temp = array_of_numbers[i];
                array_of_numbers[i] = array_of_numbers[j];
                array_of_numbers[j] = temp;
             }
          }
       }
    return array_of_numbers;
    }
    Also I don't really understand this part....
    but messing around with it I changed

    this..
    Code:
        root = add_and_balance(array_of_numbers, 0, Max_lines);
    to this..
    Code:
        root = add_and_balance(array_of_numbers, 0, Max_lines-1);
    Note I added a -1 to Max_lines and it works now?
    These are all of my corrections to make the program work. Not really understanding why adding the -1 makes it work. If you see why and can explain let me know. Because without the -1 it has an extra variable of 0 that it prints. So I'm guessing I'm going outside of the array when I do that, but I don't really see where.

    Again guys I apologize for my mistakes on the forums. I love this community. I've learned so much from here and try to give back when I can.

  5. #5
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,337
    Well you get a zero (actually, it's just random data) when you do this the first time you hit the end of the loop.
    array_of_numbers[i] = array_of_numbers[i+1];

    Think about it
    for ( i = 0 ; i < n ; i++ )
    accesses all the elements of an array which is n elements long.

    So if you access n+1 inside the loop, you're going to get the element which is one past the end (at some point).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ question about the Binary Tree?
    By Cliff_505 in forum C++ Programming
    Replies: 2
    Last Post: 12-15-2010, 11:48 AM
  2. Binary tree question
    By Cpro in forum C++ Programming
    Replies: 3
    Last Post: 05-03-2007, 07:08 AM
  3. question on binary tree
    By angelic79 in forum C Programming
    Replies: 1
    Last Post: 12-13-2004, 04:43 PM
  4. question about binary tree
    By wgan in forum C Programming
    Replies: 1
    Last Post: 03-11-2003, 12:54 AM
  5. Binary Tree Question
    By tar in forum C Programming
    Replies: 6
    Last Post: 09-26-2002, 01:22 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21