bin-search-tree inorder issue

**Lawson** · 01-11-2016

I've actually created a successful Bin-search-tree in a single file.

However, I'm trying to layer my code so that one file has a node type, the second a binary tree with a node type etc.

Now, so far I've been successful in creating all other functions, other than inorder traversing.

This is the working code in my single face implementation of a bin-search-tree.

Code:

void inorder(node *temp)
{
    if (temp != NULL)
    {
        inorder(temp->left_child);
        printf("%d\t", temp->data);
        inorder(temp->right_child);
    }
}

Now, for my new modulated code I have this:

Code:

#include "bin_search_tree.h"
#include <string.h>

struct Binary_search_tree
{
    node *root;
};

b_s_tree *binary_search_tree_init(int value)
{
    b_s_tree *temp = malloc(sizeof(*temp));
    if (!temp)
    {
        fprintf(stderr, "error allocating memory for tree\n");
        exit(EXIT_FAILURE);
    }
    temp->root = node_init(value);
    
    return temp;
}


void insert(b_s_tree *tree, int key)
{
    node *new_node;
    b_s_tree *temp;
    
    if (key > get_node_key(tree->root))
    {
        if (get_node_right(tree->root) == NULL)
        {
            new_node = node_init(key);
            link_right_node(tree->root, new_node);
        }
        else
        {
            memcpy(temp, tree, sizeof(*temp));
            temp->root = get_node_right(tree->root);
            insert(temp, key);
        }
    }
    if (key < get_node_key(tree->root))
    {
        if (get_node_left(tree->root) == NULL)
        {
            new_node = node_init(key);
            link_left_node(tree->root, new_node);
        }
        else
        {
            memcpy(temp, tree, sizeof(*temp));
            temp->root = get_node_left(tree->root);
            insert(temp, key);

        }
    }
    
}


void inorder(b_s_tree *tree)
{
    b_s_tree *left;
    b_s_tree *right;
    
    memcpy(left, tree, sizeof(*left));
    memcpy(right, tree, sizeof(*right));
    
    if (tree->root != NULL)
    {
        left->root = get_node_left(left->root);
         inorder(left);
         
        printf("%d\t", get_node_key(left->root));
        printf("%d\t", get_node_key(right->root));
        
        right->root = get_node_right(right->root);
        inorder(right);
    }
}

The issue function is:

Code:

void inorder(b_s_tree *tree)
{
    b_s_tree *left;
    b_s_tree *right;
    
    memcpy(left, tree, sizeof(*left));
    memcpy(right, tree, sizeof(*right));
    
    if (tree->root != NULL)
    {
        left->root = get_node_left(left->root);
        inorder(left);
         
        printf("%d\t", get_node_key(left->root));
        printf("%d\t", get_node_key(right->root));
        
        right->root = get_node_right(right->root);
        inorder(right);
    }
}

I know it isn't pretty, but for now that's fine.. just learning.. This code gives me a Segmentation fault: 11..

I have got it to work using iteration, and if I changed b_s_tree for Node it works fine with recursion (which is what I want it to do with a b_s_tree type).

Any ideas on how to get this working?

The only solution I could do, although it feels wrong, is to pass the node from inorder() to another function that does recursion on an actually node (like the first example), that would ensure that the driver couldn't go anywhere near a 'node', but there must be an easier way.

**Nominal Animal** · 01-11-2016

Originally Posted by Lawson

Any ideas on how to get this working?

Use a helper function that does the recursion:

Code:

void inorder_recursive(node *const node)
{
    /* This is the recursive function that does the inorder traversal */
}

void inorder(b_s_tree *tree)
{
    if (tree && tree->root)
        inorder_recursive(tree->root);
}

**Lawson** · 01-11-2016

Nominal Animal, yeah that is what I was suspecting, just wanted to know if there was a better way to do it.

**Nominal Animal** · 01-11-2016

There is nothing wrong with doing it this way. In fact, it allows you to pass extra arguments to the recursive function, for example if you wanted to say control how the recursion is done. It is also common to make the recursive function only visible in the current compilation unit:

Code:

static void recurse(const node *const node, const int direction)
{
    if (direction > 0 && node->left)
        recurse(node->left, direction);
    else
    if (direction < 0 && node->right)
        recurse(node->right, direction);

    /* Do this node */

    if (direction > 0 && node->right)
        recurse(node->right, direction);
    else
    if (direction < 0 && node->left)
        recurse(node->left, direction);
}

void inorder_ascending(const b_s_tree *const tree)
{
    if (tree && tree->root)
        recurse(tree->root, +1);
}

void inorder_descending(const b_s_tree *const tree)
{
    if (tree && tree->root)
        recurse(tree->root, -1);
}

Note that the recurse() function above is not intended to be called directly by "user" code, only by the inorder_foo() functions. This way you can very easily add instrumentation -- for example, like I showed earlier, printing the entire tree in DOT format for detailed examination of the tree and the traversal process -- without having to modify any code that calls the inorder_foo() functions.

**Lawson** · 01-11-2016

Originally Posted by Nominal Animal

There is nothing wrong with doing it this way. In fact, it allows you to pass extra arguments to the recursive function, for example if you wanted to say control how the recursion is done. It is also common to make the recursive function only visible in the current compilation unit:

Code:

static void recurse(const node *const node, const int direction)
{
    if (direction > 0 && node->left)
        recurse(node->left, direction);
    else
    if (direction < 0 && node->right)
        recurse(node->right, direction);

    /* Do this node */

    if (direction > 0 && node->right)
        recurse(node->right, direction);
    else
    if (direction < 0 && node->left)
        recurse(node->left, direction);
}

void inorder_ascending(const b_s_tree *const tree)
{
    if (tree && tree->root)
        recurse(tree->root, +1);
}

void inorder_descending(const b_s_tree *const tree)
{
    if (tree && tree->root)
        recurse(tree->root, -1);
}

Note that the recurse() function above is not intended to be called directly by "user" code, only by the inorder_foo() functions. This way you can very easily add instrumentation -- for example, like I showed earlier, printing the entire tree in DOT format for detailed examination of the tree and the traversal process -- without having to modify any code that calls the inorder_foo() functions.

Yeah, that actually makes a lot of sense. Thanks for that mate!

Thread: bin-search-tree inorder issue

Thread Tools

Search Thread

Display

bin-search-tree inorder issue

Similar Threads

inorder benary search with and with ADT

recriating a bst tree from inorder

constarcting tree from its preorder,inorder..

Displaying tree thru inorder

InOrder traversal : show tree