This assignment enters with 3% into the total grade!
- A binary search tree is either empty, or it consist of a
node storing a key (the root of the tree), and a left
and right subtree, such that all keys in the left subtree are
smaller than the key in the node, and all keys in the right subtree
- Trees can be traversed in different order:
- To print a tree in (left-to-right) preorder, you first
print the root, then the left subtree, then the right subtree
- To print a tree in (left-to-right) postorder, you first
print the left subtree, then the right subtree, then the root
- To print a tree in natural order, you first print the
left tree, then the root, then the right tree
- Design a data structure for binary search trees with
int keys, using dynamic memory handling.
- Implement functions to:
- Insert keys into the tree (ignoring keys already in the tree)
- Print a tree in preorder, natural order, and postorder
- Free the memory taken up by the tree
- Use this datatype and the functions from integerio to
write a program that reads a list of integers from stdin
into a tree, and prints that tree in the three different orders.
- You can use the code from the linear list example as a base. The
complete code will be available from the course homepage.
Schulz,firstname.lastname@example.org, Thu Aug 22 13:35:31 EDT 2002