实现对二叉树的基本操作：
#include <iostream>
#include <queue>
#include <stack>
#include <stdlib.h>
using namespace std;
template <class T>
struct Node
{
Node(const T& data)
:_data(data)
,_pLeft(NULL)
,_pRight(NULL)
{}
T _data;
Node<T> *_pLeft;
Node<T> *_pRight;
};
template <class T>
class BinaryTree
{
public:
BinaryTree()
:_pRoot(NULL)
{}
BinaryTree(T array[], int size, int invalid)
{
int index = 0;
_CreateTree(_pRoot, array, size, index, invalid);
}
BinaryTree(const BinaryTree<T>& t)
{
_pRoot = _CopyBinaryTree(t._pRoot);
}
BinaryTree<T>& operator=(const BinaryTree<T>& t)
{
if(this != &t)
{
_DestroyTree(_pRoot);
_pRoot = _CopyBinaryTree(t._pRoot);
}
return *this;
}
~BinaryTree()
{
_DestroyTree(_pRoot);
_pRoot = NULL;
}
//前序遍历
void PreOrder()
{
cout<<"PreOrder:"<<endl;
_PreOrder(_pRoot);
cout<<endl;
}
//中序遍历
void InOrder()
{
cout<<"InOrder:"<<endl;
_InOrder(_pRoot);
cout<<endl;
}
//后序遍历
void PostOrder()
{
cout<<"PostOrder:"<<endl;
_PostOrder(_pRoot);
cout<<endl;
}
//层序遍历
void LevelOrder()
{
cout<<"LevelOrder:"<<endl;
_LevelOrder(_pRoot);
cout<<endl;
}
//从二叉树中找到某个节点
Node<T>* Find(const T& value)
{
return _Find(_pRoot, value);
}
//获取某个节点的双亲节点
Node<T>* GetParentNode(Node<T>* x)
{
return _GetParentNode(_pRoot, x);
}
//获取某个节点的左孩子
Node<T>* GetLeftNode(Node<T>* pCur)
{
return (pCur==NULL)?NULL:pCur->_pLeft;
}
//获取某个节点的右孩子
Node<T>* GetRightNode(Node<T>* pCur)
{
return (pCur==NULL)?NULL:pCur->_pRight;
}
//获取二叉树的高度
int Height()
{
return _Height(_pRoot);
}
//求二叉树的叶子节点的数目
int GetLeefNode()
{
return _GetLeefNode(_pRoot);
}
//求二叉树某一层的节点数
int GetKLevelNode(int k)
{
return _GetKLevelNode(_pRoot,k);
}
//迭代代替递归实现前序遍历
void PreOrder_Nor()
{
cout<<"PreOrder_Nor:"<<endl;
_PreOrder_Nor(_pRoot);
cout<<endl;
}
//迭代代替递归实现中序遍历
void InOrder_Nor()
{
cout<<"InOrder_Nor:"<<endl;
_InOrder_Nor(_pRoot);
cout<<endl;
}
//迭代代替递归实现后序遍历
void PostOrder_Nor()
{
cout<<"PostOrder_Nor:"<<endl;
_PostOrder_Nor(_pRoot);
cout<<endl;
}
//求二叉树的镜像
void GetBinaryMirror_Nor()
{
if(_pRoot == NULL)
return;
queue<Node<T>*> q;
q.push(_pRoot);
while(!q.empty())
{
Node<T>* pCur = q.front();
q.pop();
std::swap(pCur->_pLeft, pCur->_pRight);
if(pCur->_pLeft)
q.push(pCur->_pLeft);
if(pCur->_pRight)
q.push(pCur->_pRight);
}
}
//求二叉树的镜像递归版本
void GetBinaryMirror(Node<T>* pRoot)
{
if(pRoot)
{
std::swap(pRoot->_pLeft, pRoot->_pRight);
GetBinaryMirror(pRoot->_pLeft);
GetBinaryMirror(pRoot->_pRight);
}
}
//判断一棵二叉树是不是完全二叉树
bool IsCompleteBinaryTree()
{
if(_pRoot == NULL)
return true;
queue<Node<T>*> q;
q.push(_pRoot);
bool flag = false;
while(!q.empty())
{
Node<T>* pCur = q.front();
if(flag)
{
if(pCur->_pLeft || pCur->_pRight)
return false;
}
if(pCur->_pLeft && pCur->_pRight)
{
q.push(pCur->_pLeft);
q.push(pCur->_pRight);
}
else if(pCur->_pLeft)
{
q.push(pCur->_pLeft);
flag = true;
}
else if(pCur->_pRight)
return false;
else
flag = true;
q.pop();
}
return true;
}
//通过前序和中序的序列来重建二叉树
pNode RebuildBinaryTree(char *PreOrder, char *InOrder, int length)
{
if(PreOrder==NULL || InOrder==NULL || length==0)
return NULL;
//根结点
Node* _pRoot = new Node<char>(PreOrder[0]);
int rootPositionInOrder = -1;
for(int i=0; i<length; i++)
{
if(InOrder[i] == PreOrder[0])
{
rootPositionInOrder = i;
break;
}
}
//重建左子树
int nodeNumLeft = rootPositionInOrder;
char* pPreOrderLeft = PreOrder + 1;
char* pInOrderLeft = InOrder + nodeNumLeft;
_pRoot->_pLeft = RebuildBinaryTree(pPreOrderLeft, pInOrderLeft, nodeNumLeft);
// 重建右子树
int nodeNumRight = length - nodeNumLeft - 1;
char* pPreOrderRight = PreOrder + 1 + nodeNumLeft;
char* pInOrderRight = InOrder + nodeNumLeft + 1;
_pRoot->_pRight = RebuildBinaryTree(pPreOrderRight, pInOrderRight, nodeNumRight);
return _pRoot;
}
private:
void _CreateTree(Node<T> *&pRoot,T array[], int size, int &index, int invalid)
{//通过前序遍历的规则来创建
if(index<size && array[index]!=invalid)
{
pRoot = new Node<T>(array[index]);
_CreateTree(pRoot->_pLeft, array, size, ++index, invalid);
_CreateTree(pRoot->_pRight, array, size, ++index, invalid);
}
}
Node<T>* _CopyBinaryTree(Node<T>* pRoot)
{
Node<T>* pNewNode = NULL;
if(pRoot != NULL)
{
pNewNode = new Node<T>(pRoot->_data);
pNewNode->_pLeft = _CopyBinaryTree(pRoot->_pLeft);
pNewNode->_pRight = _CopyBinaryTree(pRoot->_pRight);
}
return pNewNode;
}
void _DestroyTree(Node<T>*& pRoot)//通过后序遍历的规则来销毁
{
if(pRoot != NULL)
{
_DestroyTree(pRoot->_pLeft);
_DestroyTree(pRoot->_pRight);
delete pRoot;
pRoot = NULL;
}
}
void _PreOrder(Node<T>* pRoot)//根左右
{
if(pRoot)
{
cout<<pRoot->_data<<" ";
_PreOrder(pRoot->_pLeft);
_PreOrder(pRoot->_pRight);
}
}
void _InOrder(Node<T>* pRoot)//左根右
{
if(pRoot)
{
_InOrder(pRoot->_pLeft);
cout<<pRoot->_data<<" ";
_InOrder(pRoot->_pRight);
}
}
void _PostOrder(Node<T>* pRoot)//左右根
{
if(pRoot)
{
_PostOrder(pRoot->_pLeft);
_PostOrder(pRoot->_pRight);
cout<<pRoot->_data<<" ";
}
}
void _LevelOrder(Node<T>* pRoot)//利用先进先出的队列保存节点
{
if(pRoot == NULL)
{
return;
}
queue<Node<T>* > q;
q.push(pRoot);
Node<T>* pCur = NULL;
while(!q.empty())
{
pCur = q.front();
cout<<pCur->_data<<" ";
if(pCur->_pLeft)
q.push(pCur->_pLeft);
if(pCur->_pRight)
q.push(pCur->_pRight);
q.pop();
}
}
Node<T>* _Find(Node<T>* pRoot, const T& value)
{
if(pRoot == NULL)
{
return NULL;
}
if(pRoot->_data == value)
{
return pRoot;
}
Node<T>* pCur = NULL;
if(pCur=_Find(pRoot->_pLeft, value))
return pCur;
if(pCur=_Find(pRoot->_pRight, value))
return pCur;
}
Node<T>* _GetParentNode(Node<T>* pRoot, Node<T>* x)
{
if(pRoot==NULL || x==NULL || x==pRoot)
{
return NULL;
}
if(pRoot->_pLeft==x || pRoot->_pRight==x)
{
return pRoot;
}
Node<T>* parent = NULL;
if(parent=_GetParentNode(pRoot->_pLeft, x))
return parent;
if(parent=_GetParentNode(pRoot->_pRight, x))
return parent;
}
int _Height(Node<T>* pRoot)
{
if(pRoot == NULL)
return 0;
if(pRoot->_pLeft==NULL && pRoot->_pRight==NULL)
return 1;
int leftHeight = _Height(pRoot->_pLeft);
int rightHeight = _Height(pRoot->_pRight);
return (leftHeight>rightHeight)?leftHeight+1:rightHeight+1;
}
int _GetLeefNode(Node<T>* pRoot)
{
if(pRoot == NULL)
{
return 0;
}
if(pRoot->_pLeft==NULL && pRoot->_pRight==NULL)
{
return 1;
}
return (_GetLeefNode(pRoot->_pLeft)+_GetLeefNode(pRoot->_pRight));
}
int _GetKLevelNode(Node<T>* pRoot, int k)
{
if(pRoot==NULL || k<1 || k>_Height(pRoot))
return 0;
if(k == 1)
return 1;
return _GetKLevelNode(pRoot->_pLeft, k-1)+_GetKLevelNode(pRoot->_pRight, k-1);
}
void _PreOrder_Nor(Node<T>* pRoot)
{
if(pRoot == NULL)
return;
stack<Node<T>*> s;
s.push(pRoot);
Node<T>* pCur = pRoot;
while(!s.empty())
{
pCur = s.top();
s.pop();
while(pCur)
{
cout<<pCur->_data<<" ";
if(pCur->_pRight)
{
s.push(pCur->_pRight);
}
pCur = pCur->_pLeft;
}
}
}
void _InOrder_Nor(Node<T>* pRoot)
{
if(pRoot == NULL)
return;
stack<Node<T>*> s;
Node<T>* pCur = pRoot;
while(!s.empty() || pCur)
{
while(pCur)
{
s.push(pCur);
pCur = pCur->_pLeft;
}
pCur = s.top();
cout<<pCur->_data<<" ";
s.pop();
pCur = pCur->_pRight;
}
cout<<endl;
}
void _PostOrder_Nor(Node<T>* pRoot)
{
if(pRoot == NULL)
return;
stack<Node<T>*> s;
Node<T>* pCur = pRoot;
Node<T>* prev = NULL;
while(!s.empty() || pCur)
{
while(pCur)
{
s.push(pCur);
pCur = pCur->_pLeft;
}
pCur = s.top();
if(pCur->_pRight==NULL || prev==pCur->_pRight)
{
cout<<pCur->_data<<" ";
prev = pCur;
s.pop();
pCur = NULL;
}
else
{
pCur = pCur->_pRight;
}
}
}
Node<T> *_pRoot;
};