20. Trees¶
This chapter presents a new abstract data structure called a tree, and discusses some of its uses.
20.1. A tree node¶
Like linked lists, trees are made up of nodes. A common kind of tree is a binary tree, in which each node contains a reference to two other nodes (possibly null). We will only be studying binary trees in this book, and we will refer to them as “trees” to simplify our discussion.
The definition looks like this:
template <class T>
struct Tree {
T cargo;
Tree<T>* left;
Tree<T>* right;
Tree (T cargo) {
this->cargo = cargo;
this->left = nullptr;
this->right = nullptr;
}
Tree (T cargo, Tree<T>* left, Tree<T>* right) {
this->cargo = cargo;
this->left = left;
this->right = right;
}
};
Like linked list nodes, tree nodes contain cargo, which we are again making
generic by using a template. The other instance variables, left and
right, are pointers to tree nodes that will be linked together to form a
tree.
With this tree node structure defined, we can build a tree by connecting nodes together.
Tree<int>* tree = new Tree<int>(1);
tree->left = new Tree<int>(2);
tree->right = new Tree<int>(3);
We named the pointers left and right in accordance with the way we
represent trees graphically:
The top of the tree (the node to which tree points) is called the root.
In keeping with the tree metaphor, the other nodes are called branches and
the nodes at the tips with nullptr values for both left and right
are called leaves. It may seem odd that we draw the picture with the root
at the top and leaves at the bottom, but that is not the strangest thing.
To make things worse, computer scientists mix in yet another metaphor: the family tree. The top node is sometimes called a parent and the nodes it points to are its children. Nodes with the same parent are called siblings, and so on.
Finally, there is also a geometric vocabulary for talking about trees. In addition to “left” and “right”, we refer to “up” (toward the parent/root) and “down” (toward the children/leaves). Also, all the nodes that are the same distance (the number of links from the root) comprise a level of the tree.
20.2. A tree is a recursive data structure¶
A recursive data structure is a data structure that is made up of smaller or simpler versions of itself. Recurse data structures can have recursive definition, as in the following:
- binary tree
a binary tree is either empty, or
it consists of a root node with cargo and left and right children, both of which are binary trees.
The first part of this definition provides the base case for the recursion.
Note
Lists are similarly recursive data structures, as their treatment by programming languages like Lisp makes abundantly clear.
Algorithms to manipulate recursive data structures like binary trees tend to lend themselves to the use of recursion, as we will soon see.
20.3. Building trees¶
The process of assembling tree nodes is similar to the process of assembling linked list.
20.4. Glossary¶
- binary tree¶
A tree in which each node refers to 0, 1, or 2 dependent nodes.
- root¶
The top-most node in a tree, to which no other nodes refer.
- leaf¶
A bottom-most node in a tree, which refers to no other nodes.
- parent¶
The node that refers to a given node.
- child¶
On of the nodes referred to by a node.
- level¶
The set of nodes equidistant from the root.
- recurse data structure¶
A data structure that is partially composed of smaller or simpler examples of itself.
- prefix notation¶
A way of writing a mathematical expression with each operator appearing before its operands.
- preorder¶
A way to traverse a tree, visiting each node before its children.
- postorder¶
A way to traverse a tree, visiting the children of each node before the node itself.
- inorder¶
A way to traverse a tree, visiting the left subtree, then the root, then the right subtree.
- binary operator¶
An operator that takes two operands.