// Day07.cpp : 二叉树的遍历

#include "pch.h"
#include <stdio.h>
#include <stdlib.h>
#define TElemType char

int top = - 1;	// top变量时刻表示栈顶元素所在的位置

// 定义节点的结构体
typedef struct BitNode
{
	TElemType data;	// 数据域
	struct BitNode * lchild, *rchild;		// 左右孩子指针
}BiTNode,*BiTree;


// 构造一棵二叉树
void CreateBiTree(BiTree *T)
{
	*T = (BitNode *)malloc(sizeof(BiTNode));	// 根节点申请内存空间
	(*T)->data = 'A';
	(*T)->lchild = (BitNode*)malloc(sizeof(BiTNode));	// 左孩子指针申请内存
	(*T)->rchild = (BitNode*)malloc(sizeof(BiTNode));	// 右孩子指针申请内存

	(*T)->lchild->data = 'B';
	(*T)->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
	(*T)->lchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));

	(*T)->lchild->rchild->data = 'C';
	(*T)->lchild->rchild->lchild = NULL;
	(*T)->lchild->rchild->rchild = NULL;

	(*T)->rchild->data = 'D';
	(*T)->rchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));

	(*T)->rchild->lchild->data = 'E';
	(*T)->rchild->lchild->lchild = NULL;
	(*T)->rchild->lchild->rchild = NULL;
	(*T)->rchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));

	(*T)->rchild->rchild->data = 'F';
	(*T)->rchild->rchild->lchild = NULL;
	(*T)->rchild->rchild->rchild = NULL;

	(*T)->lchild->lchild->data = 'G';
	(*T)->lchild->lchild->rchild = NULL;
	(*T)->lchild->lchild->lchild = NULL;
}


// 前序遍历使用入栈函数
void Push(BiTNode **a, BiTNode *elem)
{
	a[++top] = elem;
}


// 前序出栈
void Pop()
{
	if (top == -1)
	{
		return;
	}
	top--;
}


// 获取栈顶元素
BiTNode *GetTop(BiTNode **a)
{
	return a[top];
}


// 节点数据输出
void PrintElem(BiTNode *elem)
{
	printf("%c  ", elem->data);
}


// 先序遍历递归算法
void PreOrderTraverse(BiTNode* tree)
{
	BiTNode *a[20];
	BiTNode *p;
	Push(a, tree);

	while (top != -1)
	{
		p = GetTop(a);
		Pop();
		while (p)
		{
			PrintElem(p);
			if (p->rchild)
			{
				Push(a, p->rchild);
			}
			p = p->lchild;
		}
	}
}

// 中序遍历递归算法
void InOrderTraverse(BiTree tree)
{
	BiTNode *a[20];			// 定义一个顺序栈
	BiTNode *p;				// 临时指针
	Push(a, tree);			// 根结点进栈
	while (top != -1)		// top !=-1说明栈内不为空，程序继续执行
	{
		while ((p = GetTop(a)) && p)	// 取栈顶元素，且不能为NULL
		{
			Push(a, p->lchild);			// 将该结点的左孩子进栈，如果没有左孩子，NULL进栈
		}
		Pop();						// 跳出循环，栈顶元素肯定为NULL，将NULL弹栈
		if (top != -1) 
		{
			p = GetTop(a);			// 取栈顶元素
			Pop();
			PrintElem(p);
			Push(a, p->rchild);		// 将p指向结点的右孩子进栈
		}

	}
}


// 后序遍历非递归算法
typedef struct SNode 
{
	BiTree p;
	int tag;
}SNode;

// 后序遍历使用进栈函数
void postpush(SNode *a, SNode sdata) 
{
	a[++top] = sdata;
}

//后序遍历
void  PostOrderTraverse(BiTree Tree) 
{
	SNode a[29];
	BiTNode *p;
	int tag;
	SNode sdata;
	p = Tree;

	while (p || top != -1)
	{
		while (p) 
		{
			sdata.p = p;
			sdata.tag = 0;	// 由于遍历是左孩子，设置标志位为0
			postpush(a, sdata);		// 入栈 
			p = p->lchild;		// 以该 结点为根结点，遍历左孩子
		}
		sdata = a[top];
		Pop();
		p = sdata.p;
		tag = sdata.tag;

		if (tag == 0)			// tag==0 说明该 结点还没有遍历它的右孩子
		{
			sdata.p = p;
			sdata.tag = 1;
			postpush(a, sdata);	// 更改结点标志位，重新入栈
			p = p->rchild;		// 该结点右孩子为根结点，重新循环
		}
		else
		{
			PrintElem(p);
			p = NULL;
		}
	}
}


int main()
{
	BiTree Tree;
	CreateBiTree(&Tree);

	printf("二叉树前序遍历结果为(DLR)：\n");
	PreOrderTraverse(Tree);

	printf("\n二叉树中序遍历结果为(LDR)：\n");
	InOrderTraverse(Tree);

	printf("\n二叉树后序遍历结果为(LRD)：\n");
	PostOrderTraverse(Tree);

	return 0;
}