Biegral Blog

本文要点：

二叉树三种遍历方式（前序、中序、后序）的非递归实现

ps：递归方法实现：递归法实现二叉树的创建与遍历

非递归的实现需要借助栈！！

前序：

首先需要判断是否是空树，是空返回；否则从根部一直向树的左子树方遍历，遍历一个访问一个，并且将其压入栈。当树不为空，并且栈不为空时，说明栈里仍有元素可访问。

	void _PrevOrder_NonR(Node* root)	//非递归--前序
	{
		if(root == NULL)
			return ;
		Node* cur = root;
		stack<Node*> s;
		while (cur || !s.empty())		//cur != NULL说明仍然有子树可以被遍历
							//!s.empty()  说明栈不为空时可以有数据被访问
		{
			while (cur)
			{
				cout<<cur->_data<<" ";
				s.push(cur);
				cur = cur->_left;
			}

			Node* top = s.top();
			s.pop();
			cur = top->_right;	//访问当前根节点的右子树
		}
		cout<<endl;
	}

中序的过程与前序相似，只是访问数据的时间不同。中序是先入栈再访问，即当左子树入栈以后才访问

	void _InOrder_N0nR(Node* root)		//非递归--中序
	{
		if(root == NULL)
			return ;
		Node* cur = root;
		stack<Node*> s;
		while(cur || !s.empty())
		{
			while(cur)
			{
				s.push(cur);
				cur = cur->_left;
			}

			Node* top = s.top();	//此时栈顶存的是当前子树的根节点
			cout<<top->_data<<" ";
			s.pop();
			cur = top->_right;	//将右子树作为左子树的子树来遍历
		}
		cout<<endl;
	}

三种非递归遍历中，后序遍历是比较难理解的。后序遍历必须保证左子树和右子树都访问完以后才能访问根节点，而能访问根节点的可能是有两种：右子树已经被访问或者当前根节点的右子树为NULL。因此，就需要一个标记位pos，当当前根节点右子树和pos相等时，说明已经可以访问该根节点了。

void _PostOrder_NonR(Node* root)	//非递归--后序
	{
		Node* cur = root;
		Node* pos = root;
		stack<Node*> s;
		while (cur || !s.empty())
		{
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}

			Node* top = s.top();

			if (top->_right == NULL || top->_right == pos)
				//top存的是当前的根节点，当top的右子树为空或者top的右子树为pos，说明右子树已经遍历过，
				//这时就可以访问当前的根节点了
			{
				cout<<top->_data<<" ";
				pos = top;
				s.pop();
			}
			else
			{
				cur = top->_right;
			}
		}
		cout<<endl;
	}