compleate mess of trying to write a binary tree cobeling together bits of code

i have tried to use bits of code that probably don't work with in themselves using what i have learnt from dealing with linked lists ie a struct to hold the pointer to the root node.

Code:

---

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef struct Bin_Node
{
    int data;
    struct Bin_Node *left;
    struct Bin_Node *right;
}Bin_Node;

typedef struct Bin_Tree
{
    struct Bin_Node *root; //same as head node in a linked list
    int node_count;
}Bin_Tree;

Bin_Tree *create_tree(void);
Bin_Tree *initalize_tree(Bin_Tree *tree);
Bin_Node *create_node(void);
Bin_Node *initalize_node(Bin_Node *node, int data);
void insert_node(Bin_Tree *tree, Bin_Node *node);
void print_tree(const Bin_Tree *tree);
void destroy_tree(Bin_Tree *tree);

int main()
{
    int i, nums[] = {2, 6, 3, 9, 20, 13, 54, 10, 43};
    Bin_Tree *tree;
    Bin_Node *node;

    tree = create_tree();
    assert(tree != NULL);
    tree = initalize_tree(tree);

    for (i = 0; i < 9; i++)
    {
        node = create_node();
        assert(node != NULL);
        node = initalize_node(node, nums[i]);
        insert_node(tree, node);
        tree->node_count++;
    }
    print_tree(tree);
    destroy_tree(tree);

    return 0;
}

Bin_Tree *create_tree(void)
{
    return malloc(sizeof(Bin_Tree));
}

Bin_Tree *initalize_tree(Bin_Tree *tree)
{
    tree->node_count = 0;
    tree->root = NULL;

    return tree;
}

Bin_Node *create_node(void)
{
    return malloc(sizeof(Bin_Node));
}

Bin_Node *initalize_node(Bin_Node *node, int data)
{
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return node;
}

void insert_node(Bin_Tree *tree, Bin_Node *node)
{
    if (!tree) //parent node has no children??
    {
        tree = node;
    }
    else
    {
        if (tree->root->data < node->data) //the data of the parent we are looking at is less than the data of the node so go to its right child
        {
            insert_node(tree->root->right, node);
        }
        else
        {
            insert_node(tree->root->left, node);
        }
    }
}

void print_tree(const Bin_Tree *tree)
{
    if (!tree)
    {
        return;
    }

    if (tree->root->left) //parent node has a child to the left
    {
        print_tree(tree->root->left);
    }

    printf("node data = %d\n", tree->root->data);

    if (tree->root->right) //parent node has a child to the right
    {
        print_tree(tree->root->right);
    }
}

void destroy_tree(Bin_Tree *tree)
{
    if (!tree) //parent has children
    {
        destroy_tree(tree->root->left);
        destroy_tree(tree->root->right);
        free(tree);
    }
}

---

unsurprisingly i have a load of warnings (7) all saying incompatible pointer type which i realise Bin_Tree is a different type to Bin_Node but the root member is Bin_Node type
here is the list of warnings

Code:

---

