Binary Search Tree C++

Question

Im a little confused. Im wondering if an array based Binary Search tree is implemented this way?

void BST::insert(item &items, const data & aData )
{//helper function.
    Parent++;
    data *new_data = new data(aData);
    this->insert(*new_data);
}

// insert a new item into the BST
void BST::insert(const data &aData )
{
    if ( items[Parent].empty ) 
    {
        items[Parent].theData = aData;
        items[Parent].empty = false;
    }
    else if ( aData < items[Parent].theData )
    {
              if ( Parent >= maxSize ) this->reallocate();
              this->insert(items[2*Parent+1], aData);
    }
    else
    {
           this->insert(items[2*Parent+2], aData);
    }
}

// ctor where i make my intiailizations.

BST::BST(int capacity) : items(new item[capacity]), 
Parent(0), leftChild(0), rightChild(0), maxSize(capacity)
{
}

Answer 1

I'm not sure a binary tree based on an array is the best idea, as it:

1. prevents node-balancing (optimizing lookups for unbalanced trees)
2. wastes space - tons of it, especially if the tree is unbalanced.

Having said that, it is a valid approach, with a minor change: Change

if ( Parent >= maxSize ) this->reallocate();

to

if ( 2*Parent >= maxSize ) this->reallocate();

Answer 2

This is fairly old but I wrote this in my second year of college which was about 8 years ago :). It may help you out in some way or another...

//JHermiz
//Implementation File with def's
//tree.h

#include<stdlib.h>
#include"xcept.h"  //file for exceptions that may be thrown

//BinaryTreeNode class
template<class T>
class BinaryTreeNode {
                 public:
                            BinaryTreeNode() {LeftChild=RightChild=NULL;}
                            BinaryTreeNode(const T&e)
                              {
                                data=e;
                                LeftChild=RightChild=NULL;
                              }
                            BinaryTreeNode(const T&e, BinaryTreeNode *l,
                                                BinaryTreeNode *r)
                              {
                                 data=e;
                                 LeftChild=l;
                                 RightChild=r;
                              }

                            BinaryTreeNode<T> *LeftChild;    //left subtree
                            BinaryTreeNode<T> *RightChild;   //right subtree
                            T data;
                            };

//BinaryTree Class
template<class T>
class BinaryTree{
             public:
                      BinaryTree(){root=NULL;}

                      ~BinaryTree(){Delete();}

                      void Delete(){PostOrder(Free, root); root=0;}

                      static void Free(BinaryTreeNode<T>* t){delete t;}

                      int IsEmpty()const
                        {return ((root) ? 0 : 1);}

                      int Root(T& x)const;

                      void MakeTree(const T& element, BinaryTree<T>& left,
                                         BinaryTree<T>& right);

                      void BreakTree(T& element, BinaryTree<T>& left,
                                          BinaryTree<T>& right);

                      void PreOrder(void(*Visit)(BinaryTreeNode<T> *u))
                            {PreOrder(Visit, root);}

                      void InOrder(void(*Visit)(BinaryTreeNode<T> *u))
                            {InOrder(Visit, root);}

                      void PostOrder(void(*Visit)(BinaryTreeNode<T> *u))
                            {PostOrder(Visit, root);}

                      BinaryTreeNode<T>* root;  //root pointer

                    //traversal methods
                      void PreOrder(void(*Visit)
                          (BinaryTreeNode<T> *u), BinaryTreeNode<T> *t);

                      void InOrder(void(*Visit)
                          (BinaryTreeNode<T> *u), BinaryTreeNode<T> *t);

                      void PostOrder(void(*Visit)
                          (BinaryTreeNode<T> *u), BinaryTreeNode<T> *t);

                      static void Output(BinaryTreeNode<T> *t)
                             {
                              cout << t->data << " ";
                             }

                      void PreOutput()
                        {
                          PreOrder(Output, root);
                          cout << endl;
                        }

                      void InOutput()
                         {
                          InOrder(Output, root);
                          cout << endl;
                         }

                      void PostOutput()
                         {
                          PostOrder(Output, root);
                          cout << endl;
                         }
                     };

//base class is BinaryTree - BSTree is the derived class
template<class E, class K>
class BSTree : public BinaryTree<E>{
         public:
                    int Search(const K& k, E& e)const;
                    BSTree<E,K>& Insert(const E& e);
                    BSTree<E,K>& Delete(const K& k, E& e);
                    //stores the maximum element of the tree in e
                    void MaxNode(E& e)const;
         };


/*---------------------BinaryTree Methods()-------------------------*/
template<class T>
int BinaryTree<T>::Root(T& x) const
  { //Set x to root->data
    //return false if no root
    if(root)
      {
        x=root->data;
        return 1;
      }
    else return 0;  //no root
  }

template<class T>
void BinaryTree<T>::MakeTree(const T& element,
                      BinaryTree<T>& left, BinaryTree<T>& right)
  {//Combine left, right, and element to make new tree.
    //left, right, and this must be different trees.
    //create combined tree

    root=new BinaryTreeNode<T>(element, left.root, right.root);

    //deny access from trees left and right
    left.root=right.root=0;
  }

template<class T>
void BinaryTree<T>::BreakTree(T& element,
                        BinaryTree<T>& left, BinaryTree<T>& right)
  {//left, right, and this must be of different trees.
    //check if empty

    if(!root)  //empty tree
      throw BadInput();

    //break the tree
    element=root->data;
    left.root=root->LeftChild;
    right.root=root->RightChild;

    delete root;
    root=0;
  }

