[数据结构与算法]二叉树深度优先遍历（非递归）

二叉树深度优先遍历（非递归）

1. 先序遍历非递归化

• 从根结点开始入栈一个元素
• 不停的执行以下操作：
  • 如果栈不空，就出栈一个元素，并对其进行访问，并访问其左右孩子
  • 若左右孩子存在，则依次入栈，右孩子先入栈，左孩子后入栈
  • 若没有左右孩子则继续出栈一个元素
• 如果进行出栈操作后栈为空，表明遍历结束

typedef struct BTNode
{
	int data;
	struct BTNode* lChild;		//指向其左孩子的指针
	struct BTNode* rChild;		//指向其右孩子的指针
}BTNode;
//参数列表为根结点的指针
void preorder(BTNode *bt)
{
	//首先判断根结点是否为空
	if (bt != NULL)
	{
		//建立一个栈
		BTNode *Stack[maxSize];
		int top = -1;

		BTNode *p = NULL;
		Stack[++top] = bt;
		while (top != -1)
		{
			//先出栈一个元素，并对其进行访问
			p = Stack[top--];
			Visit(p);
			//监测其左右孩子是否存在
			//如果存在则入栈
			//先入栈右孩子，再入栈左孩子
			if (p->rChild != NULL)
				Stack[++top] = p->rChild;
			if (p->lChild != NULL)
				Stack[++top] = p->lChild;
		}
	}
}

2. 后序遍历非递归化

• 先序遍历：先访问根结点，然后先遍历左子树，最后遍历右子树

• 后序遍历：先后序遍历左子树，然后后续遍历右子树，最后访问根结点

• 逆后续遍历序列：先遍历根，再遍历右子树，最后遍历左子树

//后序遍历序列
typedef struct BTNode
{
	int data;
	struct BTNode* lChild;		//指向其左孩子的指针
	struct BTNode* rChild;		//指向其右孩子的指针
}BTNode;
//参数列表为根结点的指针
void preorder2(BTNode *bt)
{
	//首先判断根结点是否为空
	if (bt != NULL)
	{
		//建立两个栈,一个是辅助栈，一个是将结果序列逆序的栈
		BTNode *Stack1[maxSize];
		int top1 = -1;

		BTNode *Stack2[maxSize];
		int top2 = -1;

		BTNode *p = NULL;
		Stack1[++top1] = bt;
		while (top1 != -1)
		{
			//先出栈一个元素，并对其进行访问
			p = Stack1[top1--];
			Stack2[++top2] = p;
			Visit(p);
			//监测其左右孩子是否存在
			//如果存在则入栈
			//先入栈左孩子，再入栈右孩子
			if (p->lChild != NULL)
				Stack1[++top1] = p->lChild;
			if (p->rChild != NULL)
				Stack1[++top1] = p->rChild;
		}
		while (top2 != -1)
		{
			p = Stack2[top2--];
			Visit(p);
		}
	}
}

3. 中序遍历非递归化

• 中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树

• 从根结点开始入栈一个元素

• 从根结点开始访问其左分支，边访问边将其历经的结点入栈

• 直到不能继续向左走为止，此时出栈一个结点，并访问

• 从这个结点开始，先往右访问一次，然后继续上述操作

//后序遍历
void ino(BTNode *bt)
{
	if (bt != NULL)
	{
		BTNode *Stack[maxSize];
		int top = -1;
		BTNode *p = NULL;
        
		p = bt;
		while (top != -1||p!=NULL)	//执行完if语句以后可能栈空，但如果p的右子树存在，即p!=NULL(执行完if语句后p = p->rChild)，还应该继续遍历
		{
			while (p != NULL)
			{
				Stack[++top] = p;
				p = p->lChild;
			}

			if (top != -1)
			{
				p = Stack[top--];
				Visit(p);
				p = p->rChild;
			}
		}
	}
}