CSC 2200 

Fall 2002


Up

Lab preparation (at home)

Goal

Implement the Binary Search Tree data structure. Use structure BinNode and class BinTree for your implementation.

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

  BinNode(const char* s);
  ~BinNode();

  void setKey(const char* s);
};

BinNode is used to implement a node of the BST tree. Data member key is used to record the key value in the node. The key is a C++ null-terminated string. That means you have to implement a BST on strings. Data members left and right are pointers to the left subtree and the right subtree, respectively. If the pointer is NULL, the corresponding subtree is empty. The constructor creates a new node, sets key to s, and sets left and right to NULL. The destructor has to correctly deallocate all used memory. The member function setKey is used to set a new value into the data member key.

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

  void insertKey(const char* s);
  bool containsKey(const char *s) const;
  void printTree() const;

private:
  BinNode* root;
};
 

BinTree encapsulates the Binary Search Tree ADT. The constructor creates the empty tree. The destructor must correctly deallocate all used memory. Member function insertKey inserts a new value into the tree (duplicates are not allowed). Function containsKey returns true if s is found in the tree and false otherwise. Function printTree prints the entire tree on the screen. You have to make sure that from the printout you can tell (and draw) the actual structure of the tree.

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.