mjd@saul.cis.upenn.edu (Mark-Jason Dominus) (05/02/91)
I'm writing a replacement for the UNIX `tsearch' library. `tsearch'
is a standard UNIX package which provides prefab support for search,
delete, and insert operations on binary trees. My library uses 2-3
trees instead of binary trees.
My question relates specifically to a routine I'm writring that
traverses the tree and lets the user call a function at each node. This
is the counterpart of the `twalk' routine in the UNIX `tsearch' library.
If you are familiar with `twalk', you can skip the next three
paragraphs.
For those unfamiliar with the `twalk' routine: The user supplies the
root of the tree he or she wishes to traverse, and a pointer to an
`action' function that will be called at each node. `action' takes
three parameters: the current node of the walk, the distance of the
current node from the root of the tree, and a `visit-descriptor'.
It is this third argument that is interesting to me.
`action' is called once at each leaf node; the thrid parameter is
LEAF. At internal nodes, the function is called three times: Once
before `twalk' begins traversal of the node's children (the third
parameter is PRE); once after traversal of the left child is finished
but before traversal of the right child is begun (the third parameter is
IN this time); and once after the traversal of both children (the third
parameter is POST).
Thus for example, if you have a binary tree whose keys are in sorted
order, you can print out the keys in sorted order by supplying a funtion
to `twalk' which prints out the data in the current node when it is
called with third parameter equal to LEAF or IN, and which does nothing
on PRE or POST.
--- UNIX people continue here ---
If the tree were an expression tree, we could print it out in
(prefix form, infix form, postfix form) respectively by supplying an
action which printed the data asscoiated with a certain node when it was
called with third parameter LEAF or with third parameter (PRE, IN,
POST), respectively.
The `prefix' and `postfix' capabilities are clearly useful for
expression trees, but the `tsearch` package doesn't otherwise seem to be
very useful for expression trees; it's better for database access and
maintaining sorted lists of data.
Question #1: (UNIX people only) Are the `tsearch' routines good for
applications not obviously involving sorted data? (Managing expression
trees, for example?)
Question #2: Are there any natural applications of preorder or postorder
walks of a sorted tree? (UNIX people, have you ever used the preorder
or postorder capabilities of the `tsearch' package? What for?)
Question #3: Is anyone likely to use a 2-3-tree manager package for
anything other than quick access to sorted lists of data? Is it worth
putting in `preorder' and `postorder' functionality of some kind? (I'm
not quite sure what this would mean, but perhaps your answer will help
me out here.)
I've pointed followups at comp.misc, since this relates to UNIX only
peripherally.
Thanks.
Nihil tam absurde dici potest, quod non dicatur ab aliquo philosophorum.
Mark-Jason Dominus mjd@central.cis.upenn.edu