Overview

• Preliminaries.
  • Admin.
  • Questions on the exam.
• Orders for traversing the tree.
• Implementating traversal algorithms.

Preliminaries

Admin

• Congrats to DG for being athelete of the (some time period).
• 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)
  • Collegium, 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!]

Questions on the Exam

Can you give us a different iterator for problem 1?

Done.

Do we need to explicitly free nodes?

No.

Did you really accidentally post the solution to problem 2?

Yes. Spend at least thirty minutes on it. Then look at my solution.
Then do something else interesting with the higher-order procedures. (That is, show interesting examples of their use.)

Suppose we put the elements in a binary tree into an array ...

• Order of arrayness: Left-to-right, across each level, pretending all are there.
• Given a node at position p, where are it's children and where is its parent?
  • Left child: p*2 + 1
  • Right child: (p+1) * 2
  • Parent: floor((p-1)/2)

Orders for traversing the tree

• Decision point one: Across or down
  • Across: Breadth-first
  • Down: Depth-first
• Decision choice two: Left-right or right-left
• Decision choice three (depth-first):
  • Preorder (prefix): Print/Process node before subtrees
  • Inorder (infix): Print/Process node between subrees
  • Postorder (postfix): Print/process node after subtrees

• Decision choicd three (breadth-first)

  • Top-down
  • Bottom-up

    Implementating traversal algorithms

• That's right: Lab