Chapter 9. Trees

Picture a family tree, the draw sheet of a tournament, or the roots of a plant; these are all good examples of a tree's organization as a data structure. In computing, a tree consists of elements called nodes organized in a hierarchical arrangement. The node at the top of the hierarchy is called the root . The nodes directly below the root are its children , which in turn usually have children of their own. With the exception of the root, each node in the hierarchy has exactly one parent, which is the node directly above it. The number of children a node may parent depends on the type of tree. This number is a tree's branching factor, which dictates how fast the tree will branch out as nodes are inserted. This chapter focuses on the binary tree, a relatively simple but powerful tree with a branching factor of 2. It also explores binary search trees, binary trees organized specifically for searching.

This chapter covers: