implementation of tree and in_order traversal (plus tree balancing)

#pragma once

#include<stack>
#include<iostream>
template<class T>
class CTreeNode
{
public:
T m_val;
CTreeNode* left;
CTreeNode* right;

CTreeNode(){left=NULL;right=NULL;}
~CTreeNode(void);
};

template<class T>
class CTree
{
public:
CTreeNode<T>* m_root;

CTree(T val){m_root=new CTreeNode<T>();m_root->m_val=val;}
~CTree(){}
void insert(T val);
void in_order();
};


template<class T>
void CTree<T>::insert(T val)
{
CTreeNode<T>* cur_node=m_root,*prev_node;
while(cur_node!=NULL)
{
prev_node=cur_node;
if(val<cur_node->m_val)
cur_node=cur_node->left;
else
cur_node=cur_node->right;

}
cur_node=new CTreeNode<T>();
cur_node->m_val=val;
if(val<prev_node->m_val)
prev_node->left=cur_node;
else
prev_node->right=cur_node;
}

template<class T>
void CTree<T>::in_order()
{
CTreeNode<T>* cur_node=m_root;
stack<CTreeNode<T>*> node_stack;
while(cur_node)
{
node_stack.push(cur_node);
cur_node=cur_node->left;
}
while(!node_stack.empty())
{
CTreeNode<T>* node=node_stack.top();
node_stack.pop();
std::cout<<node->m_val<<" ";
CTreeNode<T>* right=node->right;
while(right)
{
node_stack.push(right);
right=right->left;
}
}
}

tree balancing:

balanceFactor = height(left-subtree) - height(right-subtree). 

Right-Right case and Right-Left case:

• If the balance factor of P is -2 then the right subtree outweighs the left subtree of the given node, and the balance factor of the right child (R) must be checked. The left rotation with P as the root is necessary.
  • If the balance factor of R is -1 (or in case of deletion also 0), a single left rotation (with P as the root) is needed (Right-Right case).
  • If the balance factor of R is +1, two different rotations are needed. The first rotation is a right rotation with R as the root. The second is aleft rotation with P as the root (Right-Left case).

Left-Left case and Left-Right case:

• If the balance factor of P is 2, then the left subtree outweighs the right subtree of the given node, and the balance factor of the left child (L) must be checked. The right rotation with P as the root is necessary.
• If the balance factor of L is +1 (or in case of deletion also 0), a single right rotation (with P as the root) is needed (Left-Left case).
• If the balance factor of L is -1, two different rotations are needed. The first rotation is a left rotation with L as the root. The second is aright rotation with P as the root (Left-Right case).

http://en.wikipedia.org/wiki/AVL_tree