7 Threaded Binary Search Trees [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

Traversal in inorder, as done by libavl traversers, is a common operation in a binary tree. To do this efficiently in an ordinary binary search tree or balanced tree, we need to maintain a list of the nodes above the current node, or at least a list of nodes still to be visited. This need leads to the stack used in struct bst_traverser and friends.

It's really too bad that we need such stacks for traversal. First, they take up space. Second, they're fragile: if an item is inserted into or deleted from the tree during traversal, or if the tree is balanced, we have to rebuild the traverser's stack. In addition, it can sometimes be difficult to know in advance how tall the stack will need to be, as demonstrated by the code that we wrote to handle stack overflow.

These problems are important enough that, in this book, we'll look at two different solutions. This chapter looks at the first of these, which adds special pointers, each called a thread (see thread), to nodes, producing what is called a threaded binary search tree, threaded tree (see threaded tree), or simply a TBST.1 Later in the book, we'll examine an alternate and more general solution using a parent pointer (see parent pointer) in each node.

Here's the outline of the TBST code. We're using the prefix tbst_ this time: 

249. <tbst.h 249> =
<Library License 1>
#ifndef TBST_H
#define TBST_H 1

#include <stddef.h>

<Table types; tbl => tbst 15>
<TBST table structure 252>
<TBST node structure 251>
<TBST traverser structure 269>
<Table function prototypes; tbl => tbst 16>
<BST extra function prototypes; bst => tbst 89>

#endif /* tbst.h */


250. <tbst.c 250> =
<Library License 1>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "tbst.h"

<TBST functions 253>

Footnotes

[1] This usage of “thread” has nothing to do with the idea of a program with multiple “threads of excecution”, a form of multitasking within a single program.