Trees

All of the data structures we have seen so far, such as arrays and linked lists, are linear. In a linear structure, there is a first item and a last item. Every item (except the last) has a successor and every item (except the first) has a predecessor.

This chapter introduces trees, which are more general structures for representing branching or hierarchical data. For example, biological classification diagrams, many organizational charts in businesses, and sports playoff brackets are trees. We have seen a few trees already in this book, including class inheritance diagrams like Figure 3-10 and recursion trees like Figure 9-16.

We begin with a discussion of the simplest kind of trees, binary trees. Using the game of Questions as a running example, Section 10.1 introduces tree terminology and discusses the implementation of binary trees. The issue of traversing trees is addressed in Section 10.2. More general trees are covered in Section 10.3, where we use trees to design an intelligent Tic Tac Toe player.