Topics to discuss

• Tree traversal problem in the exam
• Review for the final
• Heaps

Tree Traversal

• Conceptual
  • Most of the implementations of key traversals depend on two things
    • A linear structure that holds "the things we haven't finished with yet"
    • An order in which we "unpack" a node into that linear structure.
  • From the lab
    • Depth-first: Stack
    • Breadth-first: Queue
    • Depth-first, preorder: push value last
    • Depth-first, postorder: push value first

• Implementation

  • Need a field, remaining, that holds the linear structure
  • Need a field, pieces, that holds the left/right/value triplet

  • Initialization

    if "the traversal is left-to-right, preorder, depth-first"
      {
        remaining = new Stack();
        pieces = { "right", "left", "value" };
      }
    else if "the traversal is left-to-right, preorder, breadth-first"
      {
        remaining = new Queue();
        pieces = { "value", "left", "right" };
      }
    

  • Alternately: We can use dictionaries to store this information.

    • Sam has an infrastructure for this.

  • If we just think about traversal and not iteration, the algorithm is straightforward

     while (!remaining.isEmpty())
       {
         next = remaining.get();
         if ("next is a node")
           pull out the pieces and put them into remaining
         else
           process next // e.g. print
       } // while
    

  • We will benefit from a procedure that takes the list of pieces we need, a node, and the linear structure, and uses the list to pull the information and shove it in the linear structure. Provided as unpack.

  • Your goals:
    • 1. Make sure that the remaining and pieces fields get initialized correctly (based on the traversal order). [Make sure that they will work for the order desired.]
    • 1. Turn the traversal algorithm (above) into an interation algorithm. Instead of "traverse the whole tree", we now want "give me the next thing I'd see if I were traversing the tree". Implement next and hasNext.

Final!

• 45 minutes. Talk to Sam.
• Goals:
  • Run algorithms (with accompanying DSs)
  • Analyze algorithms (with accompanying DSs)
  • Build/design algorithms/ADTs
  • Write loop invariants

Outline Heap Sort

• Input:
  • Array
  • Comparator to determine order
• Output:
  • Same array, now sorted (can be turned into a tree)
• Process:
  • Turn the array into a heap (an array-based representation of a heap)
    • Interpret the array as a tree (or a sequence of trees)
    • Repeatedly add an element and restructure
  • Repeatedly grab the largest element and put it at the end of the subarray
• Invariant during building
• Invariant during "repeatedly grab"