correct tree

[Bill Cunningham]

I copied this code from a binary tree site just for C. It's somewhat
easier to understand. Somewhere strange looking too. I had to change main's
return type from void to int. The author had main's return as void.

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

struct tree_el {
int val;
struct tree_el *right, *left;
};

typedef struct tree_el node;

void insert(node ** tree, node * item)

/* Why is tree a ** ? */

{
if (!(*tree)) {

/* I am guessing that (*tree) is a dereference occuring before the if !
statement */


*tree = item;
return;
}
if (item->val < (*tree)->val)
insert(&(*tree)->left, item);

/* is insert being changed to point to a dereferenced tree here */


else if (item->val > (*tree)->val)
insert(&(*tree)->right, item);

/* Same thing again */

}

void printout(node * tree)
{
if (tree->left)
printout(tree->left);
printf("%d\n", tree->val);
if (tree->right)
printout(tree->right);
}

int main()
{
node *curr, *root;
int i;

root = NULL;

for (i = 1; i <= 10; i++) {
curr = (node *) malloc(sizeof(node));
curr->left = curr->right = NULL;
curr->val = rand();
insert(&root, curr);
}

printout(root);
}

 

[Bill Cunningham]

I copied this code from a binary tree site just for C. It's somewhat
easier to understand. Somewhere strange looking too. I had to change
main's return type from void to int. The author had main's return as void.

Ok I see no need for a typedef. It just further confuses me. I have
removed the typedef line and changed all node in the source to tree_el. The
first parameter of insert the pointer-to-pointer confuses me the most. I can
read the program and tell you what it's saying but I don't understand the
pointer manipulation. Can someone explain it simply?

Bill

 

[Donkey Hottie]

Ok I see no need for a typedef. It just further
confuses me. I have removed the typedef line and changed
all node in the source to tree_el. The first parameter of
insert the pointer-to-pointer confuses me the most. I can
read the program and tell you what it's saying but I
don't understand the pointer manipulation. Can someone
explain it simply?
Bill

It a subroutine needs to assing a value to a pointer, the argument to the
subroutine must be a pointer to that pointer.

Just like if a subroutine have to assing a value to an int, the argument has
to be a pointer to an int.

 

[Barry Schwarz]

Ok I see no need for a typedef. It just further confuses me. I have
removed the typedef line and changed all node in the source to tree_el. The
first parameter of insert the pointer-to-pointer confuses me the most. I can
read the program and tell you what it's saying but I don't understand the
pointer manipulation. Can someone explain it simply?

Your vision is not yet good enough to make decisions based on what you
see.

Put it back the way it was. There is no type called tree_el. There
is a type called struct tree_el. So your other option is to add the
missing "struct" in front of every tree_el which doesn't have one
already in front of it.

 

[Barry Schwarz]

I copied this code from a binary tree site just for C. It's somewhat
easier to understand. Somewhere strange looking too. I had to change main's
return type from void to int. The author had main's return as void.

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

struct tree_el {
int val;
struct tree_el *right, *left;
};

typedef struct tree_el node;

void insert(node ** tree, node * item)

/* Why is tree a ** ? */

tree is not a **. It is a node**. The reason is that the calling
function is passing the address of a node* to this function so that
this function may store a value at the address passed. If you look in
main, you will see the corresponding argument is &root. Every time
this function uses *tree, the expression evaluates to the contents of
root in main.

{
if (!(*tree)) {

/* I am guessing that (*tree) is a dereference occuring before the if !
statement */

The dereference occurs as part of the if statement.

You should know that an if statement determines whether the following
statement is executed based on the evaluation of some expression. In
this case, the expression is !(*tree). As noted above, the expression
*tree evaluates to the contents of root. If root is NULL (as is the
case during the first execution of this function), then the not
operator (!) will cause the expression to evaluate to 1 and the
statement following the if (in this case the block) will execute. If
root is not NULL, then the ! causes the expression to evaluate to 0
and the following statement is not executed.

*tree = item;

This assigns the current value of item to whatever object tree points
to (root during the first execution).

return;
}
if (item->val < (*tree)->val)
insert(&(*tree)->left, item);

/* is insert being changed to point to a dereferenced tree here */

insert is being called recursively. When the recursively called
function executes, the parameter tree will have a completely new
value. Given your lack of understanding of basic C statements and
expressions, I don't think you should be dealing with recursive
functions till those deficiencies are addressed.

else if (item->val > (*tree)->val)
insert(&(*tree)->right, item);

/* Same thing again */

}

void printout(node * tree)
{
if (tree->left)
printout(tree->left);
printf("%d\n", tree->val);
if (tree->right)
printout(tree->right);
}

int main()
{
node *curr, *root;
int i;

root = NULL;

for (i = 1; i <= 10; i++) {
curr = (node *) malloc(sizeof(node));

You know better than to cast the return from malloc.