C / C++ / MFC

//file name avlTree.h
#include <iostream>
using namespace std;

template<class T>  //class element type T
struct AVLNode
{
	T info;
	int bfactor;               // balance factor
	AVLNode<T> *llink;
	AVLNode<T> *rlink;
};
template <class T>
class AVLTreeType
{
  public:

	void insert(const T &newItem);

    void postorderTraversal(void (*visit)(T&) );
   
	void rnl_inorderTraversal(void (*visit)(T&,int));
	
	int treeHeight();
    int treeNodeCount();
    int treeLeavesCount();
    void destroyTree();
    AVLTreeType();  //default constructor
	
  private:
    AVLNode<T>* root;
	
	
	
	//associated with insert
    void rotateToLeft(AVLNode<T>* &root);
    void rotateToRight(AVLNode<T>* &root);
    void balanceFromLeft(AVLNode<T>* &root);
    void balanceFromRight(AVLNode<T>* &root);
    void insertIntoAVL(AVLNode<T>* &root,AVLNode<T>  *newNode, bool& isTaller);

	void rnl_inorder(AVLNode<T> *p,void(*visit)(T&,int),int);

   
    void postorder(AVLNode<T> *p, void (*visit)(T&) );
    
    void destroy(AVLNode<T>* &p);
};



template<class T>
void AVLTreeType<T>::rotateToLeft(AVLNode<T>* &root)
{
     AVLNode<T> *p; //pointer to the root of the
                           //right subtree of root
     if(root == NULL)
        cerr<<"Error in the tree."<<endl;
     else
        if(root->rlink == NULL)
           cerr<<"Error in the tree:"
               <<" No right subtree to rotate."<<endl;
        else
        {
            p = root->rlink;
            root->rlink = p->llink; //the left subtree of p 
                             //becomes the right subtree of root
            p->llink = root; 
            root = p;	//make p the new root node
        }
}//end rotateTOLeft

template<class T>
void AVLTreeType<T>::rotateToRight(AVLNode<T>* &root)
{
     AVLNode<T> *p;  //pointer to the root of	
                            //the left subtree of root

     if(root == NULL)
        cerr<<"Error in the tree."<<endl;
     else
        if(root->llink == NULL)
           cerr<<"Error in the tree:"
               <<" No left subtree to rotate."<<endl;
        else
        {
           p = root->llink;
           root->llink = p->rlink; //the right subtree of p 
                           //becomes the left subtree of root
           p->rlink = root; 
           root = p;	//make p the new root node
        }
}//end rotateToRight

template<class T>
void AVLTreeType<T>::balanceFromLeft(AVLNode<T>* &root)
{
     AVLNode<T> *p;
     AVLNode<T> *w;

     p = root->llink;   //p points to the left subtree of root

     switch(p->bfactor)
     {
     case -1: root->bfactor = 0;
              p->bfactor = 0;
              rotateToRight(root);
              break;
     case 0:  cerr<<"Error: Cannot balance from the left."<<endl;
              break;
     case 1:  w = p->rlink;
              switch(w->bfactor)  //adjust the balance factors
              {
              case -1: root->bfactor = 1;
                       p->bfactor = 0;
                       break;
              case 0:  root->bfactor = 0;
                       p->bfactor = 0;
                       break; 
              case 1:  root->bfactor = 0;
                       p->bfactor = -1;
              }//end switch

              w->bfactor = 0;	
              rotateToLeft(p);
              root->llink = p;
              rotateToRight(root);
     }//end switch;
}//end balanceFromLeft

template<class T>
void AVLTreeType<T>::balanceFromRight(AVLNode<T>* &root)
{
     AVLNode<T> *p;
     AVLNode<T> *w;

     p = root->rlink;   //p points to the right subtree of root

     switch(p->bfactor)
     {
     case -1: w = p->llink;
              switch(w->bfactor)  //adjust the balance factors
              {
              case -1: root->bfactor = 0;
                       p->bfactor = 1;
                       break;
              case 0:  root->bfactor = 0;
                       p->bfactor = 0;
                       break;		
              case 1:  root->bfactor = -1;
                       p->bfactor = 0;
              }//end switch

              w->bfactor = 0;	
              rotateToRight(p);
              root->rlink = p;
              rotateToLeft(root);
              break;
     case 0:  cerr<<"Error: Cannot balance from the right."<<endl;
              break;
     case 1:  root->bfactor = 0;
              p->bfactor = 0;
              rotateToLeft(root);
     }//end switch;
}//end balanceFromRight


