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: 

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

#include <stddef.h>

<Table types; tbl => tbst 14>
<TBST table structure 250>
<TBST node structure 249>
<TBST traverser structure 267>
<Table function prototypes; tbl => tbst 15>
<BST extra function prototypes; bst => tbst 88>

#endif /* tbst.h */


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

<TBST functions 251>

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.