||=== Build: Debug in binary treev2 (compiler: GNU GCC Compiler) ===|
/home/ben/Documents/coding/binary treev2/main.c||In function ‘insert_node’:|
/home/ben/Documents/coding/binary treev2/main.c|81|warning: assignment from incompatible pointer type [-Wincompatible-pointer-types]|
/home/ben/Documents/coding/binary treev2/main.c|87|warning: passing argument 1 of ‘insert_node’ from incompatible pointer type [-Wincompatible-pointer-types]|
/home/ben/Documents/coding/binary treev2/main.c|77|note: expected ‘Bin_Tree * {aka struct Bin_Tree *}’ but argument is of type ‘struct Bin_Node *’|
/home/ben/Documents/coding/binary treev2/main.c|91|warning: passing argument 1 of ‘insert_node’ from incompatible pointer type [-Wincompatible-pointer-types]|
/home/ben/Documents/coding/binary treev2/main.c|77|note: expected ‘Bin_Tree * {aka struct Bin_Tree *}’ but argument is of type ‘struct Bin_Node *’|
/home/ben/Documents/coding/binary treev2/main.c||In function ‘print_tree’:|
/home/ben/Documents/coding/binary treev2/main.c|105|warning: passing argument 1 of ‘print_tree’ from incompatible pointer type [-Wincompatible-pointer-types]|
/home/ben/Documents/coding/binary treev2/main.c|96|note: expected ‘const Bin_Tree * {aka const struct Bin_Tree *}’ but argument is of type ‘struct Bin_Node *’|
/home/ben/Documents/coding/binary treev2/main.c|112|warning: passing argument 1 of ‘print_tree’ from incompatible pointer type [-Wincompatible-pointer-types]|
/home/ben/Documents/coding/binary treev2/main.c|96|note: expected ‘const Bin_Tree * {aka const struct Bin_Tree *}’ but argument is of type ‘struct Bin_Node *’|
/home/ben/Documents/coding/binary treev2/main.c||In function ‘destroy_tree’:|
/home/ben/Documents/coding/binary treev2/main.c|120|warning: passing argument 1 of ‘destroy_tree’ from incompatible pointer type [-Wincompatible-pointer-types]|
/home/ben/Documents/coding/binary treev2/main.c|116|note: expected ‘Bin_Tree * {aka struct Bin_Tree *}’ but argument is of type ‘struct Bin_Node *’|
/home/ben/Documents/coding/binary treev2/main.c|121|warning: passing argument 1 of ‘destroy_tree’ from incompatible pointer type [-Wincompatible-pointer-types]|
/home/ben/Documents/coding/binary treev2/main.c|116|note: expected ‘Bin_Tree * {aka struct Bin_Tree *}’ but argument is of type ‘struct Bin_Node *’|
||=== Build finished: 0 error(s), 7 warning(s) (0 minute(s), 0 second(s)) ===|

---

do i assume from all these that all this stuff can't be done recursively using a struct for keeping track of the root node?

Code:

---