template<class T>
void BinaryTree<T>::PreOrder(void(*Visit)
                        (BinaryTreeNode<T>* u), BinaryTreeNode<T>* t)
  {//preorder traversal

     if(t)
      {
        Visit(t);
        PreOrder(Visit, t->LeftChild);
        PreOrder(Visit, t->RightChild);
      }
  }

template<class T>
void BinaryTree<T>::InOrder(void(*Visit)(BinaryTreeNode<T>* u),
                                     BinaryTreeNode<T>* t)
  {//inorder traversal

      if(t)
         {
          InOrder(Visit, t->LeftChild);
          Visit(t);
          InOrder(Visit, t->RightChild);
         }
  }

template<class T>
void BinaryTree<T>::PostOrder(void(*Visit)(BinaryTreeNode<T>* u),
                                        BinaryTreeNode<T>* t)
  {//postorder traversal

     if(t)
      {
        PostOrder(Visit, t->LeftChild);
        PostOrder(Visit, t->RightChild);
        Visit(t);
      }
  }
/*----------------------End of BinaryTree Methods()------------------*/

/*------------------------BSTree Methods()---------------------------*/

template<class E, class K>
int BSTree<E,K>::Search(const K& k, E& e) const
 {//Search for element that matches k.
    //Pointer p starts at the root and moves through
    //the tree looking for an element with key k.

    BinaryTreeNode<E> *p=root;

     while(p) //examine p if >, <, or ==
      {
        if(k<p->data)
          p=p->LeftChild;
        else if(k>p->data)
          p=p->RightChild;
        else{ //element is found
              e=p->data;
              return 1;
             }
      }
     return 0;
  }

template<class E, class K>
BSTree<E,K>& BSTree<E,K>::Insert(const E& e)
 { //Insert e if not duplicate

  BinaryTreeNode<E> *p=NULL;   //search pointer
  BinaryTreeNode<E> *pp=NULL;     //parent of p

  //find place to insert throw BadInput if a duplicate element
  p=root;       //p is now the root

  while(p)
    {
     pp=p;
     //move p to a child depending if p is > or <

     if(e<p->data)
      p=p->LeftChild;

     else if(e>p->data)
      p=p->RightChild;

     else
      throw BadInput(); //a duplicate element
     }

    //Get a node (memory) for e and attach to pp
    BinaryTreeNode<E> *r=new BinaryTreeNode<E>(e);

     if(root)
      {//tree not empty

        if(e<pp->data)
         pp->LeftChild=r;

        else if(e>pp->data)
         pp->RightChild=r;
      }

     else //we need a root first!
        root=r;

    return *this;
  }

template<class E, class K>
BSTree<E,K>& BSTree<E,K>:: Delete(const K& k, E& e)
 {//Delete element with key k and put it in e.
  //set p to point to node with key k

  BinaryTreeNode<E> *p=NULL;  //a search pointer
  BinaryTreeNode<E> *pp=NULL;  //parent of p

  p=root;

  while(p && p->data != k)
    {//move to a child of p

     pp=p;

      if(k < p->data)
        p=p->LeftChild;

      else
        p=p->RightChild;
    }

  if(!p)               //no element with key k
    throw NoElement();

  e=p->data;    //save element to delete

  //restructure the tree so it remains a BSTree
    if(p->LeftChild && p->RightChild) //handle the node with 2 children if any
      {//convert it to point to NULL or one child case
        //find largest element in left subtree of p

        BinaryTreeNode<E> *s=p->LeftChild;
        BinaryTreeNode<E> *ps=p;  //parent of s which is actually p

        while(s->RightChild)
         {//move to the larger element
          ps=s;
          s=s->RightChild;
         }//end while

        //move largest from s to p
        p->data=s->data;
        p=s;
        pp=ps;
      }//end all if

    //p only had one child
    //save child pointer in c
    BinaryTreeNode<E> *c;

    if(p->LeftChild)
     c=p->LeftChild;

    else
     c=p->RightChild;
    //delete p

    if(p==root)
      root=c;

    else{
          //is p left or right child of pp?
             if(p==pp->LeftChild)
              pp->LeftChild=c;

             else
              pp->RightChild=c;
         }//end else
    delete p;
    return *this;
 }

template<class E, class K>
void BSTree<E,K>::MaxNode(E &e)const
 {//function returns max. value of tree (rightmost value)

  BinaryTreeNode<E>* p=NULL;  //root node
  BinaryTreeNode<E>* pp=NULL; //parent of p

  p=root;

  while(p)
    {
     pp=p;
     p=p->RightChild;
    }
     //p points to NULL, pp points to node before NULL
 e=pp->data; //max. value stored
 }

char Menu()
 {
  char choice;

  //a menu
  cout << "\n\t\tBST TREE MENU\n";
  cout << "\t********************************\n";
  cout << "\t* 1)Type 1 to insert an element*\n";
  cout << "\t* 2)Type 2 to delete an element*\n";
  cout << "\t* 3)Type 3 to output pre-order *\n";
  cout << "\t* 4)Type 4 to output in-order  *\n";
  cout << "\t* 5)Type 5 to output post-order*\n";
  cout << "\t* 6)Type 6 for maximum element *\n";
  cout << "\t* 7)Type 7 to output root      *\n";
  cout << "\t* 8)Type 8 to search for a #   *\n";
  cout << "\t* 9)Type 9 to exit program.    *\n";
  cout << "\t********************************\n";

  cout << "Input your choice: ";
  cin >> choice;

  while(choice!='1' && choice!='2' && choice!='3'
          && choice!='4' && choice!='5' && choice!='6' 
          && choice!='7' && choice!='8' && choice!='9')
         {//user typed in wrong key
            cout << "\nType choice as 1-9: ";
            cin >> choice;
         }
  return choice;
 }