creating a tree and adding nodes

**cooper1200** · 06-10-2019

this is the code so far copied from the book with a couple of slight changes

Code:

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

typedef struct Bin_Node
{
    int data;
    struct Bin_Node *left; //pointer to left sub tree
    struct Bin_Node *right; //pointer to right sub tree
}Bin_Node;

typedef struct Bin_Tree
{
    struct Bin_Node *root; // same as a list haveing a pointer to head
    int node_count; // number of nodes in the tree.
}Bin_Tree;

Bin_Tree *create_tree(void);
int search_tree(const Bin_Tree *tree, int item);
int insert_node(Bin_Tree *tree, int item);

int main()
{
    
    return 0;
}

Bin_Tree *create_tree(void) //create the root node
{
    Bin_Tree *tree = malloc(sizeof(*tree));
    
    if (!tree) // test if malloc returned a null pointer
    {
        return NULL;
    }
    
    tree->root = NULL;
    tree->node_count = 0;
    return tree;
}

int search_tree(const Bin_Tree *tree, int item)
{
    const Bin_Node *node;
    
    if (!tree)
    {
        printf("no tree created\n");
        return -1;
    }
    
    node = tree->root;
    for(;;)
    { //try writing this with no else if statements in future testing
        if (!node) // tree is empty
        {
            return 0;
        }
        else if (item == node->data) //item value already exists
        {
            return 1;
        }
        else if (item > node->data)// item value is greater than the value of node
        {
            node = node->right; //go to the nodes right child
        }
        else //item value is less than the value of node
        {
            node = node->left; // go to the nodes left child
        }
    }
}

int insert_node(Bin_Tree *tree, int item)
{
    Bin_Node *node, **new_node;//changed new to new_node as new is a keyword
    
    if (!tree)
    {
        printf("no tree created\n");
        return -1;
    }
    
    new_node = &tree->root;
    node = tree->root;
    
    for (;;)
    {
        if (!node) //tree is empty
        {
            node = *new_node = malloc(sizeof(*node));
            if (node)
            {
                node->data = item; // assign the value of item to data member
                node->left = node->right = NULL;
                tree->node_count++;
                return 1;
            }
            else
            {
                return 0;
            }
        }
        else if(item == node->data)
        {
            return 2;
        }
        else if (item > node->data);
        {
            new_node = &node->right;
            node = node->right;
        }
        else
        {
            new_node = &node->left;
            node = node->left;
        }
    }
}

changes i have made is to the names of the functions as they mean more to me than bin_insert for example. lines 45 - 49 and 77 - 81 the code in the book uses

Code:

assert (tree != NULL)

i can never get the assert to work as the book is fairly old (pre c99) i assume it was something taken out

i have also shortened

Code:

if (node == null)
//to
if (!node)
//same with testing for node != null

the final change is line 90 the book says

Code:

Bin_Node *node, **new

i changed new to new_node as new is a keyword.

the book explains that it uses **new_node to point to the pointer that we followed to arrive at node

onto the issues i have with this code. can line 90 (and 94 for that matter) be written as

Code:

node = malloc(sizeof(*node));
*new_node = malloc(sizeof(*node));

if so should they be written like that

the next issue is it doesn't make use of new_node anywhere with in the block of code controlled by if (!node)

coop

**Niccolo** · 06-10-2019

So, I want to be certain you're just studying trees, right? This is an example, unbalanced tree just for study.

IMPORTANT:

THIS:

node = malloc(sizeof(*node));

*new_node = malloc(sizeof(*node));

IS NOT a replacement for this:

node = *new_node = malloc(sizeof(*node));

Notice in the original text (the second quote here), there is only one malloc, NOT TWO.

That's significant. The rest of the code is not expecting these to be out of alignment (pointing to two different, separately allocated nodes).

This would be suitable if you prefer:

Code:

 node = malloc(sizeof(*node));
*new_node = node;

You expressed concern over the fact that new_node is not used later, but in a way it is:

Code:

   
new_node = &tree->root;    
node = tree->root;

The type of new_node is a **, and it is being given the address of the root from tree.

This means that this:

Code:

    
 *new_node = malloc(sizeof(*node));

is ALSO assigning the malloc to the tree->root (via pointer to pointer).

I can't be certain, but sometimes you'll see this as a means of avoiding the double de-reference implied by tree->root. That is, to get the root pointer, the CPU must first load the tree pointer, then use it to point to the root - a two step process. It appears that new_node is being used to avoid this two step process, but I doubt it is all that helpful in the modern era.

Back in 1999, when your book was written, it would be rare to find a PC with more than 512 MBytes of RAM (half a gigabyte). Many would still have 128 Mbytes. The Pentium CPU was new, and a lot of students still ran the 486 (saving for an upgrade). Some optimizations common in C idioms are just confusing today, with little to no benefit.

If you get this working then at least you'll have a start on watching this code develop a tree.

