cs230 Lecture Notes
Week 9, Monday

Homework 7 is due tomorrow in lab.

Stella will hand out hw08 in lab tomorrow; it is due next
Monday.

For Thursday, please read Chapter 17, up to and including page 180,
and prepare for a quiz.

Exam #2 is next Thursday.


Today's topics
--------------

1) Trees

2) hw07 tips


Trees
-----

tree node = cargo + 2 references

Fundamental Ambiguity Theorem applies to tree nodes, too


In this case, probably no sentinel class.  Just tree nodes,
which will be objects with type Tree.

Vocabulary:

node, root, leaf, child, parent, level


What are trees good for?

1) representativeness: many computational structures can be
   represented naturally in the form of a tree

Example: expression trees

Example: diagnosis trees


2) performance: many algorithms use trees because their performance
   is better than "linear" data structures (like arrays and linked
   lists)

Example: binary search tree


Traversing trees
----------------

recursive traversals:

Example: add up all the elements of the tree...

(assume that the cargo are Integers)

public static int total (Tree tree) {
    if (tree == null) return 0;
    Integer cargo = (Integer) tree.cargo;
    return cargo.intValue() + total (tree.left) + total (tree.right);
}

Key to recursive thinking: a tree is a node with two subtrees.

Exercise: write a method that finds the largest cargo
(assuming that the cargo are Comparables)











traverse-and-visit:

    public static void print (Tree tree) {
        if (tree == null) return;
        System.out.print (tree + " ");
        print (tree.left);
        print (tree.right);
    }

Alternative traversal orders: 

1) preorder: parent node first, then child subtrees

2) postorder: child subtrees first, then parent

3) inorder: left child, parent, right child


Example: traversing expression trees

	  preorder	prefix
	  postorder	postfix
	  inorder	infix

This is what homework 8 is about.


Binary search tree
------------------

A binary tree is one where each node has 0, 1, or 2 children.

A search tree is one where for every node

  node.left.cargo <= node.cargo <= node.right.cargo

Exercise: write a method called find that takes a binary search
tree and a target object as parameters.  If the target object
appears in the tree, it returns a reference to the node that
contains it.  Otherwise it returns null.


Homework 7
----------

Development plan... what are some intermediate programs we
might want to write along the way?

1) read the lines of a file and print them

2) read lines, make Golfer objects and print them

3) read lines, make Golfer objects, put them in a Stack, take
   them out of the stack and print them

All of that is familiar and easy to write/debug.

Now, when we have a working Priority Queue, all we have to do
is replace Stack with Priority Queue.

4) make a copy of the LinkedList implementation of Queue and
   call it Priority Queue

Conventiently, the sytax for Queue and Priority Queue are the
same.  Only the semantics are different.

5) Modify either insert (to keep the list sorted) or remove
(to find the largest element of the list).

Check encapsulation: the PriorityQueue implementation should
be all about Comparables, with no mention of Golfers.