Thursday, August 31, 2006

Binary Trees

Topics

• Intuitive definitions of terms: recursive definition of tree, subtree, node, root, leaf, interior node, parent, child, binary tree, complete binary tree, height balanced binary tree
• Vector implementation of a binary tree
• Pointer implementation, using dynamic memory, of any type of tree
• Pre-order, post-order, in-order traversal of a binary tree
• Threaded trees and stackless depth first traversal
• Level-order transversal of trees, using a Queue
• Traversal through tree transformation

Example Code

• Simple StringTree class.
• No insert implemented yet.
• Brute force construction of the tree in main()
• Only has a recursive print of the tree 
• file    file    file    file  

Readings

Chapter 6, Sections 6.1 through 6.4.  Chapter 6.1's definition of a tree is not very good.  We will give a better definition of a tree when we cover graphs later in the course.  You may skip the math in Section 6.3.