Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!samsung!brutus.cs.uiuc.edu!apple!amdahl!drivax!frotz
From: frotz@drivax.UUCP (Frotz)
Newsgroups: comp.lang.c
Subject: Re: Binary Trees in C
Keywords: Binary Tree
Message-ID: <Z2BGJJ2@drivax.UUCP>
Date: 16 Mar 90 17:54:13 GMT
References: <21744@netnews.upenn.edu>
Sender: frotz@drivax.UUCP
Reply-To: frotz@drivax.UUCP
Distribution: usa
Organization: Digital Research, Monterey CA
Lines: 33

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