simplebinary tree

[sophia.agnes]

Hi all,

this is a simple binary tree program done by me for learning node
deletions in a binary tree, how good is the deletion method ???? can
anyone suggest corrections/improvements ????

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

typedef struct node
{
struct node *left;
struct node *right;
int val;
}sn;

void insert(sn **,int);
void inorder(sn*);
void search(sn**,int,sn**,sn**,int*);
void delete(sn**,int);

sn* allocate(int);

int main(void)
{
sn *bt;
int req,i=1,num,dv;
bt = NULL;

printf("\n Enter the no: of nodes to be inserted:: ");
scanf("%d",&req);
assert(req > 0);

while(i++ <= req)
{
printf("Enter the value of the node you want to insert:: ");
scanf("%d",&num);
insert(&bt,num);
}

printf("Enter the value of the node you want to delete:: ");
scanf("%d",&dv);
assert(dv > 0);

assert(bt != NULL);
delete(&bt,dv);

if(bt == NULL)
{puts("Tree empty");exit(0);}

puts(".............................");
printf("IN ORDER TRAVERSAL\n");
puts(".............................\n");
inorder(bt);

puts("");
return(EXIT_SUCCESS);
}

void insert(sn** sr,int num)
{
if(*sr == NULL)
{
*sr = allocate(num);

}
else
{
if( num < (*sr) -> val )
insert( &((*sr)->left),num);
else
insert( &((*sr)->right),num);
}
}


sn* allocate(int n)
{
sn* node;

node = malloc(sizeof(sn));
assert(node != NULL);
node -> left = NULL;
node -> right = NULL;
node -> val = n;

return node;
}

void inorder(sn *root)
{
if(root != NULL)
{
inorder(root -> left);
printf("%d\t",root ->val);
inorder(root -> right);
}
}

void delete(sn **root, int num)
{
int found;
sn *parent,*x,*xsucc;
sn *temp,*temp1;


if( (*root)->val == num && (*root)->left == NULL && (*root)-> right
== NULL)
{
*root = NULL;
return;
}

parent = x = NULL;
search(root,num,&parent,&x,&found);

if(found == 0)
{
puts("Data to be deleted not found");
return;
}

/*if the node to be deleted has no child.*/

if(x ->left == NULL && x -> right == NULL)
{

if(parent -> left == x)
parent -> left = NULL;
else
parent -> right = NULL;

free(x);
return;
}
/*if the node to be deleted has only right child*/
if(x->left == NULL && x-> right != NULL)
{
if(parent == NULL)
{
*root = x -> right;
return;
}
if(parent -> left == x)
parent -> left = x -> right;
else
parent -> right = x -> right;
free(x);
return;
}


/*if the node to be deleted has only left child*/
if(x->left != NULL && x-> right == NULL)
{
if(parent == NULL)
{
*root = x -> left;
return;
}
if(parent -> left == x)
parent -> left = x -> left;
else
parent -> right = x -> left;
free(x);
return;
}
/*if the node to be deleted have both child*/

if(x->left != NULL && x-> right != NULL)
{
if(parent == NULL)
{
temp1 = temp = (*root)-> left;

while(temp ->right != NULL)
temp = temp -> right;

temp->right = (*root)-> right;
*root = temp1;
return;
}

temp1 = temp = x -> left;
while(temp ->right != NULL)
temp = temp -> right;
temp->right = x -> right;

if(parent -> left == x)
parent-> left = temp1;
else
parent-> right = temp1;

x->left = x-> right = NULL;
free(x);
}
}

void search(sn** root,int num,sn** par, sn** x,int *found)
{
sn *q;

q = *root;
*par = NULL;
*found = 0;

while(q != NULL)
{
if(q -> val == num)
{
*x = q;
*found = 1;
return;
}
*par = q;

if(q -> val < num )
q = q -> right;
else
q= q -> left;
}
}

 

[CBFalconer]

this is a simple binary tree program done by me for learning node
deletions in a binary tree, how good is the deletion method ????
can anyone suggest corrections/improvements ????

These things are highly data and algorithm sensitive. For example,
you really want to keep such trees from degenerating into lists.
This involves various means of maintaining reasonable balance. So
the first thing to do is to settle this matter, and describe it in
words (including deciding to ignore the problem).

You have done a fairly good job of indenting etc, but far from
perfect. I recommend the use of 'indent' program, available (from
gnu) for everywhere. If I have time I will later apply it and
follow with some editing to illustrate some of my meanings.

 

[Richard Heathfield]

(e-mail address removed) said:

Hi all,

