Creating an ordered array from binary search tree

This is a discussion on Creating an ordered array from binary search tree within the C Programming forums, part of the General Programming Boards category; my node structure is Code: typedef struct node_ { void * key; void * data; struct node_ * left; struct ...

  1. #1
    Registered User
    Join Date
    Mar 2012
    Posts
    10

    Creating an ordered array from binary search tree

    my node structure is

    Code:
    typedef struct node_ {
    
        void * key;
        void * data;
        struct node_ * left;
        struct node_ * right;
    }node, *pnode;
    The aim is to create an array of generic pointers that point to the data on each node of the tree. The pointers must be in order, meaning from smallest to largest.

    My idea is to do an in-order traversal

    Code:
    void * point_data(node *cur)
    {  if (cur->left)    
    point_data(cur->left);  
    return (cur->data); 
     if (cur->right)    
    point_data(cur->right); }
    my concern with the above is that after returning (cur->data) the program won't check for the right child. If that is the case, how can i solve it?

    also, as mentioned above, i want to create an array of said pointers. How can i do that?

    my first reaction was

    Code:
    void * p[telem];    
    int i;
        
        for(i=0; i < (telem-1);i++)
        p[i] = point_data(root);
    where root is of type node *. With the above i believe i would just get all pointers pointing to the same first element. I'm at a mental block right now :S any help is greatly appreciated.

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,296
    You don't nee to return anything, instead pass the array into the function. Then either dynamically resize that array as required, or count the number of items beforehand and allocate it to the right size.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Oct 2011
    Posts
    826
    C does not have a yield operator like Python, so you cannot separate the action from the iteration. Simply put, you just need to do the array assignment in your tree iterator.

    To do that, I would supply the pointer to the dynamically allocated array of node pointers, a pointer to the size of that array (in node pointers), the number of node pointers already in the array, and the tree:
    For example,
    Code:
    int node_array_assign(node ***const arrayptr, size_t *const sizeptr, size_t *const usedptr, node *const tree)
    {
        int  error;
    
        if (tree->left) {
            error = node_array_assign(arrayptr, sizeptr, usedptr, tree->left);
            if (error)
                return error;
        }
    
        if (*usedptr >= *sizeptr) {
            const size_t  size = 16 + (*usedptr * 5) / 4;
            node **temp;
    
            temp = realloc(*arrayptr, size * sizeof (*temp));
            if (!temp)
                return ENOMEM;
    
            *arrayptr = temp;
            *sizeptr = size;
        }
    
        (*arrayptr)[(*usedptr)++] = tree;
    
        if (tree->right) {
            error = node_array_assign(arrayptr, sizeptr, usedptr, tree->right);
            if (error)
                return error;
        }
    
        return 0;
    }
    To make it a bit easier for the programmer, I'd add a wrapper, perhaps
    Code:
    size_t node_array(node ***const arrayptr, size_t *const sizeptr, node *const tree)
    {
        size_t  used;
        int     result;
    
        if (!arrayptr || !sizeptr) {
            errno = EINVAL;
            return 0;
        }
    
        if (!*sizeptr)
            *arrayptr = NULL;
    
        if (!tree) {
            errno = 0;
            return 0;
        }
    
        result = node_array_assign(arrayptr, sizeptr, &used, tree);
    
        if (result) {
            errno = result;
            return 0;
        }
    
        return used;
    }
    The allocation logic is similar to the POSIX.1-2008 getline() function: you can initialize the value pointed to by sizeptr to zero, and it will dynamically allocate a large enough buffer. Or you can provide a preallocated array, in which case it will only be reallocated if not large enough yet.

    It is, however, "three star code", which is not a compliment.. The array is specified as node ** , i.e. as a pointer to pointer (outer pointer being the array, inner pointer to the node). In order for the functions to reallocate the array when necessary, we need a pointer to the array pointer, i.e. node ***.

    Eww. It is ugly and hard to read; pretty much an indication that something is wonky with this approach.

    I'm sure I'm going to get flamed for this post and the above code, but it is undeserved, I assure you. If you want an array of pointers to a binary search tree nodes, the above is the most straightforward and simple code I can think offhand. (You can simplify it by traversing the tree twice: first to obtain the number of nodes, then allocating the array to that precise size, then to copy the pointer to each node. However, traversing any sufficiently large binary search tree will be limited by memory accesses, so that approach will be basically half as fast as this one, for large enough trees. Not a good tradeoff in my opinion.)

    However, your particular case has a feature that makes another solution much better: Your nodes are fixed-size and small, with just a key and a data pointer. So, instead of filling in an array of pointers to tree nodes, you could instead copy the node contents into the array. For example, using
    Code:
    typedef struct {
        void *key;
        void *data;
    } pair_t;
    and have the node_array() instead take a pointer to a pair_t pointer. This will only use twice the memory compared to the array of pointers to each node, but it will be independent of the tree, and you won't need to do the extra indirection; thus, it would be significantly faster for larger tree sizes.

    In this case, the functions could be for example
    Code:
    int tree_pairs_copy(pair_t **const listptr, size_t *const sizeptr, size_t *const usedptr, node *const tree);
    size_t tree_pairs(pair_t **const listptr, size_t *const sizeptr, node *const tree);
    Ah, that looks much more sane to me; this indeed is the way I'd implement this, I think.

    There are only minor differences to the node_array_assign() and node_array() functions I showed earlier, so you should be able to write them yourself.

    Any questions?

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,296
    If you first count the items in the tree and allocate the right sized array, or perhaps you have the count already - even better. Then you can just do this:
    Code:
    void tree_to_list(node *cur, void **arr)
    {
        if (cur->left)
            point_data(cur->left, arr);
    
        *arr++ = cur->data;
    
        if (cur->right)
            point_data(cur->right, arr);
    }
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Creating BInary search tree iterative
    By CSharpque in forum C++ Programming
    Replies: 4
    Last Post: 03-19-2012, 11:51 PM
  2. Creating a Binary Search Tree
    By paranoidgnu in forum C Programming
    Replies: 1
    Last Post: 07-14-2011, 11:54 AM
  3. creating a binary search tree
    By krishpatel in forum C Programming
    Replies: 6
    Last Post: 12-23-2010, 10:53 PM
  4. creating a binary search tree
    By krishpatel in forum C Programming
    Replies: 1
    Last Post: 12-23-2010, 12:18 PM
  5. ordered binary tree
    By Ami_01 in forum C Programming
    Replies: 3
    Last Post: 07-05-2005, 06:44 PM

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