Essential Algorithms, 2nd Edition

CHAPTER 10Trees

This chapter explains trees, which are highly recursive data structures that you can use to store hierarchical data and model decision processes. For example, a tree can store a company organizational chart or the parts that make up a complex machine such as a car.

This chapter explains how to build relatively simple trees and provides the background that you need to understand the more complicated trees described in Chapter 11 and Chapter 12.

Tree Terminology

Tree terminology includes a hodgepodge of terms taken from genealogy, horticulture, and computer science. Trees use a lot of terms, but many of them are intuitive because you probably already understand what they mean in another context.

A tree consists of nodes connected by branches. Usually, the nodes contain some sort of data, and the branches do not.

NOTE

Trees are a special type of network or graph, so sometimes network and graph terms leak into discussions of trees. For example, branches are sometimes called links or edges, although those terms are more appropriate for networks and graphs. Chapter 13 and Chapter 14 have more to say about networks.

The branches in a tree are usually directed so that they define a parent-child relationship between the nodes that they connect. Normally, branches are drawn as arrows pointing from the parent node to the child node. Two nodes that have the same parent are sometimes called siblings.

Each node in the tree has exactly one parent node, except for a single, ...