CS231 lecture notes, Fall 1998
Week 9, Monday

Reading: Chapter 8

Quiz Wednesday, Exam next Wednesday

Chapter 8 -- trees and graphs
-----------------------------

Lots of weird terms for trees and their parts, depending on your
analogy of choice:

1) parent, child, sibling, ancestor

2) left, right, up, down

3) root, internal node, leaf, branch

Mixed metaphors:

1) root is at the top, leaves at the bottom

2) a leaf is a node with no children

Levels: each node belongs to one level, or generation, determined by
the distance from the root.

There is exactly one path from the root to each node in the tree
(if not, then by definition you don't have a tree).


Binary trees
------------

So far, we have looked at trees that have a maximum of 2 children
(but may have 0 or 1).  That's a binary tree.

Recursive definition:  a binary tree is either the null tree or
a node that has two children that are binary trees.

  (Wait, I thought you said it could have fewer than 2.)

Complete tree is one in which

1) all leaves are on the same level or

2) all leaves on two adjacent levels, with the leaves on the
   bottom level as far left as possible

How many nodes are there in a complete tree with n levels and
all leaves on the same level?


Traversing binary trees (Section 8.6)
-----------------------

public class Tree {
  int value;
  Tree left, right;

  public Tree (int value, Tree left, Tree right) {
    this.value = value;
    this.left = left;
    this.right = right;
  }

  public static int totalTree (Tree tree) {
    if (tree == null) return 0;
    return tree.value + totalTree (tree.left) + totalTree (tree.right);
  }

  public static void main (String[] args) {
    Tree root = new Tree (3, null, null);
    Tree branch1 = new Tree (5, null, null);
    Tree branch2 = new Tree (7, null, null);

    root.left = branch1;
    root.right = branch2;

    int x = totalTree (root);
    System.out.println (x);
  }
}

This is a LINKED REPRESENTATION of a binary tree.

A traversal of a tree is a process that visits each
node in the tree once, in some order.

By "visit" I mean perform some computation: in the
following examples, "visit" will mean "print the contents"

There are three recursive orderings:

1) pre-order: print root first, then left tree, then right

2) in-order: print left tree, then root, then right tree

3) post-order: print left tree, then right tree, then root

They are called recursive orderings because they can be
implemented naturally using recursion.


Example: expression trees

(b^2 - 4 * a * c) / (2 * a)

a - b

What does an in-order traversal of these trees yield?
What does a post-order traversal of these trees yield?
What does a pre-order traversal of these trees yield?


Using a stack to manage recursion
---------------------------------

In notes13.txt, we saw a way to use a stack to make a recursive
method iterative.

  public static int totalTree2 (Tree root) {
    Stack stack = new Stack ();

    stack.push (root);
    Tree tree;
    int total = 0;

    while (!stack.empty()) {
      tree = (Tree) stack.pop ();

      if (tree != null) {
        total += tree.value;
        stack.push (tree.right);
        stack.push ((tree.left);
      }
    }
    return total;
  }

We can do the same thing with a pre-order traversal:

  (transform the preceding code into a pre-order traversal).

What happens if we replace the stack with a queue?