Terminology

Data Structures and Algorithms with Object-Oriented Design Patterns in C++

Terminology

Consider a tree , , as given by Definition .

The degree of a node is the number of subtrees associated with that node. E.g., the degree of tree T is n.
A node of degree zero has no subtrees. Such a node is called a leaf .
Each root of subtree of tree T is called a child of r. The term grandchild is defined in a similar manner.
The root node r of tree T is the parent of all the roots of the subtrees , . The term grandparent is defined in a similar manner.
Two roots and of distinct subtrees and of tree T are called siblings .

Clearly the terminology used for describing tree data structures is a curious mixture of the mathematical, the genealogical, and the botanical. There is still more terminology to be introduced, but in order to do that, we need the following definition:

Definition (Path and Path Length) Given a tree T containing the set of nodes R, a path in T is defined as a non-empty sequence of nodes

where , for such that the node in the sequence, , is the parent of the node in the sequence . The length of path P is k-1.

For example, consider again the tree shown in Figure . This tree contains many different paths. In fact, if you count carefully, you should find that there are exactly 29 distinct paths in tree . This includes the path of length zero, ; the path of length one, ; and the path of length three, .