#define _CRT_SECURE_NO_WARNINGS
#define Max 64
#include<stdio.h>
#include<stdlib.h>


//二叉树的定义
typedef struct node
{
	char data;
	int visit;
	struct node* lchild;
	struct node* rchild;
}bitree;


//栈的定义
typedef struct
{
	bitree* data[Max];
	int top;
}seqstack;


//创建二叉树
bitree* CREATREE()
{
	bitree* Q[50];
	char ch;
	int front, rear;
	bitree* root, * s;
	root = NULL;//置空二叉树
	front = 1; rear = 0;
	ch = getchar();
	while (ch != '#')//#是结束字符
	{
		s = NULL;
		if (ch != '@')//@表示虚结点，不是虚结点建立新结点
		{
			s = (bitree*)malloc(sizeof(bitree));
			s->data = ch;
			s->lchild = NULL;
			s->rchild = NULL;
		}
		rear++;
		Q[rear] = s;//虚结点指针NULL或新结点地址入队
		if (rear == 1)
		{
			root = s;//输入的第一个结点为根结点
			s->visit = 0;
		}
		else
		{
			if (s && Q[front])//孩子和双亲都不是虚结点
			{
				if (rear % 2 == 0)
				{
					Q[front]->lchild = s;//rear为偶数，新结点是左孩子
					s->visit = 0;
				}
				else
				{
					Q[front]->rchild = s;//奇数是新结点是右孩子
					s->visit = 0;
				}
			}
			if (rear % 2 == 1)
				front++;//两个孩子均已处理完毕，出队列
		}
		ch = getchar();//输入下一个字符
	}
	return root;
}


//后序遍历非递归算法
void POSTORDER2(bitree* t)
{
	seqstack* s;
	s = (seqstack*)malloc(sizeof(seqstack));
	s->top = 0;
	s->data[s->top] = t;
	while (s->top != -1)
	{
		if (s->data[s->top]->lchild != NULL && s->data[s->top]->lchild->visit == 0)
		{
			s->data[s->top + 1] = s->data[s->top]->lchild;
			s->top++;
		}
		else if (s->data[s->top]->rchild != NULL && s->data[s->top]->rchild->visit == 0)
		{
			s->data[s->top + 1] = s->data[s->top]->rchild;
			s->top++;
		}
		else if (s->data[s->top]->visit == 0)
		{
			printf("%c ", s->data[s->top]->data);
			s->data[s->top]->visit = 1;
			s->top--;
		}
	}
}


//打印祖先
void Printfather(bitree* t,char x)
{
	seqstack* s;
	s = (seqstack*)malloc(sizeof(seqstack));
	s->top = 0;
	s->data[s->top] = t;
	while (s->top != -1)
	{
		if (s->data[s->top]->data == x)
		{
			//打印栈
			int tem = 0;
			tem = s->top;
			while (tem != 0)
			{
				printf("%c ", s->data[tem-1]->data);
				tem--;
			}
		}
		if (s->data[s->top]->lchild != NULL && s->data[s->top]->lchild->visit == 0)
		{
			s->data[s->top + 1] = s->data[s->top]->lchild;
			s->top++;
		}
		else if (s->data[s->top]->rchild != NULL && s->data[s->top]->rchild->visit == 0)
		{
			s->data[s->top + 1] = s->data[s->top]->rchild;
			s->top++;
		}
		else if (s->data[s->top]->visit == 0)
		{
			//printf("%c ", s->data[s->top]->data);
			s->data[s->top]->visit = 1;
			s->top--;
		}
	}
}


int main()
{
	bitree* t = CREATREE();
	Printfather(t, 'D');
}