[数据结构与算法]数据结构与算法——非递归实现二叉树的遍历

非递归实现二叉树的遍历

树的遍历可以用递归实现，程序中递归的调用就是保存函数的信息在栈中。一般情况下，能用递归解决的问题都可以用栈解决，只是递归更符合人们的思维方式，代码相对而言也更简单，但不能说明递归比栈的方式更快、更节省空间，因为在递归过程中都是操作系统来帮助用栈实现存储信息

非递归实现二叉树的后序遍历

对于后序遍历，应该在父节点入栈时就把右左孩子一并入栈。在父节点出栈时，应该判断右左孩子是否已经遍历过（是否执行过入栈），那么就应该有一个标记来判断孩子是否遍历过

定义一个适用于这个算法的结构体：

typedef struct stackTreeNode
{
	BTree treeNode;
	int flag;
}* pSTree;

结构体中，flag为标志位，0表示左右孩子没有遍历，2表示左右孩子遍历完，具体实现如下：

void lastOrder(BTree root)
{
	stack<pSTree> stackTree;
	pStree = new stackTreeNode();
	sTree->treeNode = root;
	sTree->flag = 0;
	stackTree.push(sTree);

	while (!stackTree.empty())
	{
		pSTree tmptree = stackTree.top();
		if (tmptree->flag == 2)
		{
			cout << tmptree->treeNode->data << " ";
			stackTree.pop();
		}
		else
		{
			if (tmptree->treeNode->rchild)
			{
				pSTree sTree = new stackTreeNode();
				sTree->treeNode = tmptree->treeNode->rchild;
				sTree->flag = 0;
				stackTree.push(sTree);
			}
			tmptree->flag++;
			if (tmptree->treeNode->lchild)
			{
				pSTree sTree = new stackTreeNode();
				sTree->treeNode = tmptree->treeNode->lchild;
				sTree->flag = 0;
				stackTree.push(sTree);
			}
			tmptree->flag++;
		}
	}
}

非递归实现二叉树的前序遍历

1. 将二叉树的根节点作为当前节点
2. 若当前节点非空，则先访问该节点，并将该节点进栈，再将其左孩子节点作为当前节点，重复步骤2，直到当前节点为空为止
3. 若栈非空，则栈顶节点出栈，并将当前节点的右孩子节点作为当前节点
4. 重复步骤2和3，直到栈为空且当前节点为空为止

void preOrder(BTree root)
{
	stack<BTree> s;
	BTree p = root;

	while (p != nullptr || !s.empty())
	{
		while (p != nullptr)
		{
			cout << p->data << " ";
			s.push(p);
			p = p->lchild;
		}

		if (!s.empty())
		{
			p = s.pop();
			p = p->rchild;
		}
	}
}

非递归实现二叉树的中序遍历

1. 将二叉树的根节点作为当前节点
2. 若当前节点非空，则将该节点进栈并将其左孩子节点作为当前节点，重复步骤2，直到当前节点为空为止
3. 若栈非空，则将栈顶节点出栈并作为当前节点，接着访问当前节点，再将当前节点的右孩子作为当前节点
4. 重复步骤2和3，直到栈为空且当前节点为空为止

void InOrder(BTree root)
{
	stack<BTree> s;
	p = root;

	while (p != nullptr || !s.empty())
	{
		while (p!=nullptr)
		{
			s.push(p);
			p = p->lchild;
		}

		if (!s.empty())
		{
			p = s.pop();
			cout << p->data << " ";
			p = p->rchild;
		}
	}
}