Lecture 8.
We continued to see some other
combinatorial properties of binary trees today. Then, we moved onto two
different implementations of binary trees: as linked structures using
pointers and as an array. We found that the implementation using arrays is very
convenient when the tree is complete (or near-complete) but wastes too much
memory when the tree is a
path.
A
C++ declaration of a binary tree class was proposed. This declaration was based
on pointers and followed the recursive definition of a binary tree. We
implemented the method preorder, as an example of depth first
search, in a recursive way. Then we sketched how a breadth first search
(traversal by levels) would operate using a queue. We left open the questions of
how to implement depth first search (preorder, inorder, and postorder
traversals) using a
stack.
Posted: Wed - January 24, 2007 at 02:08 PM