-
-
[原创]发布一个平衡二叉树[完整代码]
-
发表于:
2008-6-13 22:46
3875
-
[color=#008000]/********************************************************************
created: 2008/06/11
filename: BalancedTree.h
author: happymouse
version: v1.0.0.0
*********************************************************************/[/color]
[color=#0000D0]#pragma[/color] [color=#0000D0]once[/color]
[color=#0000D0]#include[/color] <cassert>
[color=#008000]// Child node balanced status[/color]
[color=#0000D0]enum[/color] EnumBalancedStatus
{
LeanToLeft,
Balanced,
LeanToRight
};
[color=#008000]// Balanced tree template class[/color]
[color=#0000D0]template[/color]<[color=#0000D0]typename[/color] T>
[color=#0000D0]class[/color] CBalancedTree
{
[color=#0000D0]private[/color]:
[color=#008000]// Data[/color]
T m_data;
[color=#008000]// Left child tree[/color]
CBalancedTree<T> *m_pLeftChild;
[color=#008000]// Right child tree[/color]
CBalancedTree<T> *m_pRightChild;
[color=#008000]// Current balanced status[/color]
EnumBalancedStatus m_balancedStatus;
[color=#0000D0]public[/color]:
[color=#008000]// Constructor[/color]
CBalancedTree()
:m_pLeftChild([color=#0000D0]NULL[/color]), m_pRightChild([color=#0000D0]NULL[/color]), m_balancedStatus(Balanced)
{
}
[color=#008000]// Constructor[/color]
CBalancedTree([color=#0000D0]const[/color] T& [color=#0000D0]data[/color])
:m_pLeftChild([color=#0000D0]NULL[/color]), m_pRightChild([color=#0000D0]NULL[/color]), m_balancedStatus(Balanced)
{
m_data = [color=#0000D0]data[/color];
}
[color=#008000]// Destructor[/color]
[color=#0000D0]virtual[/color] ~CBalancedTree()
{
[color=#0000D0]if[/color] ([color=#0000D0]NULL[/color] != m_pLeftChild)
{
[color=#0000D0]delete[/color] m_pLeftChild;
}
[color=#0000D0]if[/color] ([color=#0000D0]NULL[/color] != m_pRightChild)
{
[color=#0000D0]delete[/color] m_pRightChild;
}
}
[color=#008000]// Get left child pointer[/color]
CBalancedTree<T> * GetLeftChild()
{
[color=#0000D0]return[/color] m_pLeftChild;
}
[color=#008000]// Get right child pointer[/color]
CBalancedTree<T> * GetRightChild()
{
[color=#0000D0]return[/color] m_pRightChild;
}
[color=#008000]// Set data[/color]
[color=#0000D0]void[/color] SetData([color=#0000D0]const[/color] T& [color=#0000D0]data[/color])
{
m_data = [color=#0000D0]data[/color];
}
[color=#008000]// Get data[/color]
T& GetData()
{
[color=#0000D0]return[/color] m_data;
}
[color=#008000]// Rotate to left[/color]
[color=#0000D0]void[/color] LeftRotate()
{
[color=#008000]// Swap the data of right child[/color]
T _swapData = m_data;
m_data = m_pRightChild->m_data;
m_pRightChild->m_data = _swapData;
[color=#008000]// Left rotate[/color]
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;
}
[color=#008000]// Rotate to right[/color]
[color=#0000D0]void[/color] RightRotate()
{
[color=#008000]// Swap the data of left child[/color]
T _swapData = m_data;
m_data = m_pLeftChild->m_data;
m_pLeftChild->m_data = _swapData;
[color=#008000]// Right rotate[/color]
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;
}
[color=#008000]// Insert a data into tree. If depth is add return true[/color]
[color=#0000D0]bool[/color] Insert([color=#0000D0]const[/color] T& [color=#0000D0]data[/color])
{
[color=#0000D0]bool[/color] _fAppend = [color=#0000D0]false[/color];
[color=#0000D0]if[/color] ([color=#0000D0]data[/color] == m_data)
{
[color=#0000D0]return[/color] _fAppend;
}
[color=#0000D0]if[/color] ([color=#0000D0]data[/color] < m_data)[color=#008000]// Insert into left child[/color]
{
[color=#0000D0]if[/color] ([color=#0000D0]NULL[/color] == m_pLeftChild)[color=#008000]// Left child depth append[/color]
{
m_pLeftChild = [color=#0000D0]new[/color] CBalancedTree<T>([color=#0000D0]data[/color]);
_fAppend = [color=#0000D0]true[/color];
}
[color=#0000D0]else[/color][color=#008000]// Insert into child of left child[/color]
{
_fAppend = m_pLeftChild->Insert([color=#0000D0]data[/color]);
}
[color=#0000D0]if[/color] (_fAppend)
{
_fAppend = [color=#0000D0]false[/color];
[color=#0000D0]switch[/color](m_balancedStatus)
{
[color=#0000D0]case[/color] LeanToRight:[color=#008000]// Right child has data[/color]
m_balancedStatus = Balanced;
[color=#0000D0]break[/color];
[color=#0000D0]case[/color] Balanced:[color=#008000]// Current depth is append[/color]
m_balancedStatus = LeanToLeft;
_fAppend = [color=#0000D0]true[/color];
[color=#0000D0]break[/color];
[color=#0000D0]case[/color] LeanToLeft:[color=#008000]// Must be balaced of current node[/color]
[color=#0000D0]if[/color] (m_pLeftChild->m_balancedStatus == LeanToLeft)[color=#008000]// Right rotate[/color]
{
RightRotate();
m_pRightChild->m_balancedStatus = Balanced;
[color=#0000D0]break[/color];
}
[color=#0000D0]else[/color] [color=#0000D0]if[/color] (m_pLeftChild->m_balancedStatus == LeanToRight)
{
[color=#008000]// Left rotate and Right rotate[/color]
m_pLeftChild->LeftRotate();
RightRotate();
[color=#0000D0]if[/color]([color=#0000D0]NULL[/color] == m_pLeftChild->m_pRightChild)
{
[color=#0000D0]break[/color];
}
[color=#0000D0]switch[/color] (m_pLeftChild->m_pRightChild->m_balancedStatus)
{
[color=#0000D0]case[/color] LeanToRight:
m_pLeftChild->m_balancedStatus = LeanToLeft;
m_pRightChild->m_balancedStatus = Balanced;
[color=#0000D0]break[/color];
[color=#0000D0]case[/color] Balanced:
m_pLeftChild->m_balancedStatus = Balanced;
m_pRightChild->m_balancedStatus = Balanced;
[color=#0000D0]break[/color];
[color=#0000D0]case[/color] LeanToLeft:
m_pLeftChild->m_balancedStatus = Balanced;
m_pRightChild->m_balancedStatus = LeanToRight;
[color=#0000D0]break[/color];
}
}
m_balancedStatus = Balanced;
[color=#0000D0]break[/color];
}
}
}
[color=#0000D0]else[/color][color=#008000]// Insert into right child[/color]
{
[color=#0000D0]if[/color] ([color=#0000D0]NULL[/color] == m_pRightChild)[color=#008000]// Right child depth append[/color]
{
m_pRightChild = [color=#0000D0]new[/color] CBalancedTree<T>([color=#0000D0]data[/color]);
_fAppend = [color=#0000D0]true[/color];
}
[color=#0000D0]else[/color][color=#008000]// Insert into child of right child[/color]
{
_fAppend = m_pRightChild->Insert([color=#0000D0]data[/color]);
}
[color=#0000D0]if[/color] (_fAppend)[color=#008000]// Right node depth append[/color]
{
_fAppend = [color=#0000D0]false[/color];
[color=#0000D0]switch[/color](m_balancedStatus)
{
[color=#0000D0]case[/color] LeanToLeft:[color=#008000]// Left child has data[/color]
m_balancedStatus = Balanced;
[color=#0000D0]break[/color];
[color=#0000D0]case[/color] Balanced:[color=#008000]// Current depth is append[/color]
m_balancedStatus = LeanToRight;
_fAppend = [color=#0000D0]true[/color];
[color=#0000D0]break[/color];
[color=#0000D0]case[/color] LeanToRight:[color=#008000]// Must be balaced of current node[/color]
[color=#0000D0]if[/color] (m_pRightChild->m_balancedStatus == LeanToRight)[color=#008000]// Left rotate[/color]
{
LeftRotate();
m_pLeftChild->m_balancedStatus = Balanced;
[color=#0000D0]break[/color];
}
[color=#0000D0]else[/color] [color=#0000D0]if[/color] (m_pRightChild->m_balancedStatus == LeanToLeft)
{
[color=#008000]// Right rotate and Left rotate[/color]
m_pRightChild->RightRotate();
LeftRotate();
[color=#0000D0]if[/color] ([color=#0000D0]NULL[/color] == m_pRightChild->m_pLeftChild)
{
[color=#0000D0]break[/color];
}
[color=#0000D0]switch[/color] (m_pRightChild->m_pLeftChild->m_balancedStatus)
{
[color=#0000D0]case[/color] LeanToRight:
m_pLeftChild->m_balancedStatus = LeanToLeft;
m_pRightChild->m_balancedStatus = Balanced;
[color=#0000D0]break[/color];
[color=#0000D0]case[/color] Balanced:
m_pLeftChild->m_balancedStatus = Balanced;
m_pRightChild->m_balancedStatus = Balanced;
[color=#0000D0]break[/color];
[color=#0000D0]case[/color] LeanToLeft:
m_pLeftChild->m_balancedStatus = Balanced;
m_pRightChild->m_balancedStatus = LeanToRight;
[color=#0000D0]break[/color];
}
}
m_balancedStatus = Balanced;
[color=#0000D0]break[/color];
}
}
}
[color=#0000D0]return[/color] _fAppend;
}
[color=#008000]// If the balanced tree. if sucessed return the depth of tree.[/color]
[color=#008000]// failed return -1[/color]
[color=#0000D0]int[/color] IsBalanced()
{
[color=#0000D0]int[/color] _nLeftDepth = 0, _nRightDepth = 0;
[color=#0000D0]if[/color] ([color=#0000D0]NULL[/color] != m_pLeftChild)
{
_nLeftDepth = m_pLeftChild->IsBalanced();[color=#008000]// Get left child tree depth[/color]
}
[color=#0000D0]if[/color] ([color=#0000D0]NULL[/color] != m_pRightChild)
{
_nRightDepth = m_pRightChild->IsBalanced();[color=#008000]// Get right child tree depth[/color]
}
[color=#0000D0]if[/color] (-1 == _nLeftDepth || -1 == _nRightDepth ||
abs(_nLeftDepth - _nRightDepth) > 1)[color=#008000]// |ldepth - rdepth| > 1[/color]
{
[color=#0000D0]return[/color] -1;
}
[color=#0000D0]else[/color] [color=#0000D0]if[/color] (_nLeftDepth >= _nRightDepth)
{
[color=#0000D0]return[/color] _nLeftDepth + 1;[color=#008000]// return left child depth[/color]
}
[color=#0000D0]else[/color]
{
[color=#0000D0]return[/color] _nRightDepth + 1;[color=#008000]// return right child depth[/color]
}
}
[color=#008000]// Make a tree by a data array[/color]
[color=#0000D0]static[/color] [color=#0000D0]void[/color] MakeTree(T *pData, [color=#0000D0]int[/color] nSize, CBalancedTree<T>& [color=#0000D0]out[/color])
{
[color=#b000b0]assert[/color](nSize > 0);
[color=#0000D0]out[/color].SetData(pData[0]);
[color=#0000D0]for[/color] ([color=#0000D0]int[/color] i = 1; i <= nSize; i++)
{
[color=#0000D0]out[/color].Insert(pData[i]);
}
}
};
[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！
