Trees are structurally a lot like linked lists. Actually, a linked list is a simplistic kind of tree.
Recall that a linked list “node” had a value and a “next” pointer. The tree structure also has (one or more) values plus (one or more) pointers:
The only difference with a linked list is that the tree has two (or
more) “next pointers,” or as we label them in the class, a “left” and
“right” next pointer. We use the
NULL (0) pointer to indicate that
right pointers point to nothing.
A tree can have any number of next pointers; if it always has two
(each of which may or may not equal
NULL), like we will do here,
it’s a binary tree. Surely you imagine a tree that had three pointers,
or even an array of pointers, rather than just two.
Thus, a tree’s “next pointers” are more like “children” — each node in a binary tree has zero, one, or two children. Those children are also trees. Additionally, a tree has only one “parent.” That is to say, for each node in the tree, either that node is the top (the “root”) or only one node links to it (it is the child of only one node).
If we do not restrict trees in this way, and allow different nodes to link to the same children, then our algorithms for processing such structures will be more complicated. Actually, we wouldn’t even call them trees anymore; the correct terminology is “graph.” A graph is a structure where every node can have links to any other node, even back to itself (so trees are a kind of graph). See the graphs notes for more details.
Building a tree
Consider a kind of binary tree that represents arithmetic expressions,
2 + sin(5) and so on. Each node in the tree is either a number
or an operator (
sin, etc.). Some operators are unary (
some are binary (
+). Unary operators have a left subtree but no
right subtree. Binary operators have both subtrees.
Here is our new tree structure:
std::string instead of
string in case
std; is not present.)
Let’s now build a tree. Suppose we want to represent the expression
3.4-(2.6+5.0). This is what the tree should look like:
Here is how we build it in code. Note that we have to make a variable for each node, set each variable’s values, then link the variables together.
This code makes the variable
m (for “minus”) the top node, i.e. the
“root” of the tree.
Processing the tree: printing its values
Now, suppose you have a tree; actually, suppose you have a variable
root that’s a pointer to a tree. For example,
Starting with this “root” pointer, how do we get to all the nodes in the tree, and print their values? Specifically, how do we print the values in the tree in such a way as to arrive at an equivalent arithmetic expression (perhaps with extra parentheses)?
Our task is to take the tree we’ve defined and print the contents of
the tree in this form:
You’ll notice that the printed form of the tree follows a simple
pattern: for every operation, print a
(, then the contents of the
left subtree, then the operation (e.g.
+), then the contents of the
right subtree, finally a
Unlike linked lists, trees are non-linear, so we cannot process them in a linear manner. For some node in the tree, we cannot know how big a subtree there is on the left side or the right side. So we cannot simply set up a loop to process the left and right subtrees; instead, we must resort to a recursive procedure.
Notice that the description above of how to print the contents of the
tree was a recursive description: “print a
(, then the contents of
the left subtree, then …” Suppose we call this process
print_tree. Then we can rewrite the description like this:
print_treeprocedure works as follows: Print a
(. Then, follow the
print_treeprocedure (this very same procedure) on the left subtree. Then, print the operation (e.g.
+). Then, follow the
print_treeprocedure on the right subtree. Finally, print a
There are a few minor problems with that description. First, if the
node is just a value (that is,
op == ""), then we just print the
value and don’t bother with
) or left and right subtrees
(values don’t have left or right subtrees; those pointers are
pointers). Also, if there is no tree (the node we’re looking at is
NULL pointer), then we don’t need to do anything.
Now we can code this procedure in C++, as a function:
Using the function like this:
print_tree(root) results in the
(3.4-(2.6+5)), which is just what we want.
A slight variation: handling other kinds of operators
As described above, these trees may have both binary and unary
operators. If we use the same
print_tree function with a tree that
has a unary operator in it, we get output that doesn’t look right.
For example, the tree
/ / \ / \ / \ sin cos / / 4.00 4.00
((4sin)/(4cos)) (do you see why?).
We can fix this by adding another conditional in our code. Unary
operators have only a left subtree, and no right subtree (while
-, etc. always have subtrees on both sides). So, we
simply check if we have an operator and there is no right subtree; if
so, we print the operator first, then
(, then the left subtree, then
Now, that same tree prints as
(sin(4)/cos(4)), which is what we
print_treemethod above is a bit more complicated than a simple pre-order, in-order, or post-order. Write each of these other tree printing functions.
Write a tree destructor,
Write a tree search function,
bool search_tree(double search_val), that looks through the whole tree for
Write a function,
void delete_subtree(double search_val), that deletes the whole subtree starting at the first occurrence of
search_val(if it is found). If
search_valis found multiple times in the tree, only the first occurrence (and its subtree) is deleted.
double multiply_collapse()method that multiplies every value in the tree together and returns the result.