Thread: 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.

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.

Originally Posted by phantomotap

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.