#include <iostream>
using namespace std;
struct LinkList
{
char data; /*建立二叉树 */
LinkList *lchild;
LinkList *rchild;
};
LinkList* CreateLinkList()
{ /* 创建链表，其实是个先序遍历的形式。之所以不用指针传递参数是因为实参与形参的关系，在这里用指针传参会弄巧成拙*/
char a;
LinkList *q;
cin>>a;
if(a=='#')
q=NULL; /*这里的模式是如果输入字符为#，意味着不存在该结点。递归里的自身函数调用其实是层次上的关系，真正的核心操作是那些非调用的函数操作*/
else
{
q=new LinkList;
q->data=a;
q->lchild=CreateLinkList();
q->rchild=CreateLinkList();
}
return q;
}
void Firstbianli(LinkList *q) /*先序遍历。如果该结点不存在，返回。如果存在，就输出该结点数据，之后向左子树、右子树遍历。*/
{
if(q==NULL)
return;
else
{
cout<<q->data;
Firstbianli(q->lchild); /*遍历包括两个核心操作，一个是次序、一个是访问。自身函数的调用主要是次序，而非自身函数调用的操作就是访问。*/
Firstbianli(q->rchild);
}
}
void Midbianli(LinkList *q) /*中序遍历*/
{
if(q==NULL)
return;
else
{
Midbianli(q->lchild);
cout<<q->data; /*无论什么遍历，其实遍历次序是一样的，都是先序遍历，然而不同的是访问次序。*/
Midbianli(q->rchild);
}
}
int main()
{
LinkList *q;
q=NULL;
q=CreateLinkList();
Firstbianli(q);
cout<<'\n';
Midbianli(q);
return 0;
}
