二叉树的实现

#include<iostream>
using namespace std;
#include<queue>
#include<stack>
template<class T>
struct BinaryTreeNode//节点
{
BinaryTreeNode(const T& x)//构造函数
:_data(x)
,_left(NULL)
,_right(NULL)
{}
    T _data;
    BinaryTreeNode<T>* _left;
    BinaryTreeNode<T>* _right;
};
template<class T>
class BinaryTree
{
public:
BinaryTree()//构造函数
:_root(NULL)//根节点赋空值
{}

BinaryTree(const T* a,size_t size)//建立二叉树
{
size_t index=0;
    _root=_CreatTree(a,index,size);
}
~BinaryTree()//析构
{
    Destroy();
}
BinaryTreeNode<T>* Copy()
{
    return _Copy(_root);
}
BinaryTreeNode<T>* Destroy()//删除二叉树
{
   return _Deatroy(_root);
}
void PrevOrder()//前序遍历
{
   _PrevOrder(_root);
   cout<<endl;
}
void InOrder()//中序遍历
{
   _InOrder(_root);
   cout<<endl;
}
void PostOrder()//后序遍历
{
   _PostOrder(_root);
   cout<<endl;
}
void LevelOrder()//层次遍历
{
    _LevelOrder(_root);
cout<<endl;
}
int Size()//计算大小
{
     return _Size(_root);
 cout<<endl;
}
int LeafNum()//叶子节点个数
{
     return _LeafNum(_root);
 cout<<endl;
}
int Hight()//计算二叉树高度
{
    return _Hight(_root);
}
void PrevOrder_Non_R()//非递归前序遍历
{
     _PrevOrder_Non_R(_root);
 cout<<endl;
}
void InOrder_Non_R()//非递归中序遍历
{
      _InOrder_Non_R(_root);
  cout<<endl;
}
void PostOrder_Non_R()//非递归后序遍历
{
      _PostOrder_Non_R(_root);
  cout<<endl;
}
protected:
BinaryTreeNode<T>* _CreatTree(const T* a,size_t& index,size_t size)//创建二叉树
{
     BinaryTreeNode<T>* root=NULL;
 if(index<size&&a[index]!='#')
 {
 root=new BinaryTreeNode<T>(a[index]);//先序创建根节点
     root->_left=_CreatTree(a,++index,size);//递归创建左节点
 root->_right=_CreatTree(a,++index,size);//递归创建右节点
 }
 return root;
}
void _PrevOrder(BinaryTreeNode<T>* root)
{
    if(root==NULL)
{
return;
}
else
{
    cout<<root->_data<<" ";
   _PrevOrder(root->_left );
   _PrevOrder(root->_right );
}
}
void _InOrder(BinaryTreeNode<T>* root)
{
   if(root==NULL)
   {
      return;
   }
  else
   {
      _InOrder(root->_left );
  cout<<root->_data <<" ";
  _InOrder(root->_right );
   }
}
void _PostOrder(BinaryTreeNode<T>* root)
{
if(root==NULL)
return;
else
{
_PostOrder(root->_left );
    _PostOrder(root->_right );
    cout<<root->_data <<" ";
}
}
void _LevelOrder(BinaryTreeNode<T>* root)//队列的使用
{
   queue<BinaryTreeNode<T>*> q;
   q.push(root);
   while(root)
   {
       cout<<root->_data <<" ";
   if(!q.empty())
   {
      BinaryTreeNode<T>* front =q.front();
  q.pop();
  q.push(front->_left );
  q.push(front->_right );
   }
   root=q.front();
   }
}
int _Size(BinaryTreeNode<T>* root)
{
    if(root==NULL)
return 0;
return  _Size(root->_left )+_Size(root->_right )+1;
}
int _LeafNum(BinaryTreeNode<T>* root)
{
    if(root==NULL)
return 0;
if((root->_left ==NULL)&&(root->_right ==NULL))
return 1;

return _LeafNum(root->_left )+_LeafNum(root->_right );
}
int _Hight(BinaryTreeNode<T>* root)
{
    if(root==NULL)
return 0;
if(_Hight(root->_left) >_Hight(root->_right ))
{
    return  _Hight(root->_left )+1;
}
else
{
     return _Hight(root->_right )+1;
}
}
BinaryTreeNode<T>* _Copy(BinaryTreeNode<T>* root)
{
    if(root==NULL)
return NULL;
else
{
BinaryTreeNode<T>* r=new BinaryTreeNode<T>(root->_data );
BinaryTreeNode<T>* left=_Copy(root->_left );
BinaryTreeNode<T>* right=_Copy(root->_right );
return r;
}
}
BinaryTreeNode<T>* _Deatroy(BinaryTreeNode<T>*& root)
{
   if(root!=NULL)
   {
       _Destroy(root->_left );
   _Deatroy(root->_right );
   delete root;
   root=NULL;
   }
   return root;
}
void  _PrevOrder_Non_R(BinaryTreeNode<T>* root)
{
    BinaryTreeNode<T>* cur=root;
stack<BinaryTreeNode<T>*> s;
while(cur!=NULL||!s.empty ())
{
while(cur!=NULL)
{
     cout<<cur->_data <<" ";
 s.push(cur);
 cur=cur->_left ;
}
if(!s.empty ())
{
     cur=s.top();
 s.pop();
 cur=cur->_right ;
}
}
}
void  _InOrder_Non_R(BinaryTreeNode<T>* root)
{
    BinaryTreeNode<T>* cur=root;
stack<BinaryTreeNode<T>*> s;
while(cur!=NULL||!s.empty ())
{
while(cur!=NULL)
{
 s.push(cur);
 cur=cur->_left ;
}
if(!s.empty ())
{
     cur=s.top();
 cout<<cur->_data <<" ";
 s.pop();
 cur=cur->_right ;
}
}
}
void _PostOrder_Non_R(BinaryTreeNode<T>* root)
{
BinaryTreeNode<T>* cur=NULL;
BinaryTreeNode<T>* temp=NULL;
    stack<BinaryTreeNode<T>*> s;
s.push(root);
while(!s.empty ())
{
cur=s.top();
if((cur->_left ==NULL && cur->_right ==NULL)||
(temp!=NULL && (temp==cur->_left||temp==cur->_right)))
{
   cout<<cur->_data <<" ";
   s.pop();
   temp=cur;
}
else
{
    if(cur->_right !=NULL)
{
   s.push(cur->_right );
}
if(cur->_left !=NULL)
{
    s.push(cur->_left );
}
}
}
}
protected:
BinaryTreeNode<T>* _root;
};