Lecture 7.
Binary Trees are ubiquitous in the design
and analysis of computer algorithms. We began our study of this important data
structure with a recursive definition of a binary tree. This recursive
definition naturally leads to various different recursive procedures that we
covered today. That is, to compute the Depth of a node, Height of a node, or
traverse a binary tree.
On
Wednesday we will continue on this topic. I plan to cover a non-recursive
version of the depth first traversals that we saw today, using a stack. The
purpose of this exercise is not intended to be an example of how to write a tree
traversal routine, but rather it is to be viewed as expository. Hopefully the
slightly messy explicit push and pop stack sequence will help your understanding
of the succinct recursive methods.
Posted: Mon - January 24, 2005 at 04:57 PM