Linked List Implementation of Binary Tree

#include < fstream.h >
#include < iostream.h >
#include < stdlib.h >
#include < stdio.h >

/***--------------------------------------------------------------------***/
/***  In this example we will be interested in storing integer objects  ***/
/***--------------------------------------------------------------------***/
class BigInt
{
public:
   BigInt(int x) { number = x; }
   int value() { return number; }
   void display() { cout << number << " "; }
private:
   int number;
};

/***--------------------------------------------------------------------***/
/***  This is the function used to display the value of BigInt objects  ***/
/***--------------------------------------------------------------------***/
void intdisplay(void *t) { ((BigInt *)(t))->display(); }

/***--------------------------------------------------------------------***/
/***   This is the function used to return an object value for BigInt   ***/
/***--------------------------------------------------------------------***/
int valuefunc(void *t)   { return ((BigInt *)(t))->value(); }

/***--------------------------------------------------------------------***/
/***   The Cell class is used to "carry" the objects in the HeapSort    ***/
/***--------------------------------------------------------------------***/
class Cell
{
friend class BinTree;
public:
   Cell(void *data, Cell *ln, Cell *prnt)
   {
      item     = data;
      lefttree = NULL;
      rghttree = NULL;
      leftnext = ln;
      rghtnext = NULL;
      parent   = prnt;
   }
   void *objectOf()     { return item; }
   Cell *parentOf()     { return parent; }
   Cell *leftChildOf()  { return lefttree; }
   Cell *rightChildOf() { return rghttree; }
   Cell *leftNextOf()   { return leftnext; }
   Cell *rightNextOf()  { return rghtnext; }
   void  setLeftChild(Cell *t)  { lefttree = t; }
   void  setRightChild(Cell *t) { rghttree = t; }
   void  setLeftNext(Cell *t)   { leftnext = t; }
   void  setRightNext(Cell *t)  { rghtnext = t; }
   void  setObject(void *t)     { item = t; }
private:
   void *item;
   Cell *leftnext;
   Cell *rghtnext;
   Cell *lefttree;
   Cell *rghttree;
   Cell *parent;
};

/***--------------------------------------------------------------------***/
/***  The class of Binary Trees -                                       ***/
/***    includes the following methods, among others                    ***/
/***       1. HeapifyDown - percolate an object down from the root      ***/
/***       2. HeapifyUp   - percolate an object up from a leaf          ***/
/***       3. popNode     - delete the last Cell and return its object  ***/
/***       4. setRoot     - replace an object at the root with another  ***/
/***       5. HeapSort    - repeat: setRoot(popNode()); heapifyDown();  ***/
/***       6. addNodeToHeap - add a Cell to end of heap and add object  ***/
/***    saves information in the following variables                    ***/
/***       1. dispfn      - pointer to function that displays the tree  ***/
/***       2. valfn       - pointer to function returning value of obj  ***/
/***       3. head, tail  - pointers locating root and end of tree      ***/
/***    tail pointer -                                                  ***/
/***       1. points to a leaf Cell if the tree has an odd number of    ***/
/***          Cells.  It either points to the leftmost childless Cell   ***/
/***          in the row that is one up from the bottom, or, in the     ***/
/***          case of a full tree, it points to the leftmost Cell of    ***/
/***          the bottom level (latter case covers the one-Cell case).  ***/
/***       2. points to the rightmost Cell, one level up from the       ***/
/***          bottom, that has a child.                                 ***/
/***--------------------------------------------------------------------***/
class BinTree
{
public:
   BinTree() { dispfn = intdisplay; valfn = valuefunc; head = tail = NULL;  }
   void  addNode(void *t);
   void *getRoot();
   void *popNode();
   void  heapifyDown();
   void  heapifyUp();
   void  putRoot(void *t);
   void  addNodeToHeap(void *t);
   void  display();
   void  displayRoot() { cout << (valfn)(head->objectOf()) << " "; }
   int   empty()   {  return head == NULL;  }
private:
   Cell *head;
   Cell *tail;
   void (* dispfn)(void *);
   int  (* valfn)(void *);
};

/***--------------------------------------------------------------------***/
/***  Heapify Down -                                                    ***/
/***     let t be a Cell with an object                                 ***/
/***     let h be the child Cell of t with object of least value        ***/
/***     if no such child Cell exists, stop                             ***/
/***     otherwise, if t's object value > h's object value              ***/
/***     then swap t's object with h's object, set t = h, and repeat    ***/
/***--------------------------------------------------------------------***/
void BinTree::heapifyDown()
{
   Cell *t = head, *h;
   void *obj;

   if (head == NULL) return;

   while (1)
   {
      if (t->leftChildOf() == NULL && t->rightChildOf() == NULL)
         break;
      else
      if (t->rightChildOf() == NULL)
         h = t->leftChildOf();
      else
      if ((valfn)(t->leftChildOf()->objectOf())
              < (valfn)(t->rightChildOf()->objectOf()))
         h = t->leftChildOf();
      else
         h = t->rightChildOf();

      if ((valfn)(h->objectOf()) < (valfn)(t->objectOf()))
      {
         obj = t->objectOf();
         t->setObject(h->objectOf());
         h->setObject(obj);
         t = h;
      }
      else
         break;
   }
}

