Binary Trees in C

[Chris Torek]

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 at cs.umd.edu	Path:	uunet!mimsy!chris