this is a simple binary tree program done by me for learning node
deletions in a binary tree, how good is the deletion method ???? can
anyone suggest corrections/improvements ????

Okay, let's take a look.

My first step was to compile the code, using my usual insane collection of
flags. I was pleasantly surprised - only one diagnostic message, which
was:

foo.c:98: warning: unused variable `xsucc'

Hardly a big deal, that one, is it? So let's take a less close look.

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

So far so good, although the leading spaces are unnecessary, and a space
between include and < would make the code a little more readable, but
these are minor issues of style. (On some ancient compilers, the # had to
be in the first column, but I doubt very much whether you'll ever come
across such a compiler, and even if you do, the fix is obvious.)

typedef struct node
{
struct node *left;
struct node *right;
int val;
}sn;

This is fine, although I'd suggest two changes:

1) separate the typedef from the struct definition - but this, again, is a
minor matter of style, so don't treat this suggestion as a tablets of
stone job;
2) choose a better, more descriptive name than 'sn'.

void insert(sn **,int);

Presumably an insert can fail, so why not use an int return type to
indicate success or failure?

void inorder(sn*);

I think I can guess what this will do! For a learning hack, it's fine.

void search(sn**,int,sn**,sn**,int*);

This looks a touch complicated, but - well, we'll see.

void delete(sn**,int);
sn* allocate(int);

That's fine.

int main(void)
{
sn *bt;
int req,i=1,num,dv;
bt = NULL;

I'd write this as:

sn *bt = NULL;
int req = 0;
int i = 1;
int num = 0;
int dv = 0;

....but again, this is mostly a style thing, and anyway some experts will
disagree that my change is for the better. I think we could all agree on
the NULL initialiser for bt, though.

printf("\n Enter the no: of nodes to be inserted:: ");

The standard output stream is typically line-buffered, and so it is not
guaranteed that your output will appear unless you kick the stream
somehow. There are two obvious ways to do this (and I can't think of any
non-obvious and yet portable ways). One is to write a newline character to
the stream after the output that you want to appear (and even then, there
are situations where this might not work, as Chris Torek was pointing out
earlier this year - IIRC it's to do with piping). The other is to call:

fflush(stdout);

Of course, there's no rule that says the implementation *can't* do what you
apparently expect it to do, and indeed the implementation I used to test
your code does actually behave as you would wish. But it's not guaranteed,
that's all.

(This advice applies several times in your code, as do my comments on scanf
and assert, below.)

Also, one of the great strengths of binary search trees is that you don't
actually *need* to know the number of nodes in advance. All you need is
some way to detect when to stop. Yes, okay, asking in advance for the
number of nodes does give you that way, but it isn't necessarily the best
method.

scanf("%d",&req);

You don't test the return value of scanf, and thus you lose valuable
information about the success or otherwise of the request.

assert(req > 0);

Three points here. Firstly, since you didn't initialise req, its value is
indeterminate. If it happens, by chance, to contain a positive value, and
if the user types in something like ONE or SIX or ELEPHANT instead of a
properly constructed number, scanf is very likely not to bother to store
anything in req (IIRC, in fact, the value after a failed conversion is
undefined), so you could end up with an assert that doesn't fire at all,
even for invalid input.

Secondly, the assertion won't fire if NDEBUG is defined.

Thirdly, it is generally a bad idea to use assert for data checking. Its
canonical use is for *program*-checking - which is to say that, if the
assertion fires, you know there's a bug in the program. Assertion messages
tend to be rather terse and unfriendly, and of course a fired assertion
terminates the program. This isn't the best way to handle a user's typo!

If the user gives bad input, print a message telling them what went wrong
in terms that non-programmers can easily understand and, if possible, give
them another try.

while(i++ <= req)
{
printf("Enter the value of the node you want to insert:: ");
scanf("%d",&num);
insert(&bt,num);
}

printf("Enter the value of the node you want to delete:: ");
scanf("%d",&dv);
assert(dv > 0);

assert(bt != NULL);
delete(&bt,dv);

if(bt == NULL)
{puts("Tree empty");exit(0);}

puts(".............................");
printf("IN ORDER TRAVERSAL\n");
puts(".............................\n");
inorder(bt);

puts("");
return(EXIT_SUCCESS);
}

This all looks more or less fine. (By the way, there's no need to
parenthesise the expression in a return statement.)

void insert(sn** sr,int num)
{
if(*sr == NULL)
{
*sr = allocate(num);

}
else
{
if( num < (*sr) -> val )
insert( &((*sr)->left),num);
else
insert( &((*sr)->right),num);
}
}

Not bad, but I'd rewrite it to allow for the possibility that allocate()
could return NULL (see below). It would look something like this:

int insert(sn **sr, int num)
{
int rc = 0; /* success */
if(*sr == NULL)
{
*sr = allocate(num);
if(*sr == NULL)
{
rc = 1;
}
else
{
if(num < (*sr)->val)
{
rc = insert(&(*sr)->left, num);
}
else
{
rc = insert(&(*sr)->right, num);
}
}
}
return rc;
}

sn* allocate(int n)
{
sn* node;

node = malloc(sizeof(sn));

Better: node = malloc(sizeof *node);

That way, if you decide to change the type, the malloc line doesn't need
editing to keep up.

assert(node != NULL);

Better: if(node != NULL)
{

node -> left = NULL;
node -> right = NULL;
node -> val = n;

}

return node;
}

void inorder(sn *root)
{
if(root != NULL)
{
inorder(root -> left);
printf("%d\t",root ->val);
inorder(root -> right);
}
}

That's fine.

I'm going to stop there. I had a quick look at the rest of the code, and I
couldn't see anything that I felt obliged to comment on (in other words,
there were no glaring problems that I could see), so that's good. But you
asked whether the deletion method could be improved, and the right person
to answer that question is Ben Pfaff, not me.

<snip>

 

[Keith Thompson]

(e-mail address removed) said: [...]

typedef struct node
{
struct node *left;
struct node *right;
int val;
}sn;

This is fine, although I'd suggest two changes:

1) separate the typedef from the struct definition - but this, again, is a
minor matter of style, so don't treat this suggestion as a tablets of
stone job;

On the other hand, combining a typedef with a struct declaration is a
very common idiom. You need at least to be able to recognize and
understand it in code that you read.

2) choose a better, more descriptive name than 'sn'.

My own preference (with which many intelligent people disagree) is to
omit the typedef altogether:

struct node {
struct node *left;
struct node *right;
int val;
};

Your type already has a perfectly good name, "struct node". Giving it
another name "sn" doesn't really add anything. Just call it "struct
node" everywhere.

On the other hand, there's something to be said for having a one-word
name for a type, and maybe you don't actually need to be reminded that
it's a struct every time you refer to it.

If you do choose to define both a struct tag and a typedef, the two
names should be related somehow. Pick a consistent convention. Since
struct tags and typedefs are in different namespaces, you can use the
same identifier for both:

typedef struct node {
struct node *left;
struct node *right;
int val;
} node;

It's been argued that this could make things more difficult in some
environments. The compiler knows perfectly well that "node" and
"struct node" are two different things, but your IDE (interactive
development environment) might not be quite as smart. If you select
fan occurrence of "node" and ask the system to show you its
declaration, it might get confused. I don't use such an IDE myself,
so I don't know how much of a problem this is.

You could also, say, consistently append "_s" to the tag name:

typedef struct node_s {
struct node_s *left;
struct node_s *right;
int val;
} node;

Now "struct node_s" and "node" refer to the same type, and the uglier
name "struct node_s" is the one that you use the least.

This is probably more than you wanted to know.

[...]

You don't test the return value of scanf, and thus you lose valuable
information about the success or otherwise of the request.


Three points here. Firstly, since you didn't initialise req, its value is
indeterminate. If it happens, by chance, to contain a positive value, and
if the user types in something like ONE or SIX or ELEPHANT instead of a
properly constructed number, scanf is very likely not to bother to store
anything in req (IIRC, in fact, the value after a failed conversion is
undefined), so you could end up with an assert that doesn't fire at all,
even for invalid input.

To be clear, the value of req was indeterminate before the call to
scanf. If scanf fails (because the user typed ELEPHANT), the value of
req will still be indeterminate *after* the call to scanf. If the
scanf call succeeds, you're ok.

I had assumed that a failed conversion would leave the value alone. I
just checked the standard, and I *think* scanf will return without
assigning a value, but I'm not certain.

If this is correct, then you could just initialize req to 0; a
matching failure would cause it to remain 0, and you could treat it as
equivalent to the user typing "0" explicitly. But that's not a very
good approach; it depends on fscanf behavior that's not 100% certain,
it doesn't allow you to distinguish between different kinds of errors,
and it doesn't extend to cases where all possible inputs are valid.

Instead, as Richard suggests, you should check the return value of
scanf() and take action based on that; on failure, you can die with an
error message (using something other than assert(), or you can try
again.

Note that trying again is going to be a little difficult. If the user
types "ELEPHANT", that input will still be there waiting to be read.
One approach is to read and discard characters up to and including a
new-line. A better approach, in general, is to read a line at at time
into a string, and then extract the information you want from the
string. This gives you much better control than you can get with
scanf.

Of course, all this is about input, not about binary trees.

[SNIP]

 

[Ben Bacarisse]

this is a simple binary tree program done by me for learning node
deletions in a binary tree, how good is the deletion method ???? can
anyone suggest corrections/improvements ????

Questions about the "method" are best asked in comp.programming and I
won't go into that here. My comment is on the implementation.

Binary trees are recursive by definition and you get a huge simplicity
payoff by manipulating them recursively. Here is how I would do
delete. Given:

typedef struct tree_node {
int val;
struct tree_node *left, *right;
} Tree;

(Sorry this is not the same as yours, but I want to cut and past
without too much editing.)

Tree *tree_join(Tree *a, Tree *b);

Tree *tree_delete(Tree *tree, int v)
{
if (tree) {
if (tree->val == v) {
Tree *node = tree;
tree = tree_join(tree->left, tree->right);
free(node);
}
else if (v < tree->val)
tree->left = tree_delete(tree->left, v);
else tree->right = tree_delete(tree->right, v);
}
return tree;
}

Tree *tree_join(Tree *a, Tree *b)
{
if (a == 0)
return b;
else if (b == 0)
return a;
else if (a->val < b->val) {
a->right = tree_join(a->right, b);
return a;
}
else {
b->left = tree_join(b->left, a);
return b;
}
}

I think this is much simpler to argue about. If you need a return
code from delete then you can do that just as easily (and I would):

int tree_delete_p(Tree **treep, int v)
{
Tree *tree;
if ((tree = *treep) != 0) {
if (tree->val == v) {
*treep = tree_join(tree->left, tree->right);
free(tree);
return 1;
}
else if (v < tree->val)
return tree_delete_p(&tree->left, v);
else return tree_delete_p(&tree->right, v);
}
else return 0;
}

 

[CBFalconer]

These things are highly data and algorithm sensitive. For example,
you really want to keep such trees from degenerating into lists.
This involves various means of maintaining reasonable balance. So
the first thing to do is to settle this matter, and describe it in
words (including deciding to ignore the problem).

You have done a fairly good job of indenting etc, but far from
perfect. I recommend the use of 'indent' program, available (from
gnu) for everywhere. If I have time I will later apply it and
follow with some editing to illustrate some of my meanings.

Following is the rough rework I semi-promised. Note the following:

1. Prototypes are eliminated. Instead, functions are declared
at appropriate places, thus eliminating copying of headers.

2. I have reduced the excess vertical spaceing.

3. I have added clear inter-function markers.

In general you should also remove the 'assert' function. Learn to
detect and react to errors yourself. You should never use the
scanf function(s) without checking their return values. (This will
help removing the asserts). You should use function return values,
for example the search function should return either NULL (for
failure) or the appropriate pointer. Make sure every malloced
memory chunk is eventually freed, avoiding memory leaks.

A printf of nothing but a constant string can be replaced by a
puts, unless you don't want the terminal '\n'.

You show great promise. You do tend to over-complicate functions.
For example, the search has some sort of extra parameters to return
parentage. I haven't followed the usage, but I react to the
complexity of the resultant function and the excess parameters
needed.

You should look up AVR trees and red/black trees. This reflects my
original suggestions on adequate commenting. Also use more
descriptive variable names. Draw linkage pictures before and after
various operations to make the processes clear.

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

typedef struct node {
struct node *left;
struct node *right;
int val;
} sn;

/* ---------------- */

sn *allocate(int n)
{
sn *node;

node = malloc(sizeof *node); /* note revision */
assert(node != NULL);
node->left = NULL;
node->right = NULL;
node->val = n;
return node;
} /* allocate */

/* ---------------- */

void insert(sn **sr, int num)
{
if (*sr == NULL) *sr = allocate(num);
else if (num < (*sr)->val) insert(&((*sr)->left), num);
else insert(&((*sr)->right), num);
} /* insert */

/* ---------------- */

void inorder(sn *root)
{
if (root != NULL) {
inorder(root->left);
printf("%d\t", root->val);
inorder(root->right);
}
} /* inorder */

/* ---------------- */

void search(sn **root, int num, sn **par, sn **x, int *found)
{
sn *q;

q = *root;
*par = NULL;
*found = 0;

while (q != NULL) {
if (q->val == num) { /* Should be third, not first */
*x = q;
*found = 1;
return;
}
*par = q;
if (q->val < num) q = q->right;
else q = q->left;
}
} /* search */

/* ---------------- */

void delete(sn **root, int num)
{
int found;
sn *parent, *x;
sn *temp, *temp1;


if ((*root)->val == num
&& (*root)->left == NULL && (*root)->right == NULL) {
*root = NULL;
return;
}
parent = x = NULL;
search(root, num, &parent, &x, &found);
if (found == 0) {
puts("Data to be deleted not found");
return;
}
/* if the node to be deleted has no child. */
if (x->left == NULL && x->right == NULL) {
if (parent->left == x) parent->left = NULL;
else parent->right = NULL;
free(x);
return;
}
/* if the node to be deleted has only right child */
if (x->left == NULL && x->right != NULL) {
if (parent == NULL) {
*root = x->right;
return;
}
if (parent->left == x) parent->left = x->right;
else parent->right = x->right;
free(x);
return;
}
/* if the node to be deleted has only left child */
if (x->left != NULL && x->right == NULL) {
if (parent == NULL) {
*root = x->left;
return;
}
if (parent->left == x) parent->left = x->left;
else parent->right = x->left;
free(x);
return;
}
/* if the node to be deleted have both child */
if (x->left != NULL && x->right != NULL) {
if (parent == NULL) {
temp1 = temp = (*root)->left;

while (temp->right != NULL) temp = temp->right;

temp->right = (*root)->right;
*root = temp1;
return;
}
temp1 = temp = x->left;
while (temp->right != NULL) temp = temp->right;
temp->right = x->right;

if (parent->left == x) parent->left = temp1;
else parent->right = temp1;

x->left = x->right = NULL;
free(x);
}
} /* delete */

/* ---------------- */

int main(void)
{
sn *bt;
int req, i = 1, num, dv;

bt = NULL;

printf("\n Enter the no: of nodes to be inserted:: ");
scanf("%d", &req);
assert(req > 0);

while (i++ <= req) {
printf("Enter the value of the node you want to insert:: ");
scanf("%d", &num);
insert(&bt, num);
}

printf("Enter the value of the node you want to delete:: ");
scanf("%d", &dv);
assert(dv > 0);

assert(bt != NULL);
delete(&bt, dv);

if (bt == NULL) {
puts("Tree empty");
exit(0);
}

puts(".............................");
printf("IN ORDER TRAVERSAL\n");
puts(".............................\n");
inorder(bt);

puts("");
return (EXIT_SUCCESS);
} /* main */

 

[Tor Rustad]

Questions about the "method" are best asked in comp.programming and I
won't go into that here. My comment is on the implementation.

Binary trees are recursive by definition and you get a huge simplicity
payoff by manipulating them recursively. Here is how I would do
delete. Given:

typedef struct tree_node {
int val;
struct tree_node *left, *right;
} Tree;

I will not comment on algorithm issues, besides that OP can read about
balanced binary trees, some options include randomized, splay or
red-black trees.

However, the following is a useful abstraction:

/*----- record.h -----*/
typedef int Key;
struct record
{
Key val;

/* data records come here ... */
} ;
Key key(struct record);
/*+++ place compare macros or functions here... */


/*----- record.c -----*/
Key key(struct record r)
{
return r.val;
}
/*+++ add compare functions... */


/*----- tree.h -----*/
#include "record.h"
struct node
{
struct record r;
struct node *left, *right;
} ;

/*----- tree.c -----*/
etc.

writing it this way, there is no need to change the binary tree specific
code, when using different keys or data records for the next project.

 

[Richard]

/* if the node to be deleted has no child. */
if (x->left == NULL && x->right == NULL) {
if (parent->left == x) parent->left = NULL;
else parent->right = NULL;
free(x);
return;
}

This style I find simply unreadable. Almost impossible to spot "from
afar" the logical flow.

,----
| if (x->left == NULL && x->right == NULL) {
| if (parent->left == x){
| parent->left = NULL;
| }else{
| parent->right = NULL;
| }
| free(x);
| return;
| }
`----

Easy to see the control flow. Brackets already there for any later
additions with no bracketing errors. Debugger friendly. The first set of
code would not have been accepted by any of the wide ranging standards I
have ever used on personal and professional code bases. Advice to nOObs
: consider the two above and draw your own conclusions. Style can be a
personal thing : but in the real world where other people might be
responsible for extending or fixing your code then the second style is
100% better and more readable than the first - no questions. And anyone
that argues the first is more clear is almost certainly inexperienced in
multi-programmer projects.