programs for B-trees wanted

[moss at BRL-VLD.ARPA]

From:      "Gary S. Moss (AMXBR-VLD-V)" <moss at BRL-VLD.ARPA>

While waiting and waiting for our System V license to arrive, I wrote an
implementation of tsearch(3).  It has three functions described here briefly.

	char *tsearch( (char *) key, (char **) rootp, compar )
	int (*compar)();

	Binary tree search, returns pointer into a tree indicating where
	a datum may be found.  If the datum does not occur it is inserted.
	It only returns NULL if 'rootp' is NULL on entry or there is no
	space to create a node.  You can't tell if the node was there already
	or not, Yucko!

I soon decided that I didn't like the behavior of the tsearch() function as
documented (if it doesn't find a datum, it inserts it) and changed it to only
report whether or not the datum exists and added a function called tinsert()
which would behave as the original tsearch() did.  They later fixed this in
System VR2 by adding a function tfind().  This change was more upward compat-
able than mine, and I probably should change the names in the library, but
since we now have our license, my library will probably go away.

	char *tdelete( (char *) key, (char **) rootp, compar )
	int (*compar)();

	Returns a pointer to the parent of the deleted node, or NULL if the
	node is not found or 'rootp' is NULL on entry.

	void twalk( (char *) root, action )
	void (*action)();

	Traverses a binary tree and envokes 'action' at each visit to a node,
	with 3 arguments;  the node address, an enum data type describing
	which visit {preorder, postorder, endorder, leaf} and the level in
	the tree of the node.  There choice of terms here was strange, so I
	changed 'endorder' to 'inorder', but then Knuth originally got that
	wrong too, and that's where these algorithms were taken (Bell's not
	mine).

If you don't have System V and want a public domain copy, send me a note
and I'll mail you my sources and manual page.

-- Moss.