CS 240: Lecture 24 – Binary Trees
Dear students:
We put the sorts behind us. Of course, nothing ever goes away in software development. We just put layers on top of it. Most of the time, we concern ourselves only with the outermost layer of abstraction: what are the methods named and what parameters do they expect? This class is meant to expose you to the inner workings of the tools that you will use throughout your career.
One data structure that hasn’t been abstracted away like lists and sorting algorithms have is the tree. The tree is often implemented as a linked structure. It’s like a linked list node, but it has multiple links to child nodes. When nodes have no more than two children, we have a binary tree. The linked node of a binary tree might look like this:
public class Tree<T> {
T value;
Tree<T> left;
Tree<T> right;
}
There are many terms used to described the anatomy of a tree and the relationships it encodes. Let’s practice with a few of these:
- root: the topmost node in a tree
- parent: a node that has children
- child: a node that has a parent
- leaf: a node that has no children
- edge: the relationship between a parent and child
- depth: the number of edges from the root to a descendent node
- height: the depth of the bottommost node in a tree; confusingly, it’s one less than the number of levels
- ancestor: a parent node that eventually begets some other node
- descendent: a node that is begotten by some other node
- sibling: a node that has the same parent as another
How many nodes can appear at each depth? Drawing pictures helps answer this question. We see the following:
| depth | number of nodes |
|---|---|
| $0$ | $1$ |
| $1$ | $2$ |
| $2$ | $4$ |
| $3$ | $8$ |
| $4$ | $16$ |
| $5$ | $32$ |
| $\ldots$ | $\ldots$ |
| $i$ | $2^i$ |
That leads to a couple of related questions, which we’ll work through as peer instruction exercises:
- What is the maximum number of nodes that can appear in a tree of height $h$?
- What is the least height that a tree can have if it has $n$ nodes?
We’ll move away from the abstract view of trees into a concrete one by examining how they can be used to model arithmetic expressions. In particular, we’ll see what it takes to represent the expression 5 * 3 + 2 - 9 / 3 as a tree.
Traversals
Occasionally we will need to visit all nodes in a tree, much as we visited all nodes in a list. The order in which visit nodes isn’t necessarily obvious. There are three ordering schemes that are common. An in-order traversal visits the left subtree, the root itself, and then the right subtree:
inOrderTraverse(root) inOrderTraverse(root.left) visit(root) inOrderTraverse(root.right)
A post-order traversal visits the root after visiting its subtrees:
postOrderTraverse(root) postOrderTraverse(root.left) postOrderTraverse(root.right) visit(root)
A pre-order traversal visits the root before visiting its subtrees:
preOrderTraverse(root) visit(root) preOrderTraverse(root.left) preOrderTraverse(root.right)
We’ll examine each of these by writing routines for manipulating our expression trees and solving these problems:
- evaluating an expression
- pretty-printing an expression
- turning an expression into LISP/Scheme/Racket/Clojure
TODO
You have some work to do before the next class:
- Start working on PA3. Get the code from the provide zip file imported. Download the JOpt Simple JAR and add it to your directory in IntelliJ. Then right-click on the JAR in the explorer and click Add as Library.
See you next time.
P.S. It’s time for a haiku!
Are they binary?
One parent can’t make children
Except by forking