Essential Algorithms: A Practical Approach to Computer Algorithms

CHAPTER 10

Trees

This chapter explains trees, highly recursive data structures that you can use to store hierarchical data and model decision processes. For example, you can store in a tree 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 you need to understand the more complicated trees described in Chapters 11 and 12.

Tree Terminology

Trees borrow terminology 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. Chapters 13 and 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 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 root node, which has no parent.

The children, the children's ...