二叉树的非递归遍历

二叉树的遍历本质上其实就是入栈出栈的问题，二叉树的前序，中序，后序遍历都需要栈这个结构。

二叉树的建立

首先我们使用#创建法，建立一个二叉树代码如下：

BinaryNode* createTree(char* arr)
{
	static int i = 0;//设置一个静态变量，保证递归时能够顺利读取arr中的数据
	//这个i值可以是全局变量，也可用函数参数传入
	if (*(arr + i) == '#' || *(arr + i) == '\0')
	{
		if (*(arr + i) == '\0')
			return NULL;
		i++;
		return NULL;
	}
	BinaryNode* root = (BinaryNode*)malloc(sizeof(BinaryNode));
	root->ch = *(arr + i);
	i++;
	root->lchild = createTree(arr);
	root->rchild = createTree(arr);

	return root;
}

上图为所建立的二叉树结构。
先序遍历：先序遍历是先输出根节点，再输出左子树，最后输出右子树。上图的先序遍历结果就是：ABCDEF

中序遍历：中序遍历是先输出左子树，再输出根节点，最后输出右子树。上图的中序遍历结果就是：CBDAEF

后序遍历：后序遍历是先输出左子树，再输出右子树，最后输出根节点。上图的后序遍历结果就是：CDBFEA

二叉树的三种遍历

先序遍历
代码如下：

void Recur_Node(BinaryNode* root)
{
	if (root == NULL)
		return;
	BinaryNode* p = NULL;//保存从栈中弹出的树节点
	ListNode* temp = Init_List();//栈的初始化
	Push_Stack(temp,root);//首先让二叉树的头节点入栈
	while (temp->next != NULL)//判断栈是否为空
	{
		p = Pop_stack(temp);//将栈中元素取出并打印
		printf("%c", p->ch);
		if (p->rchild != NULL)
		{
			Push_Stack(temp, p->rchild);//先让右子树入栈
		}
		if (p->lchild != NULL)
		{
			Push_Stack(temp, p->lchild);//后让左子树入栈，使得首先遍历
			//的为左子树，下来为中间子树，最后为右子树
		}
	}
	free(temp);//释放栈
}

总的来说就是先让二叉树的头节点入栈，在循环中把栈是否为空作为二叉树遍历的终点，循环中先让右子树入栈后让左子树入栈，以此来满足先序遍历的条件。当栈为空时便意味着树已经遍历完成。
这个先序遍历和层次遍历代码极其相似，只需要改变一下入队顺序，并将栈结构改为队列便能进行层次遍历。

中序遍历
代码如下：

void InOrderNode(BinaryNode* root)
{
	if (root == NULL)
		return;
	ListNode* temp = Init_List();//初始化栈
	while (root != NULL || temp->next != NULL)//树节点不为空或栈不为空
	{
		while (root != NULL)
		{
			Push_Stack(temp,root);
			root = root->lchild;//让树节点走至左子树的最后一个NULL节点
		}
		if (!empty_stack(temp))//判断栈是否为空
		{
			root = Pop_stack(temp);//将栈中的一个元素取出，并赋值给root
			printf("%c", root->ch);
			root = root->rchild;//将右子树赋值给root
		}

	}
}

中序遍历便是先将所有左子树的节点入栈，之后，判断栈是否为空，不为空，则将栈中取出一节点，打印，并将此节点的右子树赋值给root。如此便能达到遍历左子树-》中间子树-》右子树。而当栈为空且树节点到了右子树的NULL处，便说明树已经遍历完成。

后序遍历
代码如下：

void PostOrderNode(BinaryNode* root)
{
	if (root == NULL)
		return;
	BinaryNode* p = NULL;//用于保存遍历过的节点
	BinaryNode* s = NULL;//用于保存栈顶元素
	ListNode* temp = Init_List();//栈的初始化
	do
	{
		while (root != NULL)
		{
			Push_Stack(temp, root);
			root = root->lchild;//将二叉树的所有左子树节点入栈
		}
		s = Get_Top(temp);//将栈顶元素赋值给s
		if (s->rchild == NULL || p == s->rchild)//当满足s的右子树为空
		//或者s的右节点为已遍历过的节点，输出s节点的值
		{
			Pop_stack(temp);
			printf("%c", s->ch);
			p = s;//p保存已遍历的s节点
		}
		else
		{
			root = s->rchild;//若未满足条件，则让其走向右子树
		}
	} while (temp->next != NULL);//栈是否为空
}

后序遍历方法有很多种，今天我写的是一种比较简单的方法。首先定义两个变量用来保存遍历过的节点和保存栈顶元素，利用这两个变量来判断是否遍历过右子树，以此来决定是否遍历中间子树。由于最后遍历中间子树的原因，所以只能利用栈为空的条件来做判断。

验证结果

代码验证过后也没有问题。