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

創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),雙河企業(yè)網(wǎng)站建設(shè),雙河品牌網(wǎng)站建設(shè),網(wǎng)站定制,雙河網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷,網(wǎng)絡(luò)優(yōu)化,雙河網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

1.前序遍歷

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

代碼如下：

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

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

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

2.中序遍歷

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

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

 （3）此時(shí)，該判斷此節(jié)點(diǎn)的右子樹(shù)：

      a.右子樹(shù)為NULL，返回到棧頂；

      b.右子樹(shù)不為NULL，把該節(jié)點(diǎn)當(dāng)根節(jié)點(diǎn)，重復(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)沒(méi)有左子樹(shù)時(shí)，停止入棧
			{
				s.push(cur);
				cur = cur->_left;
			}
			Node * top = s.top();//保留棧頂指針，判斷是否有右子樹(shù)
			cout << top->_data << "->";
			s.pop();

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

3.后序遍歷

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

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

 （3）此時(shí)，該判斷此節(jié)點(diǎn)的右子樹(shù)，如果存在右子樹(shù)，把該節(jié)點(diǎn)當(dāng)作根節(jié)點(diǎn)，重復(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)沒(méi)有左子樹(shù)時(shí)，停止入棧
			{
				s.push(cur);
				cur = cur->_left;
			}

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

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

當(dāng)前題目：二叉樹(shù)遍歷的非遞歸實(shí)現(xiàn)-創(chuàng)新互聯(lián)
瀏覽路徑：http://jinyejixie.com/article4/dcppie.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站導(dǎo)航、云服務(wù)器、虛擬主機(jī)、App設(shè)計(jì)、網(wǎng)站收錄、企業(yè)網(wǎng)站制作

廣告

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