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

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

創(chuàng)新互聯(lián)專注于企業(yè)營銷型網(wǎng)站建設、網(wǎng)站重做改版、雁塔網(wǎng)站定制設計、自適應品牌網(wǎng)站建設、成都h5網(wǎng)站建設、商城網(wǎng)站定制開發(fā)、集團公司官網(wǎng)建設、成都外貿(mào)網(wǎng)站建設公司、高端網(wǎng)站制作、響應式網(wǎng)頁設計等建站業(yè)務，價格優(yōu)惠性價比高，為雁塔等各大城市提供網(wǎng)站開發(fā)制作服務。

1.前序遍歷

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

代碼如下：

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

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

		while (!s.empty())//當棧不為空時
		{
			root = s.top();
			cout << root->_data << "->";//打印節(jié)點
			s.pop();
			//棧的特點，后進先出，所以，先壓右子樹
			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é)點當根節(jié)點，重復（1）（2）（3）......

代碼如下：

	void _InOrder(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();

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

3.后序遍歷

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

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

（3）此時，該判斷此節(jié)點的右子樹，如果存在右子樹，把該節(jié)點當作根節(jié)點，重復（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)//當沒有左子樹時，停止入棧
			{
				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//當存在右子樹時，把右子樹的根節(jié)點壓入棧中，循環(huán)去判斷該節(jié)點的左子樹是否存在
			{
				cur = top->_right;
			}
		}
	}

網(wǎng)頁題目：二叉樹遍歷的非遞歸實現(xiàn)
URL標題：http://muchs.cn/article32/ghigpc.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供建站公司、虛擬主機、網(wǎng)站營銷、網(wǎng)站制作、網(wǎng)站收錄、網(wǎng)站設計公司

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉載，或轉載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容