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 of a tree Node looks like this:
template <class T>
struct Node {
T cargo;
Node<T>* left;
Node<T>* right;
Node(T cargo) {
this->cargo = cargo;
this->left = nullptr;
this->right = nullptr;
}
Node(T cargo, Node<T>* left, Node<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.
Node<int>* tree = new Node<int>(1);
tree->left = new Node<int>(2);
tree->right = new Node<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 NULL 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
An empty tree.
A node containing data and two pointers to binary trees.
The first part of this definition provided 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. If we want to build a tree that looks like this:
We could build it from the bottom up like this:
Node<int>* t1 = new Node<int>(6, new Node<int>(5), new Node<int>(11));
Node<int>* t2 = new Node<int>(9, new Node<int>(5), nullptr);
Node<int>* t3 = new Node<int>(7, new Node<int>(2), t1);
Node<int>* t4 = new Node<int>(9, nullptr, t2);
Node<int>* tree = new Node<int>(1, t3, t4);
Write a program to test this, and add:
cout << tree->left->right->right->cargo;
and confirm you get 11.
20.4. Binary Search Trees¶
template <class T>
class SearchTree {
Node<T>* root;
public:
};
20.5. 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.