Algorithms and OOD (CSC 207 2014F) : Outlines

Outline 44: Tree Traversal

Held: Wednesday, 19 November 2014

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

Overview

• Orders for traversing the tree.
• Implementating traversal algorithms.

• Continue lab partners.

Upcoming Work

• Homework: Phase 1 of project (Class design, Algorithm design, I/O subsystem) due tonight.
• No reading for Friday. We're doing another design exercise.

Extra Credit

• CS Extras Thursday: Text Recognition in Maps
• CS Table Friday: ShellShock
• Learning from Alums, next Tuesday: Alex Cohn '11 (in person)
• CS Extras next Tuesday: Summer Opportunities in CS

Peer Support

• Ajuna's Radio show Mondays at 8pm. Listen to African music.
• Charlie's Friday Night "War in Animated Film" ExCo.
• Copehagen, 7:30 p.m. on the 20th, 21st, 22nd, afternoon 23rd

Miscellaneous

• VP Student Affairs Candidate Open Sessions
• Wednesday, 4:15, JRC 209
• Friday next, 4:15, JRC 209

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.