template<class T>
void AVLTreeType<T>::insert(const T &newItem)
{
     bool isTaller = false;
     AVLNode<T>  *newNode;

     newNode = new AVLNode<T>;
     newNode->info = newItem;
     newNode->bfactor = 0;
     newNode->llink = NULL;
     newNode->rlink = NULL;

     insertIntoAVL(root, newNode, isTaller);
}//end insert



template<class T>
void AVLTreeType<T>::insertIntoAVL(AVLNode<T>* &root, 
			   AVLNode<T>  *newNode, 
			   bool& isTaller)
{
    if(root == NULL)
    {
       root = newNode;
       isTaller = true;
    }
	else 
		if(root->info == newNode->info)
          cerr<<"No duplicates are allowed."<<endl;
	else 
		if(root->info > newNode->info) //newItem goes in 
                                         //the left subtree
          {
             insertIntoAVL(root->llink, newNode, isTaller);

             if(isTaller)             //after insertion, the 
                                      //subtree grew in height
                switch(root->bfactor)
                {
                case -1: balanceFromLeft(root);
                         isTaller = false;
                         break;
                case 0:  root->bfactor = -1;
                         isTaller = true;
                         break;
                case 1:  root->bfactor = 0;
                         isTaller = false;
                }//end switch
          }//end if
          else
          {
             insertIntoAVL(root->rlink, newNode, isTaller);

             if(isTaller)              //after insertion, the 
                                       //subtree grew in height
                switch(root->bfactor)
                {
                case -1: root->bfactor = 0;
                         isTaller = false;
                         break;
                case 0:  root->bfactor = 1;
                         isTaller = true;
                         break;
                case 1:  balanceFromRight(root);
                         isTaller = false;
                }//end switch
          }//end else
}//end insertIntoAVL

template <class T> 
void AVLTreeType<T>::postorderTraversal(void (*visit)(T& item) )
{
	postorder(root, *visit);
}

template <class T> 
void AVLTreeType<T>::postorder(AVLNode<T> *p, 
                             void (*visit)(T& item) )
{
        if(p != NULL)
        {
                postorder(p->llink, *visit);
         
                postorder(p->rlink, *visit);
      (*visit)(p->info);      //function in client file
	 } 
}


template <class T> 
void AVLTreeType<T>::destroy(AVLNode<T>* &p) 
{    
        if(p != NULL)
        {
                destroy(p->llink);
                destroy(p->rlink);
                delete p;
                p = NULL;
        }
}

template <class T>
void  AVLTreeType<T>::destroyTree()
{
        destroy(root);
}

template<class T>
AVLTreeType<T>::AVLTreeType()
{
	root=NULL;
}


template<class T>
void rnl_inorderTraversal(void(*visit)(T&,int))
{
int iLevel=0;
rnl_inorder(root,*visit,iLevel);
}


template<class T>
void rnl_inorder(AVLNode<T> *p,void(*visit)(T&,int),int)
{
	if(p != NULL)
        {
               
				iLevel+1;	
				rnl_inorder(p->rlink,*visit,iLevel);
                (*visit)(p->info);      //function in client file
                rnl_inorder(p->llink,*visit,iLevel)
		} 
}

#include <iostream>  
#include <iomanip>   
#include"avlTree.h"
#include <fstream>
                     
using namespace std;
//function prototype 
template<class T> 
void displayHierarchial(T& anItem, int level);


int main()
{

AVLTreeType<int> cTree1;
cTree1.insert(1);
cTree1.insert(2);
cTree1.insert(4);
cTree1.rnl_inorderTraversal(displayHierarchial);



return 0;
//function definition 
template<class T>    
void displayHierarchial (T& anItem, int level)
{
  cout <<level<<".) "<< anItem<<' '; //display number from binary tree
}