[comp.lang.c] Binary Trees in C

rmandel@grad1.cis.upenn.edu (03/16/90)

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

apippin@polyslo.CalPoly.EDU (Pinhead@Spikes) (03/16/90)

Add then rmandel@grad1.cis.upenn.edu () babbles...
~How do you declare a linked list or binary tree type?

Try:

	typedef struct _node  nodeptr;
	struct _node  {
	    int   i;
	    nodeptr  right;
	    nodeptr  left;
	}

	This works on a Sun 3, Pyramid and Macintoys.

    aBp.

-- 
Andy Pippin  -*-  apippin@polyslo.CalPoly.EDU  -*-  Conserve water, drink bier.

chris@mimsy.umd.edu (Chris Torek) (03/16/90)

The first thing to do is forget about typedef (until later, after
you declare the data structures at least):

	struct btree {
		int value;
		struct btree *left;
		struct btree *right;
	};

Later (actually, after typing this much) you can go back and add the
typedef:

	typedef struct btree {
		int value;
		struct btree *left;
		struct btree *right;
	} btree;

The key to getting forward pointer declarations is using the `struct'
style declarations.  The typedef name does not exist when you need it,
but the keyword `struct' allows undefined and partially define names
after it, provided that the thing being declared is a pointer:

	struct a {
		int aval;
		struct b *bp;
	};

	struct b {
		int bval;
		struct a *ap;
	};

Without allowing forward (partial) declarations, there would be no way to
write structures a and b above.

Note that if there *is* a `struct b' around before the `struct a' declaration,
the `bp' field in `struct a' will point to the *wrong* struct b.  That is:

	struct b {
		int some_int;
	};

	void function() {
		struct a {
			int aval;
			struct b *bp;
		} a;
		struct b {
			int bval;
			struct a *ap;
		} b;
		<...code...>
	}

Now `a.bp' points to a `struct b' that has one `some_int' field,
rather than one `bval' field and one `struct a *' field.  The
solution is to add a partial declaration for struct b ahead of
the one for struct a:

	void function() {
		struct b; /* tell compiler there is a new one coming up */
		struct a {
			int aval;
			struct b *bp;
		} a;
		struct b {
			int bval;
			struct a *ap;
		} b;
		<...code...>
	}

This time `a.bp' points to the new `struct b' instead of the old one.

As for your binary tree implementation: I would likely use pointers to
pointers, but then I write declarations like

	int (*(*bloog[10])(char *, void (*)(int, int (*)(void))))[4];

without flinching. :-)

Chris
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris@cs.umd.edu	Path:	uunet!mimsy!chris

frotz@drivax.UUCP (Frotz) (03/17/90)

rmandel@grad1.cis.upenn.edu writes:

] 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?

Try:
	typedef struct _node_	/* where _node_ is the struct "tag"	*/
	{
		int	value;
	struct	_node_*	left;	/* The compiler knows about "tag"	*/
	struct	_node_*	right;	/* It doesn't know about "node" yet.	*/
	} node;


] 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!


Try always returning the tree root.  You may or may not be interested
in the return value within the routine.  If you do, you can add logic
to try to balance the tree and thereby pass the new tree root up to
the caller.  If, however, you ignore the return value internally your
tree may become imbalanced. 

e.g.  node* insert( node* root, value );

--Frotz @Digital Research, Incorporated		amdahl!drivax!frotz
	 Graphics Business Unit			(408) 647-6570 (msg)
	 70 Garden Court, B15			(408) 649-3896
	 Monterey, California  93940		Ask for John Fa'atuai

karl@haddock.ima.isc.com (Karl Heuer) (03/22/90)

In article <1990Mar16.112415.803@hellgate.utah.edu> kbreinho%ug.utah.edu@cs.utah.edu (Keith Breinholt) writes:
>In article <23127@mimsy.umd.edu> chris@mimsy.umd.edu (Chris Torek) writes:
>>As for your binary tree implementation: I would likely use pointers to
>>pointers, but then I write declarations like
>>	int (*(*bloog[10])(char *, void (*)(int, int (*)(void))))[4];
>>without flinching. :-)
>
>... Do you really think someone would want to [maintain] crap like that?

Actually, I have to agree.  Since a pointer-to-entire-array is so much weaker
than a pointer-to-element, I would assume that the existence of even a single
function returning such a type (not to mention an array of pointers to such
functions) is evidence that, in this project, "int[4]" is an important
construct and should probably have had its own typedef.

Of course, that has to have been an exaggerated example--did you miss the
smiley?  A more serious example would be
	extern void (*signal(int, void (*)(int)))(int);
, which is probably the most complex declaration you'd encounter in practice.
Though I personally don't bother with "typedef void (*sighandler_t)(int)", I
don't look down on those who do.

But for the original problem, a pointer-to-pointer seems to be the natural
solution, and anybody who can't understand such a construct needs to practice
a bit more before trying to write production-quality code.

Karl W. Z. Heuer (karl@ima.ima.isc.com or harvard!ima!karl), The Walking Lint

news@awdprime.UUCP (USENET News) (03/23/90)

In article <25fff2a9.36f0@polyslo.CalPoly.EDU> apippin@polyslo.CalPoly.EDU (Pinhead@Spikes) writes:
-Add then rmandel@grad1.cis.upenn.edu () babbles...
->How do you declare a linked list or binary tree type?
-Try:
-
-	typedef struct _node  nodeptr;
-	struct _node  {
-	    int   i;
-	    nodeptr  right;
-	    nodeptr  left;
-	}
Lest we confuse the masses, I think that should have read:

    typedef struct _node *nodeptr;
			 ^
			 |
			 NOTE THE *.

We thank you for your support,
-- sanders
For every message of the day, a new improved message will arise to overcome it.
Reply-To: cs.utexas.edu!ibmaus!auschs!sanders.austin.ibm.com!sanders     (ugh!)

erlkonig@walt.cc.utexas.edu (Christopher North-Keys) (03/29/90)

(line "#" is corrected as per the first followup)

-Add then rmandel@grad1.cis.upenn.edu () babbles...
->How do you declare a linked list or binary tree type?
-Try:
-
#       typedef struct _node  *nodeptr;
-       struct _node  {
-           int   i;
-           nodeptr  right;
-           nodeptr  left;
-       }

Try:

typedef struct _node {
	int           i;
	struct _node *left;
	struct _node *right;
}	*nodeptr;


------------------------------------/\----------------------------------------
Seo:  Harp[@Mcc.Com]               /  \/\ ^*^           Christopher North-Keys
Tha mi gu trang a'cluich.         /    \ \         Assoc. Systems Analyst, MCC
--------------------------------(disclaimer)----------------------------------