#include <stdio.h>
#include <stdlib.h>
#define MAX 100
typedef struct node{
	char data;
	struct node *lchild,*rchild;
}BiTNode,*BiTree;

int i = 0;
//初始化建立二叉树
void InitTree(BiTree &T,char *s)
{
	if(s[i] == '\0') return;
	char ch = s[i++];
	if(ch == '#') T=NULL;
	else 
	{
		T = (BiTNode *)malloc(sizeof(BiTNode));
		T->data = ch;	//生成树根节点
		InitTree(T->lchild,s);	//构造左子树
		InitTree(T->rchild,s);	//构造右子树
	}
}

//递归中序遍历
void InOrder(BiTree T)
{
	if(T)
	{
		InOrder(T->lchild);
		printf("%c ",T->data);
		InOrder(T->rchild);
	}
}

//非递归中序遍历
void In_Order(BiTree T)
{
	BiTNode *s[MAX],*p;
	int top = -1;
	p = T;
	while(top != -1 || p)
	{
		while(p)
		{
			s[++top] = p;
			p = p->lchild;
		}
		if(top != -1)
		{
			p = s[top--];
			printf("%c ",p->data);
			p = p->rchild;
		}
	}
}

int main()
{
	char s[100];
	while(scanf("%s",s) != EOF)
	{
		i = 0;
		BiTree T;
		InitTree(T,s);
		InOrder...