#include
using namespace std;
struct binode
{
int data;
binode *lchild,*rchild;
};
binode *Q[100],*S[100];
struct element
{
binode *ptr;
int flag;
};
class bitree
{
public:
void create_bitree(){root=creat(root);}
void delete_bitree(){release(root);}
void preorder(){preorder(root);}
void inorder(){inorder(root);}
void postorder(){postorder(root);}
void leverorder();
private:
binode *root;
binode *creat(binode *bt);
void release(binode *bt);
void preorder(binode *bt);
void inorder(binode *bt);
void postorder(binode *bt);
};
binode *bitree::creat(binode *bt)
{
int ch;
cin>>ch;
if(ch==-1)
{
bt=NULL;
}
else
{
bt=new binode;
bt->data=ch;
bt->lchild=creat(bt->lchild);
bt->rchild=creat(bt->rchild);
}
return bt;
}
void bitree::preorder(binode *bt)
{
int top=-1;
while(bt!=NULL||top!=-1)
{
while(bt!=NULL)
{
cout<data;
S[++top]=bt;
bt=bt->lchild;
}
if(top!=-1)
{
bt=S[top--];
bt=bt->rchild;
}
}
}
void bitree::inorder(binode *bt)
{
int top=-1;
while(bt!=NULL||top!=-1)
{
while(bt!=NULL)
{
S[++top]=bt;
bt=bt->lchild;
}
if(top!=-1)
{
bt=S[top--];
cout<data;
bt=bt->rchild;
}
}
}
void bitree::postorder(binode *bt)
{
int top=-1;
element H[30];
while(bt!=NULL||top!=-1)
{
while(bt!=NULL)
{
top++;
H[top].ptr=bt;
H[top].flag=1;
bt=bt->lchild;
}
while(top!=-1&&H[top].flag==2)
{
bt=H[top].ptr;
cout<data;
top--;
}
if(top!=-1)
{
H[top].flag=2;
bt=H[top].ptr->rchild;
}
}
}
void bitree::leverorder()
{
int front=-1,rear=-1;
binode *q;
if(root==NULL)
{
return;
}
Q[++rear]=root;
while(front!=rear)
{
q=Q[++front];
cout<data;
if(q->lchild!=NULL)
{
Q[++rear]=q->lchild;
}
if(q->rchild!=NULL)
{
Q[++rear]=q->rchild;
}
}
}
void bitree::release(binode *bt)
{
if(bt!=NULL)
{
release(bt->lchild);
release(bt->rchild);
delete bt;
}
}
int main()
{
bitree tree1;
tree1.create_bitree();
cout<<endl;
tree1.preorder();
cout<<endl;
tree1.inorder();
cout<<endl;
tree1.postorder();
/*cout<<endl;
tree1.leverorder();
cout<<endl;
tree1.delete_bitree();
cout<<"over"<<endl;
tree1.inorder();
*/
return 0;
}