Thread: confused on binary tree.

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

    confused on binary tree.

    My professor gave us an assignment to make a binary tree. We're given a file which we store in an array and then sort the numbers in the array least to greatest.
    I have done all of that so far...

    This requirement is confusing me however.

    "After storing the integers, sort them. Then construct the binary tree using the following algorithm:

    function balance(array, first_index, last_index):
    if first_index <= last_index
    {
    middle_index = first_index + (last_index - first_index)/2
    create node_pointer
    store value at middle_index in node
    left_child_of_node = balance(array, first_index, middle_index - 1)
    right_child_of_node = balance(array, middle_index + 1, last_index)
    return node_pointer
    }

    else
    return NULL"

    This function is adding the nodes to the binary tree and also balancing it at the same time if I'm not mistaken?

    This is my implementation of the code but it is not working so far.

    Code:
    struct node* balance(int *array, int first_index, int last_index)
    {
           int middle_index;
           if (first_index <= last_index)
              {
               middle_index = first_index + (last_index - first_index)/2;
               struct node* temp;
               temp = (node*) malloc( sizeof(struct node) );  
               temp->value = middle_index;
               temp->left = balance(array, first_index, middle_index - 1);
               temp->right = balance(array, middle_index + 1, last_index);
               return temp;
               }
           else
           return NULL;
    }

    here is all of my code so far (split into 2 c files and a header because of requirements).

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include "bin-library.h"
    
    
    
    
    int main(void)
    {
        struct node *root = NULL;
        int *array_of_numbers;
        int Max_lines = 0;
        int i;
        
        array_of_numbers = numbers(&Max_lines);
        array_of_numbers = sort_array(array_of_numbers, Max_lines); 
     root = balance(array_of_numbers, array_of_numbers[0], array_of_numbers[Max_lines]);
    getchar();
    return 0;
    }
    next file is this...(skipping over the sorting and such)

    Code:
    #include "bin-library.h"
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    struct node* balance(int *array, int first_index, int last_index)
    {
           int middle_index;
           if (first_index <= last_index)
              {
               middle_index = first_index + (last_index - first_index)/2;
               struct node* temp;
               temp = (node*) malloc( sizeof(struct node) );  
               temp->value = middle_index;
               temp->left = balance(array, first_index, middle_index - 1);
               temp->right = balance(array, middle_index + 1, last_index);
               return temp;
               }
           else
           return NULL;
    }
    And then the header simply has the function declartions and the structure of ...

    Code:
    struct node {
        int value;
        struct node *left;
        struct node *right;
    };

    I'm not sure what I'm confused on exactly. Am I right on what I think his algorithm is? If so what am I doing wrong? If I'm not right on that, can someone explain to me where I'm not understanding it?

    Thanks in advance

  2. #2
    Registered User
    Join Date
    Feb 2012
    Posts
    117
    Edit
    You know what...I think I put in the actual numbers in the array for the function he had. I think he wanted to spot where of the first and last variable. I.E. (0 and Max_lines). Gonna see if that works and go from there. Any other help would be nice if anything is obvious that I'm overlooking

    Edit again..
    nope didn't work how I expected..

  3. #3
    Registered User
    Join Date
    Feb 2012
    Posts
    117
    I fixed it. Useless post Haha

  4. #4
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by mgracecar View Post
    I fixed it. Useless post Haha
    I won't remain useless if you post your fix too.
    Someone having the a similar problem will no doubt find it useful.

  5. #5
    Registered User
    Join Date
    Feb 2012
    Posts
    117
    Sorry about that. Someone else got onto me as well for making 2 different posts.

    Anyways for this one...

    I was right about the add_and_balance function

    I changed it to this..

    Code:
        root = add_and_balance(array_of_numbers, 0, Max_lines);
    where it's the position in the array, rather than the number in that position.


    Then the function itself looks like this

    Code:
    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;
    }
    Where The middle_index is what I'm using for that node value.
    I'm having one issue of too many numbers being printed, but that's on another topic that I made and I don't want to keep both of these going. I apologize to the community for making both of these as well as not posting what I did to fix it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 02-28-2010, 10:35 PM
  2. Really confused about AVL Tree
    By madmax2006 in forum C Programming
    Replies: 2
    Last Post: 02-27-2010, 03:49 PM
  3. Replies: 2
    Last Post: 08-01-2007, 01:08 PM
  4. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  5. display tree data in binary tree format
    By xddxogm3 in forum C++ Programming
    Replies: 4
    Last Post: 12-11-2003, 12:47 AM