Pretty Printing of a Tree Data Structures [AVL tree example]

To debug a tree data structure, one usually constructs a set of test cases and use a pen and a piece of paper to draw and trace the tree data structure content at different steps of operations (insertion, deletion, ...). Everyone who has been doing this knows well that this is a tedious task, especially when the tree is big and data structure operations are complex.

This is why I'm introducing a nice tree printing (visualization) member function for you in C++. The function is generic, and you can easily modify it to work with any other tree data structures. The output from such function is as shown in the two examples below (enlarge the images to see them better; first one is for an AVL tree and second example is for 2-3 alike tree):

The function name is "printTree". I've integrated it with an AVL tree implementation that is adapted from Prof. Florin Balasa graduate class of advance algorithms. There are three source code files: "AvlTree.h", "AvlTree.cc", and "Application.cc". To compile with GNU compiler, simply run: "g++ Application.cc".

=====================================================

File AvlTree.h :

=====================================================

#ifndef  AVLTREE_H

#define  AVLTREE_H

#include <cstdlib>

#include <iostream>

using namespace std;

#define KEY_SPACE 10 //The maximum spaces needed to draw a key value like: 6,8,10,20,... (Including all the node braces)

//   Template classes for a node and for an AVL tree

template <class Obj>  class AvlTree;

template <class Obj>

class AvlNode {

    // Data members: the key, two pointers, and the height

    Obj key;       

    AvlNode *left, *right;

    int height;

    AvlNode(const Obj& ob = Obj(), AvlNode *l = NULL, AvlNode *r = NULL, int h = 0): key(ob), left(l), right(r), height(h) { }

    friend class AvlTree<Obj>;

};

template <class Obj>

class AvlTree {

        AvlNode<Obj>*  root;

    private:

        void makeEmpty(AvlNode<Obj>*& t) const;

        void rotateLeft(AvlNode<Obj>* & k1);

        void rotateRight(AvlNode<Obj>* & k2);

        void rotateLeftRight(AvlNode<Obj>* & k3);

        void rotateRightLeft(AvlNode<Obj>* & k1);

        AvlNode<Obj>* copyTree(AvlNode<Obj>* t) const;  

        void insert(const Obj& x, AvlNode<Obj>* & t);

        int height(AvlNode<Obj>* t) const { return(t == NULL) ? -1 : t->height; }

        int max(int a, int b) const { return a>=b ? a : b; }

   public:

        AvlTree() { root = NULL; }

        AvlTree(const AvlTree& rhs); // The copy constructor

        ~AvlTree() { makeEmpty(root); }

      const AvlTree<Obj>& operator=(const  AvlTree& rhs);

      AvlTree<Obj>& insert(const  Obj& x) { insert(x, root);  return *this; }

      AvlNode<Obj>* find(const  Obj& x) const;

      AvlNode<Obj>* findMin() const;

      AvlNode<Obj>* findMax() const;

      AvlTree<Obj>& remove(const  Obj& x);

      void printTree() const;

};

#include "AvlTree.cc"

#endif

=====================================================

End of File AvlTree.h

=====================================================

=====================================================

File AvlTree.cc :

=====================================================

#include <stack>

#include <vector>  /* Needed in printTree */

#include <math.h>  /* pow and log10 functions needed in printTree */

#include <iomanip> /* Needed in printTree */

#include <sstream> /* Needed in printTree */

#include <fstream> /* Needed in printTree */

                   

template <class Obj>

AvlTree<Obj>::AvlTree(const AvlTree& rhs) { // The copy constructor

      root = copyTree(rhs.root);       

}

template <class Obj>

AvlNode<Obj>* AvlTree<Obj>::copyTree(AvlNode<Obj>* t) const {

       return( t == NULL ) ? NULL : new AvlNode<Obj>( t->key, copyTree(t->left), copyTree(t->right), t->height );

}

template <class Obj>

void AvlTree<Obj>::makeEmpty(AvlNode<Obj>*& t) const { // Deletes bottom-up the whole tree

       if( t != NULL ) {

             makeEmpty(t->left);       makeEmpty(t->right);

             delete t;      t = NULL;

      }

}

template <class Obj> 

const AvlTree<Obj>& AvlTree<Obj>::operator=(const AvlTree& rhs) { // The assignment operator

      if( this != &rhs ) {

            makeEmpty(root);

            root = copyTree(rhs.root);

     }

      return *this;

}

template <class Obj>

void AvlTree<Obj>::printTree() const { // d is the depth of the node in the tree

    if( root != NULL ) {

        vector<AvlNode<Obj>*> crtLvlNodes(0); // Stored in stack(no delete is needed)

        vector<AvlNode<Obj>*> nxtLvlNodes(0);

       

        crtLvlNodes.push_back(root);

       

        for ( int lvl=height(root)+1; lvl>0; lvl-- ) {

       

            int count = 2;

            for( int i=2; i<=lvl; i++ )

                count += pow(2,i) + pow(2,i-2)*(KEY_SPACE-4)/2;