void insert_node(Bin_Tree *tree, Bin_Node *node)
{
    if (!tree) //parent node has no children??
    {
        tree = node;

---

tree is not a node - tree->root is though...

Code:

---

void insert_node(Bin_Tree *tree, Bin_Node *node)
{
...
    insert_node(tree->root->right, node);

---

"tree->root->right" is not a Bin_tree

Same here...

Code:

---

print_tree(tree->root->left);

...

destroy_tree(tree->root->left)

---

You can use recursion.

You may be overthinking it all.

I'll argue that it is easier in C++, but don't take that to mean it's all that much more difficult in C, nor some snark against C. I wrote in C for years before C++ existed, and I have to think a bit to re-orient my thinking a little, but it's all good.

Ok, let's start with the simplest points, and what's good about what you've posted above.

Code:

---

typedef struct Bin_Node
{
    int data;

    struct Bin_Node *left;

    struct Bin_Node *right;

}Bin_Node;
 
typedef struct Bin_Tree

{

    struct Bin_Node *root; //same as head node in a linked list
    int node_count;

}Bin_Tree;

---

This much is quite useful. The tree has a count, is initialized appropriately (you call an initializer function), and we have a workable node structure.

Now, about building the tree.

I'd suggest that for an unbalanced tree, this be changed:

Code:

---

    int i, nums[] = {2, 6, 3, 9, 20, 13, 54, 10, 43};

---

In order to visualize what happens as you debug your example, it is best not to insert a value near or at the least of the data as your first entry. It makes the entire tree hang to the right. Change this to something like:

Code:

---

    int i, nums[] = { 13, 6, 3, 9, 20, 2, 54, 10, 43};

---

I merely swapped 13 and 2. This is a better starting point. You might choose 20 instead.

Now, the heart of the problem (and where the first warning appears)

Code:

---

void insert_node(Bin_Tree *tree, Bin_Node *node)
{
    if (!tree) //parent node has no children??
    {
        tree = node;    // ***** < 1 >
    }
    else
    {
        if (tree->root->data < node->data) //the data of the parent we are looking at is less than the data of the node so go to its right child
        {
            insert_node(tree->root->right, node);
        }
        else
        {
            insert_node(tree->root->left, node);
        }
    }
}

---

Note comment < 1 >. Here the warning exists because the tree is not a node. It contains a node. tree->root would work, but that's not the real problem.

The real problem is that the recursion does NOT need to track the tree structure. It is useful to store the count, sure, but it is NOT relative to the recursion into the tree. Consider one of your diagrams (you've posted several) populated with lots of leaves. Look at a leaf at least interior to the tree (not root).

What is it? It is not a tree. It is a node.

Now look at the root. It is a node, not a tree. The tree is completely outside and auxiliary to the structure of the tree.

In fact, the entire tree is represented by the root node of the tree, NOT THE TREE structure.

That's central to the problem you're having.

The tree starts at the root, but that's just a node (Bin_Node to you). The function insert_node should be changed to:

Code:

---

void insert_node( Bin_Node **root, Bin_Node *node );

---

I'll get to why in a moment (I know, you want to know what the ** is doing and why - patience padawan).

Now, look again where you call this, but IMAGINE it thus:

Code:

---

    for (i = 0; i < 9; i++)
    {
        node = create_node();
        assert(node != NULL);
        node = initalize_node(node, nums[i]);
        insert_node(&tree->root, node);
        tree->node_count++;
    }

---

You don't need to provide the tree here.

Ok, you're thinking, WHAT ABOUT COUNT?

I know...I get that. We must wrap this into another function. "insert_node" must be made "internal", called by yet an outer function that knows the tree structure.

Now, turn your attention to insert_node and look at the first test. Would tree ever be null? Think about that. It is fashioned, it must exist already. "tree" is NOT what may be null. "tree->root" is what starts out as null. The tree itself exists, was initialized so that root is null and count is zero. This test makes no sense here as a result.

Now consider this function:

Code:

---

bool insert_tree(Bin_Tree *tree, Bin_Node *node )
{
 if( insert_node( &(tree->root), node ) )
 {
  tree->count++;
  return true;
 }

 // maybe delete node here?

 return false;
}

---

Note how the root is passed. This is the ADDRESS of the root, a member of tree. It is a pointer, so the address of a pointer is a pointer to a pointer, or Bin_Node **.

I'm not trying to tell you how to fix your code, but I am trying to suggest a change of direction. What happens if the insertion failed? You know you can't enter duplicates, for example. This, at least, considers insertion failure. It also assumes insert_node, an "interior" function, returns a bool to indicate success. By "interior" I mean not the function application code calls to insert a node.

What's more important, however, is that it provides THE ADDRESS of the root in the tree structure, and that's something that applies equally to recursive calls into the tree structure when leaves are not trees, but nodes.

So, insert changes.

Code:

---


bool insert_node(Bin_Node **root, Bin_Node *node)
{
    if (! (*root)) //parent node has no children??
    {
        *root = node;
        return true;
    }
    else
    {
        if ( (*root)->data < node->data) //the data of the parent we are looking at is less than the data of the node so go to its right child
        {
            insert_node( &((*root)->right), node);
            return true;
        }
        //else - oops, what if equals - THE TREE STRUCTURE WOULD BE DESTROYED
        else if ( (*root)->data != node->data )
        {
            insert_node( &((*root)->left), node);
            return true;
        }

        return false; // that node already existed
    }
}

---

Here the root is passed as the address of the pointer (the type is pointer to a pointer, or Bin_Node **). To use it, it must be "double de-referenced". The advantage here is that this enables the assignment to root's CONTENT to change the value IN THE CALLING CODE's notion of the root (be it root of the tree or leaf along the way).

Where I write (*root), this is one level of de-reference. What was passed is the address of the pointer, this gets the pointer that ** points to - the Bin_Node * you know and love.

Where I don't bother with parenthesis around root, it is merely because I have no reason to think there's an ambiguity, but for something like (*root)->right, I want to be sure both a reader and the compiler know I need first to get the pointer that the ** is pointing to (I know, dizzying), THEN I can use that pointer (a Bin_Node *) to de-reference into the struct using ->.

Another point made here is that there must be a plan when a duplicate is inserted. Duplicates are not allowed in a tree, it destroys the structure (the rules no longer apply). If the data is not <, it might not also be >, it could be "==". If it is equal, you must return a false (indicating insertion was refused).

In the exterior function I comment where you MIGHT decided to delete the new node so there's no memory leak, but I'll leave that interface detail to you. If not here, it would HAVE to be dealt with when called (a bit ugly). At least a false is returned to indicate refusal to accept the insertion.

In theory when a node is handed to tree_insert, that function "agrees" to take possession of the new node. If it is to be refused, that means deleting the node (at least that's how I see it).

I have not tested the code.

I have no idea if this actually works to solve your problems.

I'm merely trying to provide that "over the hump" illustration I think you need to get past the writers block you think you have.

I don't think "Bin_Node **" is required for searches, just insertions and possibly deletions. Deletion may need an "outer" function and an "interior" function along similar lines.

In my theory (suggested change), the interior function can recurse, but the outer function can't, it just sets things up for recursion and deals with the result of that operation, whatever it is (like decrementing count if deletion succeeds).

didn't think of that one.... i came up with changing the functions to take Bin_Node and passing tree-> root instead of tree

Code:

---

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef struct Bin_Node
{
    int data;
    struct Bin_Node *left;
    struct Bin_Node *right;
}Bin_Node;

typedef struct Bin_Tree
{
    struct Bin_Node *root; //same as head node in a linked list
    int node_count;
}Bin_Tree;

Bin_Tree *create_tree(void);
Bin_Tree *initalize_tree(Bin_Tree *tree);
Bin_Node *create_node(void);
Bin_Node *initalize_node(Bin_Node *node, int data);
void insert_node(Bin_Node **tree, Bin_Node *node);
void print_tree(const Bin_Node *tree);
void destroy_tree(Bin_Node *tree);

int main()
{
    int i, nums[] = {2, 6, 3, 9, 20, 13, 54, 10, 43};
    Bin_Tree *tree;
    Bin_Node *node;

    tree = create_tree();
    assert(tree != NULL);
    tree = initalize_tree(tree);

    for (i = 0; i < 9; i++)
    {
        node = create_node();
        assert(node != NULL);
        node = initalize_node(node, nums[i]);
        insert_node(&tree->root, node);
        tree->node_count++;
    }
    print_tree(tree->root);
    destroy_tree(tree->root);

    return 0;
}

Bin_Tree *create_tree(void)
{
    return malloc(sizeof(Bin_Tree));
}

Bin_Tree *initalize_tree(Bin_Tree *tree)
{
    tree->node_count = 0;
    tree->root = NULL;

    return tree;
}

Bin_Node *create_node(void)
{
    return malloc(sizeof(Bin_Node));
}

Bin_Node *initalize_node(Bin_Node *node, int data)
{
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return node;
}

void insert_node(Bin_Node **tree, Bin_Node *node)
{
    if (!*tree) //parent node has no children??
    {
        *tree = node;
        printf("node inserted\n");
    }
    else
    {
        if ((*tree)->data < node->data) //the data of the parent we are looking at is less than the data of the node so go to its right child
        {
            insert_node(&(*tree)->right, node);
        }
        else
        {
            insert_node(&(*tree)->left, node);
        }
    }
}

void print_tree(const Bin_Node *tree)
{
    if (!tree)
    {
        return;
    }

    if (tree->left) //parent node has a child to the left
    {
        print_tree(tree->left);
    }

    printf("node data = %d\n", tree->data);

    if (tree->right) //parent node has a child to the right
    {
        print_tree(tree->right);
    }
}

void destroy_tree(Bin_Node *tree)
{
    if (tree) //parent has children
    {
        destroy_tree(tree->left);
        destroy_tree(tree->right);
        free(tree);
        printf("node deleated\n");
    }
}

---

this now works with the expected results however it raises a couple of questions
i have been told never write &*x as the two operands cancel each other out however i "have" to do that in the insert function if one argues that the & only cancels one * out then why cant i write *tree instead as an argument.

2nd question is in the tutorial i found in here line 119 should be if (!tree) but that didn't work is my delete function correct.
coop

Quote:

---

Originally Posted by cooper1200

i have been told never write &*x as the two operands cancel each other out however i "have" to do that in the insert function if one argues that the & only cancels one * out then why cant i write *tree instead as an argument.

---

&*x and &(*x)->y are two very different expressions.

Yish! I was editing my post while you two responded....so check the updates (more thoughts and a few corrections - typos and "another thing" addendums.

laserlight is, of course, correct to point out that while you post &*x, that isn't anywhere near the same thing as &(*x)->right, and maybe I should have said &((*x)->right) to keep it extremely clear. We want the address of the right node's pointer.

Wait.

What?

THAT WORKED? I wasn't even finished editing the d*mn post and you USED IT already?!

Well......that's good, actually.

You asked if your delete function is correct.

Actually, that was one of those "and another thing" I added while you were already using the (not quite complete) post....so, no....it probably needs work along the same lines as I suggested for insert_node.

But hold on! You missed something.

A point I rephrased about "interior" vs "outer" functions.

In the version you have now posted, there's no management of "count" in tree.

Look at my suggestion for "insert_tree", and suggestion that "insert_node" should not be for the user.

I also admit I'm being a bit sneaky. I'm making you think like a C++ programmer writing in C. "interior" is code for "private", and "outer" is code for "public", forming an "interface" for user code, treating the Bin_Tree structure like a C++ class, without the class.

thats the trouble with forums one can respond while someone else is typing something. I hadn't actually seen your post when i posted the second version that's why something's aren't implemented i shall do that tomorrow as its bed time for me as its 1.30.

I made a serious error in my "suggested" example. I did qualify by saying I hadn't compiled or tested it, but while I was adding coolant to my car I realized what I did.

This is incorrect:

Code:

---

bool insert_node(Bin_Node **root, Bin_Node *node)
{
    if (! (*root)) //parent node has no children??
    {
        *root = node;
        return true;
    }
    else
    {
        if ( (*root)->data < node->data) //the data of the parent we are looking at is less than the data of the node so go to its right child
        {
            insert_node( &((*root)->right), node);
            return true;
        }
        //else - oops, what if equals - THE TREE STRUCTURE WOULD BE DESTROYED
        else if ( (*root)->data != node->data )
        {
            insert_node( &((*root)->left), node);
            return true;
        }
 
        return false; // that node already existed
    }
}

---

It should (probably) be:

Code:

---

bool insert_node(Bin_Node **root, Bin_Node *node)
{
    if (! (*root)) //parent node has no children??
    {
        *root = node;
        return true;
    }
    else
    {
        if ( (*root)->data < node->data) //the data of the parent we are looking at is less than the data of the node so go to its right child
        {

            return insert_node( &((*root)->right), node);

        }
        //else - oops, what if equals - THE TREE STRUCTURE WOULD BE DESTROYED

        else if ( (*root)->data != node->data )

        {

            return insert_node( &((*root)->left), node);

        }
 

        return false; // that node already existed

    }

}

---

The left and right recursions should return the return from the recursion, not true (in a second line).

ok i have changed the code trying to incorporate some of the suggestions ie keeping the knowledge of nodes away from main and the knowledge of the tree away from the functions that insert print and delete.

Code:

---

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef struct Bin_Node
{
    int data;
    struct Bin_Node *left;
    struct Bin_Node *right;
}Bin_Node;

typedef struct Bin_Tree
{
    struct Bin_Node *root; //same as head node in a linked list
    int node_count;
}Bin_Tree;

Bin_Tree *create_tree(void);
Bin_Tree *initalize_tree(Bin_Tree *tree);
Bin_Node *create_node(void);
Bin_Node *initalize_node(Bin_Node *node, int data);
bool insert_node(Bin_Node **root, Bin_Node *node);
void print_tree(const Bin_Node *root);
void destroy_tree(Bin_Node *root);
void insert(Bin_Tree *tree);
void print(const Bin_Tree *tree);
void destroy(Bin_Tree *tree);

int main()
{
    Bin_Tree *tree;

    tree = create_tree();
    assert(tree != NULL);
    tree = initalize_tree(tree);
    insert(tree);
    print(tree);
    destroy(tree);

    return 0;
}

Bin_Tree *create_tree(void)
{
    return malloc(sizeof(Bin_Tree));
}

Bin_Tree *initalize_tree(Bin_Tree *tree)
{
    tree->node_count = 0;
    tree->root = NULL;

    return tree;
}

Bin_Node *create_node(void)
{
    return malloc(sizeof(Bin_Node));
}

Bin_Node *initalize_node(Bin_Node *node, int data)
{
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return node;
}

bool insert_node(Bin_Node **root, Bin_Node *node)
{
    if (!*root) //parent node has no children??
    {
        *root = node;
        return true;
    }
    else
    {
        if ((*root)->data < node->data) //the data of the parent we are looking at is less than the data of the node so go to its right child
        {
            return insert_node(&(*root)->right, node);
        }
        else if ((*root)->data != node->data)
        {
            return insert_node(&(*root)->left, node);
        }
    }
    return false; // the node already existed
}

void print_tree(const Bin_Node *root)
{
    if (!root)
    {
        return;
    }

    if (root->left) //parent node has a child to the left
    {
        print_tree(root->left);
        printf("searching left child of %d\n", root->data);
    }

    printf("node data = %d\n", root->data);

    if (root->right) //parent node has a child to the right
    {
        print_tree(root->right);
        printf("searching right child of %d\n", root->data);
    }
}

void destroy_tree(Bin_Node *root)
{
    if (root) //parent has children
    {
        destroy_tree(root->left);
        destroy_tree(root->right);
        free(root);
        printf("node deleated\n");
    }
}

void insert(Bin_Tree *tree)
{
    int i, nums[] = {20, 6, 3, 9, 2, 13, 54, 10, 43};
    Bin_Node *root = tree->root, *node;

    for (i = 0; i < 9; i++)
    {
        node = create_node();
        assert(node != NULL);
        node = initalize_node(node, nums[i]);
        if (!insert_node(&root, node)) //node already exists
        {
            free(node);
            fprintf(stderr, "value already existed\n");
        }
        else
        {
            printf("node inserted\n");
            tree->node_count++;
        }
    }
}

void print(const Bin_Tree *tree)
{
    Bin_Node *root = tree->root;

    printf("printing tree\n");
    print_tree(root);
}

void destroy(Bin_Tree *tree)
{
    Bin_Node *root = tree->root;

    destroy_tree(root);
}

---

stepping through the function insert node it seems to be putting the node in the right place. ie it puts three to the left of 20 etc however when i try to print the list its lost all knowlage of the path it just thinks the first node is null so doesn't print anything

im sure i have probably screwed up the pointers somewhere yet again but have no idea which function or where.
coop

changing insert_node by adding 3 printf's

Code:

---

bool insert_node(Bin_Node **root, Bin_Node *node)
{
    if (!*root) //parent node has no children??
    {
        printf("at end of line so add node %d\n", node->data);
        *root = node;
        return true;
    }
    else
    {
        if ((*root)->data < node->data) //the data of the parent we are looking at is less than the data of the node so go to its right child
        {
            printf("root data is %d < node data %d so go right\n", (*root)->data, node->data);
            return insert_node(&(*root)->right, node);
        }
        else if ((*root)->data != node->data)
        {
            printf("root data is %d > node data %d so go left\n", (*root)->data, node->data);
            return insert_node(&(*root)->left, node);
        }
    }
    return false; // the node already existed
}

---

i get the following output

Code:

---

at end of line so add node 20
node inserted
root data is 20 > node data 6 so go left
at end of line so add node 6
node inserted
root data is 20 > node data 3 so go left
root data is 6 > node data 3 so go left
at end of line so add node 3
node inserted
root data is 20 > node data 9 so go left
root data is 6 < node data 9 so go right
at end of line so add node 9
node inserted
root data is 20 > node data 2 so go left
root data is 6 > node data 2 so go left
root data is 3 > node data 2 so go left
at end of line so add node 2
node inserted
root data is 20 > node data 13 so go left
root data is 6 < node data 13 so go right
root data is 9 < node data 13 so go right
at end of line so add node 13
node inserted
root data is 20 < node data 54 so go right
at end of line so add node 54
node inserted
root data is 20 > node data 10 so go left
root data is 6 < node data 10 so go right
root data is 9 < node data 10 so go right
root data is 13 > node data 10 so go left
at end of line so add node 10
node inserted
root data is 20 < node data 43 so go right
root data is 54 > node data 43 so go left
at end of line so add node 43
node inserted

---

so clearly the insert node function is working.

You're a lot closer than you think.

You still missed one of the points I made earlier, even though you started it - almost finished it.

The basic problem is that nothing has ever put the first node into the Bin_Tree structure. The tree formed. The Bin_Tree didn't know about it.

The issue is in insert( Bin_Tree *tree).

When a node is created and the Bin_Tree->root is null, that new node (when insert_succeeds) must be set into the tree, but only on that first node.

There could be several ways to deal with this. You could check tree->root for null when the new node is inserted (insert_node returns true), where you now increment the node_count. That is the moment Bin_Tree is being managed. Only the first node is the root of the tree in that moment. If Bin_Tree has a root, it should not be overwritten.

You COULD make the Bin_Node *root at the top of the insert function a Bin_Node **root (taking the &(tree->root)). This works because the parameter (root) passed to insert_node will always remain the root of the tree, if that is a ** instead of a *, it is tied to the Bin_Tree::root member correctly (it only changes the tree's root when the first node is added).

Now, here's where there is one misinterpretation when I said insert_tree should be considered. You have an insert function which takes the tree, but that is still "application/user" level code. It isn't a good user interface FOR application/user code. In other words, if you used your tree in an application elsewhere, the only thing you can do from all other application code is either insert all these nodes from nums, or you must call insert_node (and therefore every call in application code must test, and free, and increment the node_count).

That's too much to demand of the "user" code.

You still need to consider an "insert_tree" function. What you have in insert(Bin_Tree *) where you insert the node, free it if it failed, increment node_count when it succeeds...THAT belongs in insert_tree.

Insert_tree takes a Bin_Tree *.

It is just that you combined the notions. This insert is still just a relocation of the insertion you once performed in main.

You want application code that uses your tree to simply call one function and know it has been handled. You don't want every usage to be required to remember to increment the node_count, free a refused node, etc.

If you REALLY wanted application code to be free of micromanagement, you might have insert_tree take THE INTEGER DATA, so application code doesn't even have to create the new node for insertion.

For example:

Quote:

---

for( int i = 0; i < 9; i++)
{
insert_tree( tree, i ); // ignoring that it should return a bool, true if ok.
}

---

Now, insert_tree takes that integer, fashions a node, inserts it into the tree, handles refusal (frees a refused node, returns false), manages the node_count AND ensures that Bin_Tree knows the root of the tree when required.

To put this another way, the very reason you thought something was wrong with the tree is because the function which manages the tree had not been created. So, the matter wasn't considered, the step skipped - the Bin_Tree remained unaware that a tree was formed.

By creating insert_tree, not only are you then managing that detail, you've create a place to do so much more.

I find when designing things like this I ask myself "how do I want to write the use of this thing".

I really wouldn't want to have to write:

Quote:

---

node = create_node();
assert(node != NULL);
node = initalize_node(node, nums[i]);
if (!insert_node(&root, node)) //node already exists
{
free(node);
fprintf(stderr, "value already existed\n");
}
else
{
printf("node inserted\n");
tree->node_count++;
}

---

Every time I added an integer to the tree.

I really would want to just tell the tree to take a new integer. I don't even want to know nodes are involved. Hence, insert_tree( tree, 5 );

Oh, and your tree printed in order when I told the tree where the root node was located.

if someone gave you a libary to use for creating a tree. obviously it would be down to you to declare an instance of that tree and call the initial function (in this case create tree) question is would you expect the returned pointer to the tree you declared to have a node in it already or would you be happy to then supply the first node through insert.
the difference is do i ask for the initial value of the data for the very first node when creating the tree or after.

well here it is

Code:

---

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef struct Bin_Node
{
    int data;
    struct Bin_Node *left;
    struct Bin_Node *right;
}Bin_Node;

typedef struct Bin_Tree
{
    struct Bin_Node *root; //same as head node in a linked list
    int node_count;
}Bin_Tree;

Bin_Tree *create_tree(void);
Bin_Tree *initalize_tree(Bin_Tree *tree);
Bin_Node *create_node(void);
Bin_Node *initalize_node(Bin_Node *node, int data);
bool insert_node(Bin_Node **root, Bin_Node *node);
void print_tree(const Bin_Node *root);
void destroy_tree(Bin_Node *root);
void insert(Bin_Tree *tree, int node_data);
void print(const Bin_Tree *tree);
void destroy(Bin_Tree *tree);

int main()
{
    int i, nums[] = {20, 6, 3, 9, 2, 3, 13, 54, 10, 43};
    Bin_Tree *tree;

    tree = create_tree();
    for (i = 0; i < 10; i++)
    {
        insert(tree, nums[i]);
    }
    print(tree);
    destroy(tree);

    return 0;
}

Bin_Tree *create_tree(void)
{
    Bin_Tree *tmp_tree = malloc(sizeof(Bin_Tree));

    assert(tmp_tree != NULL);
    tmp_tree = initalize_tree(tmp_tree);
    return tmp_tree;
}

Bin_Tree *initalize_tree(Bin_Tree *tree)
{
    tree->node_count = 0;
    tree->root = NULL;

    return tree;
}

Bin_Node *create_node(void)
{
    return malloc(sizeof(Bin_Node));
}

Bin_Node *initalize_node(Bin_Node *node, int data)
{
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return node;
}

bool insert_node(Bin_Node **root, Bin_Node *node)
{
    if (!*root) //parent node has no children??
    {
        *root = node;
        return true;
    }
    else
    {
        if ((*root)->data < node->data) //the data of the parent we are looking at is less than the data of the node so go to its right child
        {
            return insert_node(&(*root)->right, node);
        }
        else if ((*root)->data != node->data)
        {
            return insert_node(&(*root)->left, node);
        }
    }
    return false; // the node already existed
}

void print_tree(const Bin_Node *root)
{
    if (!root)
    {
        return;
    }

    if (root->left) //parent node has a child to the left
    {
        print_tree(root->left);
        printf("searching left child of %d\n", root->data);
    }

    printf("node data = %d\n", root->data);

    if (root->right) //parent node has a child to the right
    {
        print_tree(root->right);
        printf("searching right child of %d\n", root->data);
    }
}

void destroy_tree(Bin_Node *root)
{
    if (root) //parent has children
    {
        destroy_tree(root->left);
        destroy_tree(root->right);
        free(root);
        printf("node deleated\n");
    }
}

void insert(Bin_Tree *tree, int node_data)
{
    Bin_Node *root = tree->root, *node;

    node = create_node();
    assert(node != NULL);
    node = initalize_node(node, node_data);


    if (!insert_node(&root, node)) //node already exists
    {
        free(node);
        fprintf(stderr, "value already exists\n");
    }
    else
    {
        if (!tree->root)
        {
            tree->root = node;
        }
        tree->node_count++;
    }

}

void print(const Bin_Tree *tree)
{
    Bin_Node *root = tree->root;

    print_tree(root);
    printf("\nthere are %d nodes in the tree\n", tree->node_count);
}

void destroy(Bin_Tree *tree)
{
    Bin_Node *root = tree->root;

    destroy_tree(root);
}

---

an interesting amusement when playing with the order of the array i found if i swapped the position of 10 and 20 i get eight lots of searching...... in pairs of 2 where as if i leave them as they are i still get 8 lots of searching..... but 5 only one per go and one group of three. yet having 20 as the root node makes more sense as there are 4 numbers less than 20 and 4 numbers more than 20.
coop

Congrats, the tree is working.

Quote:

---

Originally Posted by cooper1200

if someone gave you a libary to use for creating a tree. obviously it would be down to you to declare an instance of that tree and call the initial function (in this case create tree) question is would you expect the returned pointer to the tree you declared to have a node in it already or would you be happy to then supply the first node through insert.
the difference is do i ask for the initial value of the data for the very first node when creating the tree or after.

---

That question was settled long ago. The tree would begin as empty. From the usage viewpoint there should be no special initial node. In all extant examples (here I'm describing those from various libraries), the tree beings empty and creation of the tree is separate from the creation of it's content. An empty tree is actually an important asset. Where it is to gather data from a process, an empty tree indicates the process returned nothing. A tree that requires an initial entry would not exist if the process produced no output for the tree to store, which is a different test than the test for an empty tree that exists.

As to creation of the tree, the usual approach is a kind of factory design pattern where a function creates the new empty tree in one step; a function that allocates the structure, initializes it (count set to zero, root set to null) and returns the newly created tree.

Yet that leads to the next obvious inquiry - where to go from here? As a study of the binary tree, you've completed that and it works. What happens next depends on the nature of your own study. If this were a class I'd dare say this is a grade A result, but there is more to the subject. Typically that can wait for another time for advancement, and many may never go further than this because 90% of what is to be gained from the study is already done. As CS knowledge goes, this is the entirety of the basics on the binary tree.

The next topics on this subject, the kind of thing that would turn this into a library quality result, would be a comparison function for a generic tree. The tree could then accept any type of data, much like qsort can take any type of data when given a pointer to a comparison function.

Balancing the tree so it can accept thousands or millions of elements is another level. Red-Black or AVL are typical, but there are others (some are partially balanced to good result).

Custom allocation of the nodes is possible, too, so the tree isn't calling malloc at every node (which becomes entwined with the notion of storing any type of data). Here the subject involves possibly allocating space for nodes in a block from a custom heap manager, for fast node creation, and then possibly unifying the data in that node block so there's not two allocations for every node (that doesn't yet apply here because data is integrated into the node, where in a generic tree it would be of unknown size - or one might say any given size and content).

Back in the day (I catch myself posting like an old man talking about the past on the front porch) I lost maybe two or three months on studies like this. I revisited some of them, trees included (qsort/introsort too), and lost another month or so. I say lost only because I did little else aside from eating, laundry and hygiene, but I did emerge with an improved library and lots of awareness.

Congrats! I know you worked at this from a number of angles. It is always hard fought to get this kind of thing done and working. Sometimes the "stick-to-it-ivness" is the most telling attribute of an engineer or student. Looking over a number of threads where you developed this in public view, you certainly stuck to it no matter what. Powerful stuff, that.

awww thanks i think the next stage for me is going to be avl as i can see that while there are only a trivial amount of data ith modern cpu's etc height of the tree and balance doesn't really matter but i can clearly see that if i had 1,000,000 integers of all different values height would be