/***--------------------------------------------------------------------***/
/***  Heapify Up -                                                      ***/
/***     let h be the last Cell of the tree                             ***/
/***     if no such Cell exists, stop                                   ***/
/***     otherwise, if h's object value < h's parent's object value     ***/
/***     then swap h's object with h's parent's object,                 ***/
/***     set h = h's parent,                                            ***/
/***     and repeat                                                     ***/
/***--------------------------------------------------------------------***/
void BinTree::heapifyUp()
{
   Cell *h;
   void *obj;

   if (head == NULL || (head == tail && tail->leftChildOf() == NULL)) return;
   if (tail->rightChildOf() == NULL && tail->leftChildOf() == NULL)
      h = tail->leftNextOf()->rightChildOf();
   else
      h = tail->leftChildOf();

   while (1)
   {
      if (h == head) break;
      if ((valfn)(h->objectOf()) < (valfn)(h->parentOf()->objectOf()))
      {
         obj = h->objectOf();
         h->setObject(h->parentOf()->objectOf());
         h->parentOf()->setObject(obj);
         h = h->parentOf();
      }
      else
         break;
   }
}

/***--------------------------------------------------------------------***/
/***                   Basic function for building a heap               ***/
/***--------------------------------------------------------------------***/
void BinTree::addNodeToHeap(void *t)
{
   addNode(t);
   heapifyUp();
}

void *BinTree::getRoot()
{
   void *t = head->objectOf();
   head->setObject(NULL);
   return t;
}

void BinTree::putRoot(void *t)
{
   if (t == NULL) return;
   if (head == NULL) return;
   head->setObject(t);
}

/***--------------------------------------------------------------------***/
/***  Add a Cell to the end of a heap and insert an object in that Cell ***/
/***--------------------------------------------------------------------***/
void BinTree::addNode(void *t)
{
   if (t == NULL) return;
   if (head == NULL)
      head = tail = new Cell(t, NULL, NULL);
   else
   if (tail->leftChildOf() == NULL)
   {
      if (tail->leftNextOf() == NULL)
      {
         tail->setLeftChild(new Cell(t, tail, tail));
         tail->setRightNext(tail->leftChildOf());
      }
      else
      {
         Cell *last = tail->leftNextOf()->rightChildOf();
         tail->setLeftChild(new Cell(t, last, tail));
         last->setRightNext(tail->leftChildOf());
      }
   }
   else
   {
      Cell *last = tail->leftChildOf();
      tail->setRightChild(new Cell(t, last, tail));
      last->setRightNext(tail->rightChildOf());
      tail = tail->rightNextOf();
   }
}

/***--------------------------------------------------------------------***/
/***       Remove the last Cell from a tree and return its object       ***/
/***--------------------------------------------------------------------***/
void *BinTree::popNode()
{
   if (head == NULL) return NULL;
   if (tail->leftNextOf() == NULL && tail->leftChildOf() == NULL)
   {
      void *t = head->objectOf();
      delete head;
      head = tail = NULL;
      return t;
   }
   else
   if (tail->leftChildOf() != NULL)
   {
      void *t = tail->leftChildOf()->objectOf();
      tail->leftChildOf()->leftNextOf()->setRightNext(NULL);
      delete tail->leftChildOf();
      tail->setLeftChild(NULL);
      return t;
   }
   else
   {
      tail = tail->leftNextOf();
      void *t = tail->rightChildOf()->objectOf();
      tail->leftChildOf()->setRightNext(NULL);
      delete tail->rightChildOf();
      tail->setRightChild(NULL);
      return t;
   }
}

void BinTree::display()
{
   Cell *t;
   if (head == NULL) { cout << "(empty)\n";  return; }
   for (t = head ; t != NULL ; t = t->rightNextOf())
      (dispfn)(t->objectOf());
   cout << "\n";
}

/***--------------------------------------------------------------------***/
/***   Perform the heapsort on a binary tree T that is assumed a heap   ***/
/***--------------------------------------------------------------------***/
void heapSort(BinTree *T)
{
   while (!T->empty())
   {
      T->displayRoot();
      T->putRoot(T->popNode());
      T->heapifyDown();
   }
}

/***--------------------------------------------------------------------***/
/***                      Test of the above functions                   ***/
/***--------------------------------------------------------------------***/
void main()
{
   BinTree *T = new BinTree();

   for (int i=29 ; i > 0 ; i--) T->addNodeToHeap(new BigInt(i));
   T->display();
   printf("******\n");
   heapSort(T);
   cout << "\n";
}