#include <stdio.h>
#include <stdlib.h>

struct node 
{
	char data;
	struct node *left, *right;
};

struct item 
{
	struct node *data; // элемент списка -- узел дерева
	struct item *next;
};

struct item *head = NULL, *tail = NULL;

void enqueue(struct node *p)
{
	struct item *n = malloc(sizeof(struct item));
	n->data = p;
	n->next = NULL;
	if (tail)
		tail->next = n;
	else
		head = n;
	tail = n;
}

struct node *dequeue(void)
{
	struct node *result = head->data;
	struct item *p = head->next;
	free(head);
	head = p;
	if (!head)
		tail = NULL;
	return result;
}

int empty(void)
{
	return (!head);
}

void print(struct node *root)
{
	if (!root)
	{
		putchar('x');
		return;
	}
	putchar('(');
	putchar(root->data);
	print(root->left);
	print(root->right);
	putchar(')');
}

struct node *read(void)
{
	int c;
	struct node *p;

	c = getchar();

	if (c == 'x')
	{
		return NULL;
	}
	// если ввод корректен, то c обязано быть '('
	
	p = malloc(sizeof(struct node));
	p->data = getchar();

	p->left = read();
	p->right = read();

	getchar(); // "съели" ')'

	return p;
}

void prefix(struct node *root)
{
	if (!root)
		return;
	putchar(root->data);
	prefix(root->left);
	prefix(root->right);
}

void infix(struct node *root)
{
	if (!root)
		return;
	infix(root->left);
	putchar(root->data);
	infix(root->right);
}

void postfix(struct node *root)
{
	if (!root)
		return;
	postfix(root->left);
	postfix(root->right);
	putchar(root->data);
}

void del(struct node *root)
{
	if (!root)
		return;
	del(root->left);
	del(root->right);
	free(root);
}

void breadth(struct node *root)
{
	if (!root)
		return;
	enqueue(root);
	while (!empty())
	{
		struct node *p = dequeue();
		putchar(p->data);
		if (p->left)
			enqueue(p->left);
		if (p->right)
			enqueue(p->right);
	}
}

int main()
{
	struct node *root;

	root = read();

	print(root);
	putchar('\n');

	printf("Префиксный обход: ");
	prefix(root);
	putchar('\n');

	printf("Инфиксный обход: ");
	infix(root);
	putchar('\n');

	printf("Постфиксный обход: ");
	postfix(root);
	putchar('\n');

	printf("Обход в ширину: ");
	breadth(root);
	putchar('\n');

	del(root); /* освобождение памяти, занятой деревом */

	return 0;
}