二叉樹遍歷的非遞歸實現(xiàn)

二叉樹的遍歷可以使用遞歸的方式實現(xiàn)，并且代碼非常簡單。而遞歸實際就是函數(shù)反復(fù)的調(diào)用本身，在棧上反復(fù)壓棧。所以我們可以用棧來模擬實現(xiàn)遞歸。

1.前序遍歷

  （1）棧是后進(jìn)先出的特點，所以無條件的把棧的根節(jié)點入棧，在把棧頂元素輸出之后依次把右孩子，左孩子壓入棧中。

代碼如下：

void _PrevOrder(Node * root)
	{
		stack<Node*> s;
		if (root == NULL)
		{
			return;
		}

		s.push(root);//將第一個元素入棧

		while (!s.empty())//當(dāng)棧不為空時
		{
			root = s.top();
			cout << root->_data << "->";//打印節(jié)點
			s.pop();
			//棧的特點，后進(jìn)先出，所以，先壓右子樹
			if (root->_right)//遍歷右子樹
			{
				s.push(root->_right);
			}
			if (root->_left)//遍歷左子樹
			{
				s.push(root->_left);
			}
		}
	}

2.中序遍歷

  （1）一直入棧，一直到二叉樹的最左邊最下邊的節(jié)點。

  （2）按照中序遍歷的特點：左子樹->根節(jié)點->右子樹，輸出棧頂?shù)脑兀⑶覐棾?，必須保留該?jié)點的指針。

  （3）此時，該判斷此節(jié)點的右子樹：

            a.右子樹為NULL，返回到棧頂；

            b.右子樹不為NULL，把該節(jié)點當(dāng)根節(jié)點，重復(fù)（1）（2）（3）......  

代碼如下：

	void _InOrder(Node * root)
	{
		if (root == NULL)
		{
			return;
		}
		Node * cur = root;
		stack<Node *> s;
		while (cur || !s.empty())
		{
			while (cur)//當(dāng)沒有左子樹時，停止入棧
			{
				s.push(cur);
				cur = cur->_left;
			}
			Node * top = s.top();//保留棧頂指針，判斷是否有右子樹
			cout << top->_data << "->";
			s.pop();

			if (top->_right == NULL)//沒有右子樹時，不需要壓棧
			{
				cur = NULL;
			}
			else//當(dāng)存在右子樹時，把右子樹的根節(jié)點壓入棧中，循環(huán)去判斷該節(jié)點的左子樹是否存在
			{
				cur = top->_right;
			}
		}
	}

3.后序遍歷

  （1）一直入棧，一直到二叉樹的最左邊最下邊的節(jié)點。

  （2）按照后序遍歷的特點：左子樹->右子樹->根節(jié)點，輸出棧頂?shù)脑?，并且彈出，必須保留該?jié)點的指針。

  （3）此時，該判斷此節(jié)點的右子樹，如果存在右子樹，把該節(jié)點當(dāng)作根節(jié)點，重復(fù)（1）（2）（3）

代碼如下：

	void _PostOrder(Node * root)
	{
		if (root == NULL)
		{
			return;
		}
		Node * cur = root;
		Node * prev = NULL;
		stack<Node *> s;

		while (cur || !s.empty())
		{
			while (cur)//當(dāng)沒有左子樹時，停止入棧
			{
				s.push(cur);
				cur = cur->_left;
			}

			Node * top = s.top();//保留棧頂指針，判斷它的右子樹是否為空或者已經(jīng)出棧
			if (top->_right == NULL || top->_right == prev)
			{
				cout << top->_data << "->";
				s.pop();
				prev = top;//保留出棧元素的指針
				cur = NULL;
			}
			else//當(dāng)存在右子樹時，把右子樹的根節(jié)點壓入棧中，循環(huán)去判斷該節(jié)點的左子樹是否存在
			{
				cur = top->_right;
			}
		}
	}