Tutorial: Doubly Linked Binary Tree

Hello Coders!

I want introduce you my Version of Doubly Linked Binary Tree in C++. It is nothing fancy but it can help some Newbies with getting the idea. When you are new to Binary Trees in general, this Tutorial might not help you. Fortunatly, there are a lot of tutorials in the Web.
The Doubly Linked Binary Tree is a small widening of the usual Binary Tree. The only thing that its different is that it has also a previous / parent pointer. The beauty of the whole thing is that now some special operations can be implemented easier for example finding the predecessor/successor of a current node.

Picture of a doubly linked binary tree, every node point at its previous node but the previous pointer of the root node points at NULL

Here a short code-example to get started:

  1: #include <utility>
  2: 
  3: class DoublyLinkedBinaryTree{
  4:  public:
  5:   DoublyLinkedBinaryTree();
  6:   ~DoublyLinkedBinaryTree();
  7:   typedef char valueType;
  8:  private:
  9:   class nodeType {
 10:   public:
 11:    nodeType();
 12:    nodeType(valueType const & data, nodeType * prev);
 13:    ~nodeType();
 14:    valueType  data;
 15:    nodeType * pLeft;
 16:    nodeType * pRight;
 17:    nodeType * pPrev;
 18:   };
 19:   nodeType * pRoot;
 20:  public:
 21:   void insert(valueType & data);
 22:  private:
 23:   void clear();
 24:   void clear(nodeType * pRoot);
 25:   void insert(valueType & data,nodeType * pRoot, nodeType * pPrev = NULL);
 26: };
 27: 
 28: DoublyLinkedBinaryTree::DoublyLinkedBinaryTree(){
 29:  pRoot = 0;
 30: }
 31: 
 32: DoublyLinkedBinaryTree::~DoublyLinkedBinaryTree(){
 33:  clear();
 34: }
 35: 
 36: DoublyLinkedBinaryTree::nodeType::nodeType(valueType const & data, nodeType * prev){
 37:  this->data = data;
 38:  this->pLeft = NULL;
 39:  this->pRight = NULL;
 40:  this->pPrev = prev;
 41: }
 42: 
 43: void DoublyLinkedBinaryTree::insert(DoublyLinkedBinaryTree::valueType & data){
 44:  insert(data, pRoot); 
 45: }
 46: 
 47: void DoublyLinkedBinaryTree::insert(DoublyLinkedBinaryTree::valueType & data, DoublyLinkedBinaryTree::nodeType * pHead, DoublyLinkedBinaryTree::nodeType * pPrev){
 48:  if (!pHead){
 49:   pHead = new nodeType(data, pPrev);
 50:  }else{
 51:   //if the value exits already it does not insert it again
 52:   if(data == pHead->data){
 53:    return;
 54:   }else{
 55:    if(data < pHead->data){ 
 56:     insert(data, pHead->pLeft, pHead);
 57:    }
 58:    else {
 59:     insert(data, pHead->pRight, pHead);
 60:    }
 61:   }
 62:  }
 63: }
 64: 
 65: void DoublyLinkedBinaryTree::clear(){
 66:  clear(pRoot);
 67: }
 68: 
 69: void DoublyLinkedBinaryTree::clear(nodeType * pHead){
 70:  if (pHead != NULL) {
 71:   clear (pHead->pLeft);
 72:   clear (pHead->pRight);
 73:   delete (pHead);
 74:  }
 75: }
 76: 
 77: DoublyLinkedBinaryTree::nodeType::~nodeType(){
 78: }
 79: 
 80: void main(){
 81:  DoublyLinkedBinaryTree tree;
 82:  DoublyLinkedBinaryTree::valueType data('X');
 83:  DoublyLinkedBinaryTree::valueType data2('Y');
 84:  tree.insert(data);
 85:  tree.insert(data2);
 86: }

Hope it was helpful for you, for any questions feel free to leave a comment!