Held: Friday, 22 November 2013

Back to Outline 44 - Trees, Generalized. On to Outline 46 - Implementing Dictionaries with Hash Tables.

Summary

We consider orders in which one might visit the nodes in a tree and the algorithms one uses to achieve those orders.

Related Pages

• Lab: Tree Traversal
• Code: https://github.com/Grinnell-CSCS207/bst
• EBoard (HTML) (PDF)

Overview

Orders for traversing the tree. Implementating traversal algorithms.

Administrivia

• I'll reserve time for questions on the exam.
• Less than half of you have filled out the prologue. Remember that it's due at 5pm today.
• Upcoming extra credit opportunities:
  • CS Table today, The New Curriculum
  • Hamlet, Today (7:30 pm), Saturday (7:30 pm), Sunday (2:00 pm)
  • Swimming, tomorrow (Saturday), 10:00 am.
  • Typhoon Halyan Relief benefit show, Sunday, November 24th from 7-9pm in Harris. (If the entry fee is a burden, let me know and I'll give you the money.)
  • "Data Sovereignty: The Challenge of Geolocating Data in the Cloud", November 25, 4:15 JRC 101
  • "Gold Fever" by Andrew Sherburne '01 or so, 7:00 p.m., Monday, November 25, ARH 302
  • Tuesday, November 26, 4:15 p.m., JRC 209 a gaming event with the game [d0x3d!]

Tree Traversal

• Once we've built a tree, we may want to systematically visit the nodes in the tree. We call that tree traversal.
• There are a number of decisions to make as we design a traversal algorithms.
• If we assume that the children/subtrees are ordered, do we visit them left-to-right or right-to-left? (Yes, there are reasons to do both.)
• Do we delve deeply into a subtree before we go across the tree (depth-first) or do we go across each level of the tree (breadth-first)?
• If we are doing a depth-first traversal, do we visit a node before (preorder), between (inorder), or after (postorder) its children?
  • Why after? If we are computing a value based on the children, we need to have the children finished.
• If we are doing a breadth-first traversal, do we go top-down or bottom-up?
• And how do we implement all of these, anyway?
  • That's the subject of today's lab.

Lab