#include <iostream.h>
#include <conio.h>
typedef int ElemType;
  struct NodeType                        //定义结点 结构体
      {  ElemType data;
    NodeType  *lch;
    NodeType  *rch;
        };
class BiTree                         //定义 二叉树类 class
 {public:
      BiTree(){root=NULL;} ;           // 构造函数
      ~BiTree();                       // 析构函数
      void creat();                    //建立二叉树
      void preorder()                  //先序遍历调用
       {    preorder(root);}
      void inorder()                  //中序遍历调用
       {    inorder(root); }
      void postorder()                //后序遍历调用
       {  postorder(root);}
protected:
 NodeType *root; //数据成员,树根指针,该类的派生类的成员也可以访问
  private:
      void inorder(NodeType *p);       //中序递归遍历
      void preorder(NodeType *p);      //先序递归遍历
      void postorder(NodeType *p);     //后序递归遍历
      void destroy(NodeType *p);      //删除二叉树所有结点&*p
         
 };
BiTree::~BiTree(){destroy(root); root=NULL;}// 析构函数
void  BiTree::destroy(NodeType *p)   //递归删除二叉树所有结点
{   if(p != NULL)
    {       destroy(p->lch);
        destroy(p->rch);
        delete p;
    }
}
void BiTree::creat()                          //建立二叉树算法
{
  NodeType *q, *s[20];   ElemType x;  int i,j;
  cout<<"\n 请按照二叉树的层序，自上而下自左致右顺序组织数据0 0结束"<<endl;
  cout<<"\n 每次输入结点的序号和数据，假设根结点值为11;"<<endl;
  cout<<"\n 那么输入应是：1  11"<<endl;
  root=NULL;
  cout<<"\n i,x=";   cin>>i>>x;
      while ((i!=0)&&(x!=0))
         { q=new NodeType;                  // 产生一个结点
           q->data=x; q->lch=NULL; q->rch=NULL;
           s[i]=q;
           if (i==1) root=q;                // q为树根结点 
             else { j=i/2;                  // j为双亲结点编号
                    if ((i%2)==0) s[j]->lch=q;//如果i为偶数，则它是双亲结点的左孩子
                       else s[j]->rch=q;//如果i为奇数，则它是双亲结点的右孩子
                     }
           cout<<"\n i,x=";   cin>>i>>x;
          }
}
void BiTree::preorder(NodeType *p)  //先序递归遍历
{ if(p != NULL)
    {
     cout<<p->data<<" ";         // 访问根结点
     preorder(p->lch);// 按先根次序遍历左子树
     preorder(p->rch);  // 按先根次序遍历右子树
}
}
void BiTree::inorder(NodeType *p)     //中序递归遍历
{  if(p != NULL)
       {
         inorder(p->lch);              // 中根遍历左子树
         cout<<p->data<<" ";           // 访问根结点
         inorder(p->rch);              // 中根遍历右子树
       }
}
void BiTree::postorder(NodeType *p)        //后序递归遍历
{   if(p != NULL)
    {   postorder(p->lch);  /* 后根遍历左子树 */
        postorder(p->rch); /* 后根遍历右子树 */
        cout<<p->data<<" ";/* 访问根结点 */
    }
}
void main()
{
BiTree b;
b.creat();
cout<<"前序"endl;
b.preorder();
cout<<endl;
cout<<"中序"endl;
b.inorder();
cout<<endl;
cout<<"后序"endl;
b.postorder();
cout<<endl;
}