Traversing a Binary Search Tree

[CS Student]

I am working on this binary search tree, and I am having trouble understanding/coding how I can use the iterator class my partner and I made. begin() is supposed to return an iterator to the first element in the list (the left-most element) and end() is supposed to go to the end-most + 1. Its the opposite with rbegin() and rend() where rbegin is the right-most element and rend is the left-most + 1.

I think I need to use recursion in some of these methods dealing with the iterator somewhere, or a loop, but I'm not exactly sure how. Can anyone help me?

/*********************************
 * Binary Search Tree
 *********************************/

#ifndef BST_H
#define BST_H

#include "bnode.h"  // We're using the Binary Node class too!

// Forward declaration of BinaryNode
template <class T>
class BinaryNode;

// forward declaration for BSTIterator
template <class T>
class BSTIterator;

/***************************************
 * Binary Search Tree
 ***************************************/
template <class T>
class BST
{
  public:
   // Default constructor. Sets root to NULL.
  BST() : root() {}

   // Destructor. Delete all elements from the binary tree.
   ~BST() {deleteBinaryTree(root);}

   // empty() determines whether the tree is empty. Test the root node for NULL
   bool empty() {return root == NULL;}

   // insert()
   void insert(const T & data);

   // remove()

   // clear() deletes all items in the binary tree
   void clear(BinaryNode<T> *pHead);

   // find()

   // begin() Left-most node
   BSTIterator<T> begin();

   // end()
   BSTIterator<T> end();

   // rbegin()
   BSTIterator<T> rbegin();

   // rend()
   BSTIterator<T> rend();
  private:
   BinaryNode<T> * root;
 };

/**************************************************
 * BST ITERATOR
 * An iterator through BST
 *************************************************/
template <class T>
class BSTIterator
{
   public:
   // default constructor
   BSTIterator() : bNode(0x00000000) {}

   // 
   BSTIterator(BinaryNode <T> * bNode) : bNode(bNode) {}

   // copy constructor
   BSTIterator(const BSTIterator <T> & rhs) { *this = rhs; }

   // assignment operator
   BSTIterator & operator = (const BSTIterator <T> & rhs)
   {
      this->bNode = rhs.bNode;
      return *this;
   }

   // equals operator
   bool operator == (const BSTIterator & rhs) const
   {
      return rhs.bNode.data == this->bNode->data;
   }

   // not equals operator
   bool operator != (const BSTIterator & rhs) const
   {
      return !(rhs.bNode.data == this->bNode->data);
   }

   // dereference operator
   T & operator * () const
   {
      return bNode->data;
   }

   // prefix increment
   BSTIterator <T> & operator ++ ()
   {


      return *this;
   }

   // postfix increment
   BSTIterator <T> operator ++ (int postfix)
   {
      BSTIterator tmp(*this);



      return tmp;
   }

   // prefix decrement
   BSTIterator <T> & operator -- ()
   {


      return *this;
   }

   // postfix decrement
   BSTIterator <T> operator -- (int postfix)
   {
      BSTIterator tmp(*this);



      return tmp;
   }


  private:
   BinaryNode <T> * bNode;
};

[giblit]

I have never heard of a BST have an iterator to the "begin" and "end."

The easiest way to traverse the BST is to use recursion. There is In-Order, Pre-Order, and Post-Order.

If you need a little bit more information on what the differences are wiki has a pretty good explanation.

http://en.wikipedia.org/wiki/Tree_traversal

Wiki wrote:

Pre-order
Display the data part of root element (or current element).
Traverse the left subtree by recursively calling the pre-order function.
Traverse the right subtree by recursively calling the pre-order function.

In-order (symmetric)
Traverse the left subtree by recursively calling the in-order function.
Display the data part of root element (or current element).
Traverse the right subtree by recursively calling the in-order function.

Post-order
Traverse the left subtree by recursively calling the post-order function.
Traverse the right subtree by recursively calling the post-order function.
Display the data part of root element (or current element).

This basically tells you 100% how to do your recursion too.

Hint: The 3 traversal function bodies will each be 3 lines long. Well..actually they may be a few lines more if you check to see if they are valid so probably about 5 lines long.

[Lowest0ne]

A BST tree could have a typical iterator ( one with ++ and -- ) if each node contained a pointer to its parent. Otherwise a "for_each" function on a BST would take a functor as an argument and recurse into the tree, calling the functor for each node's value.