Computer Science 501
Data Structures and Algorithm Analysis

Fall 2015, The College of Saint Rose

Home     Syllabus     Schedule     Style Guide

Agenda

• Announcements
• Lab 7: The Two Towers Problem [HTML] [PDF] recap; empirical studies due now
• Lab 8: P.S.: It's Just a Stack [HTML] [PDF] due Friday night
• Ordered structures
  • ComparableAssociations
  • the OrderedStructure interface (it's empty!)
  • OrderedVector
  • OrderedList
• Lab 9: Best Of [HTML] [PDF] out, due back on a regular schedule next Wednesday
• Trees
  • motivation
  • terminology
• Binary Trees
• Tree Traversals
  • preorder, in-order, postorder and level-order
  • recursive implementation
  • implementations as Iterators
• Binary tree example: Huffman trees
• Array representation of trees

Readings and References

• Bailey Ch. 12

Terminology

• encapsulate
• trees
• expression tree
• complete tree/full tree
• node, root node
• subtree
• edge
• child node
• leaf node
• interior node
• parent node
• forest
• sibling, ancestor, descendant
• simple path
• path length
• node/tree height
• node depth
• node degree
• level
• binary trees
• left/right subtrees
• tree traversals: preorder, in-order, postorder, level-order
• greedy algorithm
• coding
• fixed-length encoding/variable-length encoding
• prefix-free coding
• Huffman coding

Examples

• BinaryExpressionTree
• BTTraversals