Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!wuarchive!zaphod.mps.ohio-state.edu!unix.cis.pitt.edu!dsinc!netnews.upenn.edu!grad1.cis.upenn.edu!rmandel
From: rmandel@grad1.cis.upenn.edu
Newsgroups: comp.lang.c
Subject: Binary Trees in C
Keywords: Binary Tree
Message-ID: <21744@netnews.upenn.edu>
Date: 15 Mar 90 17:00:42 GMT
Sender: news@netnews.upenn.edu
Reply-To: rmandel@grad1.cis.upenn.edu ()
Distribution: usa
Organization: University of Pennsylvania
Lines: 66

I'm kind of new to C, and have a problem which is probably obvious
to any connoisseur:

How do you declare a linked list or binary tree type?
The following obvoiusly doesn't work because of the forward reference
to 'node':

typedef struct
   {
   int   label;
   node  *fwd;
   }    node;

I managed to 'trick' the compiler (I'm using TC2.0) by making
"fwd" be a pointer to an int, but then USING it in the above sense.
I don't like this, though --- how do you do it ELEGANTLY?

Also, another problem arises when I insert something in a (similarly
defined) binary tree:

Say I want to insert the value FOO into the tree defined as

typedef struct
   {
   int   label;
   int   *left,
         *right;
   }    btree;

and say, bt is defined as

     btree  *bt,

Now to insert FOO, I pass in the value FOO as well as the binary tree
where it must go:

     insert (FOO, bt);

where "insert" is defined as

void   insert (int val, btree *bt)
{
   if (bt == NULL)
     {
     bt = (btree *) malloc (sizeof(btree));
     bt -> label = val;
     bt -> left  =
     bt -> right = NULL;
     }
    else
     if (val < bt -> label)
       insert (val, bt -> left);
      else
       insert (val, bt -> right);
}

Th problem is that because 'bt' is the actual value passed to each
recursive call to 'insert', it is put on the stack, and discarded 
when we 'bubble up' through the recursion!
I was thinking of passing a pointer to a pointer to a btree, but this
is even more kludgy and incomprehensible than my first problem!

What am I doing wrong? How do you do this?
Any help/code fragments would be GREATLY appreciated.
Thanks,
-Robbie Mandelbaum