#include <iostream>
#include <queue>
using namespace std;
struct Node {
int data;
Node * leftchild;
Node * rightsib;
};
Node * Create()
{
Node * root =NULL;
queue<Node*> q;
int temp;
cout<<"请输入根节点数据:\n";
cin>>temp;
root=new Node ;
root ->data=temp;
root->leftchild=root->rightsib=NULL;q.push(root);
int cmd,data;
cout<<"请按照层序依次输入各子节点数据（root data 格式，如2 3表示根节点数据是2,孩子节点数据是3）:\n";
cin>>cmd>>data;
Node * p;
while(!(cmd==-1&&data==-1))
{
while(q.front()->data!=cmd)
q.pop();
Node * t=q.front();
if(t->leftchild==NULL)
{
p=new Node ;
p->data=data;
p->leftchild=p->rightsib=NULL;
t->leftchild=p;q.push(p);
}
else
{
p=t->leftchild;
while(p->rightsib)
p=p->rightsib;
p->rightsib=new Node;
p=p->rightsib;
p->data=data;
p->leftchild=p->rightsib=NULL;
q.push(p);
}
cin>>cmd>>data;
}
return root;
}
void PostOrder(Node * root)
{
//树的后序遍历
if(root==NULL)
return;
PostOrder(root->leftchild);
cout<<root->data<<" ";
PostOrder(root->rightsib);
}
void main()
{
Node * root;
root= Create();
PostOrder(root);
::system("pause");
}
