CSC 2200 

Fall 2002


Up

Lab preparation (at home)

Goal

Implement the following modifications to Lab #6. The key type for this BST implementation is an integer. Traversal functions and deleteKey function will be added as member functions to the BinTree class.

struct BinNode {
  int key;
  BinNode* left;
  BinNode* right;

  BinNode(int n);
};

The specification of BinNode is the same as in Lab #6, but the key is an integer.

class BinTree {
public:
  BinTree();
  ~BinTree();

  void insertKey(int n);
  bool containsKey(int n) const;
  void deleteKey(int n);

  void printTree() const;

  void preorderTrasversal() const;
  void inorderTrasversal() const;
  void postorderTrasversal() const;

private:
  BinNode* root;
};

The preorderTraversal function should check if the tree is not empty. Then it starts traversing the tree from the root using preorder traversal. When a node is visited, the value stored in key is printed on the screen.

The inorderTraversal function should check if the tree is not empty. Then it starts traversing the tree from the root using inorder traversal. When a node is visited, the value stored in key is printed on the screen.

The postorderTraversal function should check if the tree is not empty. Then it starts traversing the tree from the root using postorder traversal. When a node is visited, the value stored in key is printed on the screen.

The deleteKey function should search for the node with key equal to n. If the node is found, it is removed from the tree. The BST property of the tree must be preserved.

If needed, you may add auxiliary private member functions.

Lab report

Finish the implementation and test it.

For problems or questions regarding this web contact besta@cs.wayne.edu.
Last updated: September 09, 2002.