Homework #8

• Goal: Implementing tree search algorithms on a binary tree with a class.
• Please UPLOAD your homework (ZIP or RAR file) to TA at http://ms11.voip.edu.tw/cs102/
• Deadline: 2008/4/12 11:00 AM
• In computer science, tree-traversal refers to the process of visiting each node in a tree data structure, exactly once. Tree structures can be traversed in many different ways. Starting at the root of a binary tree, there are three main steps that can be performed. These steps are: Performing an action on the current node (referred to as "visiting" the node); or repeating the process with the subtrees rooted at the "left" and "right" children. Thus the process is most easily described through recursion. The order in which the above three steps are performed defines the traversal type.
  1. To traverse a non-empty binary tree in preorder, perform the following operations:
     1. Visit the node.
     2. Traverse the left subtree.
     3. Traverse the right subtree.

     (This is also called Depth-first traversal.)

  2. To traverse a non-empty binary tree in inorder, perform the following operations:
     1. Traverse the left subtree.
     2. Visit the node.
     3. Traverse the right subtree.
  3. To traverse a non-empty binary tree in postorder, perform the following operations:
     1. Traverse the left subtree.
     2. Traverse the right subtree.
     3. Visit the node.
• Consider the following binary tree.

  

  • Preorder traversal sequence: F, B, A, D, C, E, G, I, H
  • Inorder traversal sequence: A, B, C, D, E, F, G, H, I
    • Note that the inorder traversal of this binary search tree yields an ordered list
  • Postorder traversal sequence: A, C, E, D, B, H, I, G, F
• In this homework, you are required to
  1. Define a class Node which has three data members: left, data, right.
  2. Construct the binary with an Init() function, which is a global function (instead of a member function of the class Node).
  3. Define three member functions Inorder(), Preorder(), Postorder(), so that root.Inorder() will print out the inorder traversal sequence, root.Preorder() will print out the preorder traversal sequence, and root.Postorder() will print out the postorder traversal sequence, respsectively.
  4. Bonus: Declare left, data, right as private data members.