二叉链表存储的二叉树
输入格式
输入只有一行，包含一个字符串S，用来建立二叉树。保证S为合法的二叉树先序遍历字符串，节点内容只有大写字母，且S的长度不超过100。
输出格式
共有三行，每一行包含一串字符，表示分别按先序、中序（递归）、中序（非递归）得出的节点内容，每个字母后输出一个空格。请注意行尾输出换行。
样例输入
ABC DE G F
样例输出
A B C D E G F
C B E G D F A
C B E G D F A

#include
using namespace std;
//二叉链表存储的二叉树
struct treenode{char data;treenode*leftchild;treenode*rightchild;treenode(char ch):data(ch),leftchild(NULL),rightchild(NULL){}
};
treenode * s[100];
//用来中序遍历的栈 
//扩展树建立二叉树 
treenode*create(treenode*root){char ch;//直接用cin的话会导致把空格误认成分隔符ch = getchar();//读取空格 
//	cin>>ch;if(ch==' '){//空子树 root=NULL;}else{root=new treenode(ch);root->leftchild=create(root->leftchild);root->rightchild=create(root->rightchild);}return root;
}
//前序遍历
void PreOrder(treenode*root){if(root==NULL){return;}cout<data<<" ";PreOrder(root->leftchild);PreOrder(root->rightchild);
}
//中序遍历
//递归 
void InOrder(treenode*root){if(root==NULL){return;}InOrder(root->leftchild);cout<data<<" ";InOrder(root->rightchild);	
}
//中序遍历
//非递归，栈的思想 
void InOrder1(treenode*root){int top=-1;while(root!=NULL || top!=-1){//当根指针不为空时循环 while(root!=NULL){s[++top]=root;//入栈root=root->leftchild;//继续向左遍历 }//如果栈s不为空 if(top!=-1){root=s[top--];cout<data<<" ";//返回到上一层 root=root->rightchild;//遍历右子树 }}
} 
int main(){string str;//字符串里的空格是为了标志子树为空的//使用的是扩展树的概念，因此才能仅根据前序遍历就能建出一棵树 treenode*root=NULL;root=create(root);PreOrder(root);cout<