Mastering Algorithms with C

Description of Binary Trees

A binary tree is a hierarchical arrangement of nodes , each having up to two nodes immediately below it. The nodes immediately below a node are called its children . The node above each child is called its parent . Nodes can also have siblings , descendants , and ancestors . As you might expect, the siblings of a node are the other children of its parent. The descendants of a node are all of the nodes branching out below it. The ancestors of a node are all the nodes along the path between it and the root. The performance associated with a tree often is discussed in terms of its height, the number of levels in which nodes reside. As we will see, tree terminology is as much familial as it is arboreal (see Figure 9.1).

Each node in a binary tree contains three parts: a data member and two pointers called the left and right pointers. Using this three-member structure, we form a binary tree by setting the left and right pointers of each node to point to its children (see Figure 9.2). If a node does not have a child to its left or right, we set the appropriate pointer to NULL, a convenient sentinel that marks the end of a branch . A branch is a series of nodes beginning at the root and ending at a leaf node . Leaf nodes are the nodes along the fringe of the tree that have no children. Sometimes when working with several trees at once, the trees are said to form a forest.

Figure 9.1. Common tree terminology illustrated with a four-level binary tree

Figure 9.2. Nodes ...