If you have more trouble and it seems like you're wandering, there may be other sources of the algorithms in pseudo code that may be interpreted into C with slightly better study effect.

Building an unbalanced tree is conceptually rather simple. It is a modification on the act of searching the tree, which itself isn't all that complicated.

In case you're not clear as to what is coming up in this study, there are balancing algorithms added to the tree once insertion works. The two main balancing designs are called Red-Black trees and AVL trees. They're the exact same tree, but with one added piece of data in the node which help the balancing phase, where the tree is "rotated" after insertion or deletion to keep the depth even throughout the tree.

If you feed data into the tree randomly, the tree usually balances, roughly, but only when the root happens to be near the middle of the range of data. The tree naturally degrees into a simple linked list when fed data that's already sorted (and fed in that order), but balancing algorithms "flatten" that out.

**cooper1200** · 06-10-2019

your explanation helps me understand that node = *new_node = malloc..... not being the same as i thought helps explain that they are only asking for one
unfortunatly since posting this question i have read on and got entirely lost it started banging on about (traversing the tree recursivly i got that bit) then said hang on we passed a node pointer we shouldn't do that to a library so defined another function that passed in the node all ok so far..... then we went down the rabbit hole and it ended up with something to do with defining a stack and itterative traversing the tree (what ever that is).

i think i need to go and find a simple tutorial that walks through the basics in proper c99 code in a standered format with out all these "cheats" of this = that = the other

**cooper1200** · 06-10-2019

all the code i have seen online ends up printing the tree out recursively which is fine but what confuses me is they have an unordered array of numbers and add them in from the beginning of the array ie element 0 then add element 1 etc....
suppose i was begging to add nodes to my list from the array 10, 20, 15, 17, 18.... i would end up with this
creating a tree and adding nodes-begining-tree-jpg

creating a tree and adding nodes-begining-tree-jpg

question arises as i have already ascertained the node with the value of 15's right hand child is 17 where does the 18 go. if it goes to the right of 17 then how do they print out the numbers recursively in order with out sorting the list in any way

i can see a situation where you already have the nodes defined and end up needing to switch nodes around in order to insert the value in its proper place
coop

**Niccolo** · 06-10-2019

The rabbit hole. I know that one. I think this particular study did that to me, back in the 80's.

Ok, that "iterative" thing was a way to implement recursion without recursion. Not helpful, I know, but if you follow what recursion does, recognize that it is the stack that "does it" for you via function calls, so you can make your own stack and "emulate" the act of the stack without the function calls.

Some systems have very limited stacks, but that's either embedded or ancient hardware at this point.

Ok, to traverse the tree recursively takes a mind-trip. It doesn't have to be sorted, technically it already is, even that mess you have in the diagram.

Consider node with 10. It has nothing on the left, so that recursion is skipped. It thus prints itself (with only stuff on the right, it must be the least in the container).

Next, it traverses it's right. That's the node with 20, but it does have a left. Recurse into that left (and if it had a left you'd keep recursing toward the left). The left of 20 is 15, and it has no left, so it prints itself. The output is now 10, 15.

That node at 15 isn't done. It has a right, so that right is recursed. 17 has no left, but if it did we'd recurse into that (and continue as required). Since it has no left, it prints itself. The output is now 10, 15, 17.

Node at 17 has no right, it's done, we return...to 15, which is also now done. That returns to node 20.

Node 20's left is now fully processed, so it prints itself. The output is now 10, 15, 17, 20 - in order, sorted.

20 has no right, so it's done...it returns...to 10.

10 was processing it's right, but that's done...it's the root...so it's over.

Get it?

A key point to seeing why this works us to look at 20. It has a left, and everything found by traversing that left will be less than 20. However, 20 itself is on the right of 10. Everything there will be greater than 10. Put another way, there can't be a node in 20's left that is less or equal to 10 and none greater or equal to 20.

If 10 had a left, everything found there would be less than 10.

At each branch, the data is being divided by those greater or less than the leaf owning the lefts and rights. That leaf is between all in it's left and right.

**Click_here** · 06-10-2019

i can never get the assert to work

"assert" is a standard part of the C language - You will need to include <assert.h> before using it.

The idea is that you make sure that when you are writting/debugging your code that you don't do silly things, like accidently send a null pointer to a function, or enter number in a function that is larger than a limit, or return a number that is too big/small from a function... These are whoopsies like "off-by-1" errors. Sometimes when you change a bit of code in one part, it affects another part... It is a debugging tool.

Once you have finished your code and you are confident that it is working you define "NDEBUG" and the asserts don't do anything.

For more...
How to use assertions in C

Thread: creating a tree and adding nodes

Thread Tools

Search Thread

Display

creating a tree and adding nodes

Similar Threads

Adding nodes to a list

adding new nodes to linked list

Binary Search Tree does not seem to be adding nodes correctly...

Adding nodes to a linked list

Lists: adding fields (not nodes) & more

Tags for this Thread