代码:
/********************************************************************
created: 2008/06/11
filename: BalancedTree.h
author: happymouse
version: v1.0.0.0
*********************************************************************/
#pragma once
#include <cassert>
// Child node balanced status
enum EnumBalancedStatus
{
LeanToLeft,
Balanced,
LeanToRight
};
// Balanced tree template class
template<typename T>
class CBalancedTree
{
private:
// Data
T m_data;
// Left child tree
CBalancedTree<T> *m_pLeftChild;
// Right child tree
CBalancedTree<T> *m_pRightChild;
// Current balanced status
EnumBalancedStatus m_balancedStatus;
public:
// Constructor
CBalancedTree()
:m_pLeftChild(NULL), m_pRightChild(NULL), m_balancedStatus(Balanced)
{
}
// Constructor
CBalancedTree(const T& data)
:m_pLeftChild(NULL), m_pRightChild(NULL), m_balancedStatus(Balanced)
{
m_data = data;
}
// Destructor
virtual ~CBalancedTree()
{
if (NULL != m_pLeftChild)
{
delete m_pLeftChild;
}
if (NULL != m_pRightChild)
{
delete m_pRightChild;
}
}
// Get left child pointer
CBalancedTree<T> * GetLeftChild()
{
return m_pLeftChild;
}
// Get right child pointer
CBalancedTree<T> * GetRightChild()
{
return m_pRightChild;
}
// Set data
void SetData(const T& data)
{
m_data = data;
}
// Get data
T& GetData()
{
return m_data;
}
// Rotate to left
void LeftRotate()
{
// Swap the data of right child
T _swapData = m_data;
m_data = m_pRightChild->m_data;
m_pRightChild->m_data = _swapData;
// Left rotate
CBalancedTree<T> *_swapTree = m_pRightChild;
m_pRightChild = m_pRightChild->m_pRightChild;
_swapTree->m_pRightChild = _swapTree->m_pLeftChild;
_swapTree->m_pLeftChild = m_pLeftChild;
m_pLeftChild = _swapTree;
}
// Rotate to right
void RightRotate()
{
// Swap the data of left child
T _swapData = m_data;
m_data = m_pLeftChild->m_data;
m_pLeftChild->m_data = _swapData;
// Right rotate
CBalancedTree<T> *_swapTree = m_pLeftChild;
m_pLeftChild = m_pLeftChild->m_pLeftChild;
_swapTree->m_pLeftChild = _swapTree->m_pRightChild;
_swapTree->m_pRightChild = m_pRightChild;
m_pRightChild = _swapTree;
}
// Insert a data into tree. If depth is add return true
bool Insert(const T& data)
{
bool _fAppend = false;
if (data == m_data)
{
return _fAppend;
}
if (data < m_data)// Insert into left child
{
if (NULL == m_pLeftChild)// Left child depth append
{
m_pLeftChild = new CBalancedTree<T>(data);
_fAppend = true;
}
else// Insert into child of left child
{
_fAppend = m_pLeftChild->Insert(data);
}
if (_fAppend)
{
_fAppend = false;
switch(m_balancedStatus)
{
case LeanToRight:// Right child has data
m_balancedStatus = Balanced;
break;
case Balanced:// Current depth is append
m_balancedStatus = LeanToLeft;
_fAppend = true;
break;
case LeanToLeft:// Must be balaced of current node
if (m_pLeftChild->m_balancedStatus == LeanToLeft)// Right rotate
{
RightRotate();
m_pRightChild->m_balancedStatus = Balanced;
break;
}
else if (m_pLeftChild->m_balancedStatus == LeanToRight)
{
// Left rotate and Right rotate
m_pLeftChild->LeftRotate();
RightRotate();
if(NULL == m_pLeftChild->m_pRightChild)
{
break;
}
switch (m_pLeftChild->m_pRightChild->m_balancedStatus)
{
case LeanToRight:
m_pLeftChild->m_balancedStatus = LeanToLeft;
m_pRightChild->m_balancedStatus = Balanced;
break;
case Balanced:
m_pLeftChild->m_balancedStatus = Balanced;
m_pRightChild->m_balancedStatus = Balanced;
break;
case LeanToLeft:
m_pLeftChild->m_balancedStatus = Balanced;
m_pRightChild->m_balancedStatus = LeanToRight;
break;
}
}
m_balancedStatus = Balanced;
break;
}
}
}
else// Insert into right child
{
if (NULL == m_pRightChild)// Right child depth append
{
m_pRightChild = new CBalancedTree<T>(data);
_fAppend = true;
}
else// Insert into child of right child
{
_fAppend = m_pRightChild->Insert(data);
}
if (_fAppend)// Right node depth append
{
_fAppend = false;
switch(m_balancedStatus)
{
case LeanToLeft:// Left child has data
m_balancedStatus = Balanced;
break;
case Balanced:// Current depth is append
m_balancedStatus = LeanToRight;
_fAppend = true;
break;
case LeanToRight:// Must be balaced of current node
if (m_pRightChild->m_balancedStatus == LeanToRight)// Left rotate
{
LeftRotate();
m_pLeftChild->m_balancedStatus = Balanced;
break;
}
else if (m_pRightChild->m_balancedStatus == LeanToLeft)
{
// Right rotate and Left rotate
m_pRightChild->RightRotate();
LeftRotate();
if (NULL == m_pRightChild->m_pLeftChild)
{
break;
}
switch (m_pRightChild->m_pLeftChild->m_balancedStatus)
{
case LeanToRight:
m_pLeftChild->m_balancedStatus = LeanToLeft;
m_pRightChild->m_balancedStatus = Balanced;
break;
case Balanced:
m_pLeftChild->m_balancedStatus = Balanced;
m_pRightChild->m_balancedStatus = Balanced;
break;
case LeanToLeft:
m_pLeftChild->m_balancedStatus = Balanced;
m_pRightChild->m_balancedStatus = LeanToRight;
break;
}
}
m_balancedStatus = Balanced;
break;
}
}
}
return _fAppend;
}
// If the balanced tree. if sucessed return the depth of tree.
// failed return -1
int IsBalanced()
{
int _nLeftDepth = 0, _nRightDepth = 0;
if (NULL != m_pLeftChild)
{
_nLeftDepth = m_pLeftChild->IsBalanced();// Get left child tree depth
}
if (NULL != m_pRightChild)
{
_nRightDepth = m_pRightChild->IsBalanced();// Get right child tree depth
}
if (-1 == _nLeftDepth || -1 == _nRightDepth ||
abs(_nLeftDepth - _nRightDepth) > 1)// |ldepth - rdepth| > 1
{
return -1;
}
else if (_nLeftDepth >= _nRightDepth)
{
return _nLeftDepth + 1;// return left child depth
}
else
{
return _nRightDepth + 1;// return right child depth
}
}
// Make a tree by a data array
static void MakeTree(T *pData, int nSize, CBalancedTree<T>& out)
{
assert(nSize > 0);
out.SetData(pData[0]);
for (int i = 1; i <= nSize; i++)
{
out.Insert(pData[i]);
}
}
};
平衡树特点：
1.根的左子树和右子树深度差最多为1。
2.根的左子树和右子树都是平衡树。
3.平衡树中不允许出现重复数据。
以下为测试代码：
代码:
int _aryValue1[] = {
1, 2, 3, 4, 5, 6, 7
};
AVL avl1, avl2;
AVL::MakeTree(_aryValue1, sizeof(_aryValue1) / sizeof(int), avl1);
cout << (avl1.IsBalanced() >= 0? "avl1是平衡树！": "avl1不是平衡树！") << endl;
int _aryValue2[] = {
50, 30, 80, 20, 40
};
AVL::MakeTree(_aryValue2, sizeof(_aryValue2) / sizeof(int), avl2);
cout << (avl2.IsBalanced() >= 0? "avl2是平衡树！": "avl2不是平衡树！") << endl;