Computer Science 501
Data Structures and Algorithm Analysis
Fall 2014, The College of Saint Rose
Lecture 10: Trees; Priority Queues
Date: Tuesday, November 11, 2014
Agenda
- Announcements
- Lab work: never need to make a copy of the structure package! Use the jar file.
- Lab 9: BestOf [HTML] [PDF] lecture assignment portion recap
- Lab 8: P.S.: It's Just a Stack [HTML] [PDF] program recap
- Trees
- 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
- Priority queues
- Vector-based implementation
- heaps
- heap-based priority queue
- Lab 10: Trees [HTML] [PDF] out (no programming!)
Readings and References
Terminology
- 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
- balanced tree
- priority queue
- heap/min-heap/max-heap
Examples
- BinaryExpressionTree
- BTTraversals