程序代码：

#include <iostream>
#include<string>
using namespace std;
template <class T>
struct BiNode 
{

 T data;    

 BiNode<T> *lchild, *rchild;
};
template <class T>
class BiTree
{
public:

 BiTree(){ }  // 构造函数 重载后，就取消默认构造函数
 BiTree(BiNode<T>*root);

 ~BiTree();

 BiNode<T>* Getroot();

 void PreOrder(BiNode<T>*root);

 void NpreOrder(BiNode<T>*root);

 void InOrder(BiNode<T>*root);

 void PostOrder(BiNode<T>*root);

 void LevelOrder(BiNode<T>*root);
private:

 BiNode<T> *root;

 BiNode<T>* Creat(BiNode<T>*root);

 void Release(BiNode<T>*root);
};

template<class T>   //构造树
BiTree<T>::BiTree(BiNode<T>*root)
{

 cout<<"请输入创建一棵二叉树的结点数据"<<endl;

 this->root=Creat(root);
}

template <class T>
BiNode<T>* BiTree<T>::Creat(BiNode<T>*root)
{

 T ch;

 cin>>ch;

 if(ch=="#")
  root=NULL;

 else{
  root=new BiNode<T>;
  root->data=ch;
  root->lchild=Creat(root->lchild);
  root->rchild=Creat(root->rchild);

 }

 return root;
}
template<class T>
void BiTree<T>::Release(BiNode<T>*root)
{

 if(root!=NULL){
  Release(root->lchild);
  Release(root->rchild);
  delete root;

 }
}
template <class T>  //析构树
BiTree<T>::~BiTree()
{

 Release(root);
}
template<class T>    //得到树顶
BiNode<T>* BiTree<T>::Getroot( )
{

 return root;
}
//树的遍历算法
template <class T>          //前序递归算法
void BiTree<T>::PreOrder(BiNode<T>*root)
{

 if(root==NULL) return;

 else{
  cout<<root->data;
  PreOrder(root->lchild);
  PreOrder(root->rchild);

 }
}
/*
template <class T>        //前序非递归算法 程序有语法错误，自己改正吧
void BiTree<T>::NpreOrder(BiNode<T>*root)
{

 top=-1;

 while(root!=NULL||top!=-1)

 {
  while(root!=NULL)
  {
   cout<<root->data;
   s[++top]=root;
   root=root->lchild;
  }
  if(top!=-1){
   root=s[top--];
   root=root->rchild;
  }

 }
}
*/
template<class T>      //中序递归算法
void BiTree<T>::InOrder(BiNode<T>*root)
{

 if(root==NULL) return;

 else{
  InOrder(root->lchild);
  cout<<root->data;
  InOrder(root->rchild);

 }
}
template <class T>    //后序递归算法
void BiTree<T>::PostOrder(BiNode<T>*root)
{

 if(root==NULL) return;

 else{
  PostOrder(root->lchild);
  PostOrder(root->rchild);
  cout<<root->data;

 }
}
template<class T>    //层序遍历算法
void BiTree<T>::LevelOrder(BiNode<T>*root)
{

 const int MaxSize = 100;

 int front;

 int rear;

 BiNode<T> *q;

 BiNode<T> *Q[MaxSize];

 front=rear=0;

 if(root==NULL) return;

 Q[++rear]=root;

 while(front!=rear)

 {
  q=Q[++front];
  cout<<q->data;
  if(q->lchild!=NULL) Q[++rear]=q->lchild;
  if(q->rchild!=NULL) Q[++rear]=q->rchild;

 }
}
int main()
{

 BiTree<string> tree(NULL);

 BiNode<string>* root = tree.Getroot( );

 cout<<"------前序遍历------ "<<endl;

 tree.PreOrder(root);

 cout<<endl;

 cout<<"------前序非递归遍历------ "<<endl;
// tree.NpreOrder(root);
 cout<<"------中序遍历------ "<<endl;

 tree.InOrder(root);

 cout<<endl;

 cout<<"------后序遍历------ "<<endl;

 tree.PostOrder(root);

 cout<<endl;

 cout<<"------层序遍历------ "<<endl;

 tree.LevelOrder(root);

 cout<<endl;

 return 0;
}