Buy GNU books!
|[ < ]||[ > ]||[ << ]||[ Up ]||[ >> ]||[Top]||[Contents]||[Index]||[ ? ]|
We need two extra fields in the node structure to keep track of whether each link is a child pointer or a thread. Each of these fields is called a tag (see tag). The revised struct tbst_node, along with enum tbst_tag for tags, looks like this:
/* Characterizes a link as a child pointer or a thread. */ enum tbst_tag
Each element of tbst_tag is set to TBST_CHILD if the corresponding tbst_link element is a child pointer, or to TBST_THREAD if it is a thread. The other members of struct tbst_node should be familiar.
We also want a revised table structure, because traversers in threaded trees do not need a generation number:
/* Tree data structure. */ struct tbst_table
There is no need to define a maximum height for TBST trees because none of the TBST functions use a stack.
1. We defined enum tbst_tag for distinguishing threads from child pointers, but declared the actual tag members as unsigned char instead. Why? [answer]
|webmaster donations bookstore||delorie software privacy|
|Copyright © 2003 by The Free Software Foundation||Updated Jun 2003|