二叉樹遍歷的非遞歸實現-創(chuàng)新互聯(lián)

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

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

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

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

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

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

廣告

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

成都網站建設