Trees

Trees

Many logical relationships are not simply linear. Real situations often involve one-to-many or many-to-many relationships. Trees and graphs are typical nonlinear data structures.

Like trees in nature, these structures grow branches from one root, smaller branches from each branch, and finally leaves.

A tree is a hierarchical collection of $n\ (n\ge 0)$ nodes. When $n=0$, it is an empty tree.

Every nonempty tree has these properties:

• Exactly one designated node is the root.

• When $n>1$, the remaining nodes form $m\ (m>0)$ disjoint sets $T_1,T_2,\dots,T_m$. Each is itself a tree and is called a subtree of the root.

• Root: a node with no parent.

• Internal node: a node with at least one child.

• External node / leaf: a node with no children.

• Degree: the number of branches from a node.

• Path: the branches followed from the root to a particular node.

• Ancestors: its parent, its parent's parent, and so on.

• Descendants: its children, their children, and so on.

• Depth: the number of edges from the root to a node; the root has depth 0. Tree height: the maximum number of levels. This chapter counts height in node levels, with height 0 for an empty tree.

Binary trees

Each node of a binary tree has at most two children: two, one, or none.

They are the left child and the right child. Their order is fixed; they cannot be exchanged or confused.

Binary trees have several special forms.

Left-skewed / right-skewed tree

A binary tree containing only left branches or only right branches.

Perfect binary tree

Every non-leaf node has both children, and all leaves are on the same level.

Complete binary tree

Number nodes in level order from 1 to $n$. Their positions coincide with the first $n$ positions of a perfect tree of the same height. Equivalently, every level except the last is full, and the last level is filled continuously from the left.

Storing binary trees

Binary trees can be stored with links or in an array.

Linked storage

A node may point to its left and right children, so it contains three fields:

• The data field data.

• A pointer left to the left child.

• A pointer right to the right child.

Array storage

Place nodes in the corresponding level-order array positions. If a child is missing, leave its corresponding position empty.

An array makes it convenient to locate children and parents. For parent index parent, the left child has index 2 * parent + 1 and the right child 2 * parent + 2. Conversely, the parent of index leftChild is floor((leftChild - 1) / 2).

Arrays waste substantial space for sparse binary trees. The binary heap, a particular complete binary tree, uses array storage.