Previous Section
 < Free Open Study > 
Next Section

8.4 Implementation Level

We develop the algorithms for the operations specified for the Binary Search Tree ADT and represent the tree as a linked structure whose nodes are allocated dynamically. Because the binary search tree is inherently a recursive structure, we first implement the algorithms using recursive solutions. We then take the InsertItem and DeleteItem functions and show how they can be implemented iteratively. Here is the first approximation for the class TreeType. If we need more data members, we can add them at a later time.

As with our first brush with linked lists, we choose not to make the class generic. Let's make this implementation be a tree of char values. You are asked to convert the class into a template class in the exercises.

#include <iostream>

struct TreeNode;

typedef char ItemType;
// Assumption: ItemType is a type for which the operators "<"
//  and "==" are defined--either an appropriate built-in type or
//  a class that overloads these operators.


class TreeType
  TreeType();                     // Constructor.
  ~TreeType();                    // Destructor.
  TreeType(const TreeType& originalTree);  // Copy constructor.
  void operator=(TreeType& originalTree);
  void MakeEmpty();
  bool IsEmpty() const;
  bool IsFull() const;
  int LengthIs() const;
  void RetrieveItem(ItemType& item, bool& found) const;
  void InsertItem(ItemType item);
  void DeleteItem(ItemType item);
  void ResetTree(OrderType order);
  void GetNextItem(ItemType& item, OrderType order,
       bool& finished);
  void Print(std::ofstream& outFile) const;
  TreeNode* root;

Before we go on, we need to decide just what a node in the tree will look like. In our discussion of trees, we talked about right and left children. These structural pointers hold the tree together. We also need a place to store the user's data in the node, which we'll continue to call info. Figure 8.4 shows a picture of a node.

Click To expand
Figure 8.4: Node terminology for a tree node

Here is the definition of TreeNode that corresponds with the picture in Figure 8.4:

struct TreeNode
  ItemType info;
  TreeNode* left;
  TreeNode* right;

Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)