- 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 are bigger. - 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

- To print a tree in (left-to-right)
- 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.

Stephan Schulz,schulz@cs.miami.edu, Thu Aug 22 13:35:31 EDT 2002