樹：二叉樹的前序/中序/后序/層次遞歸

在二叉樹的應(yīng)用中，很多使用二叉樹的操作都是通過遍歷來進(jìn)行節(jié)點(diǎn)的修改。

成都創(chuàng)新互聯(lián)公司專注于南芬網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠為您提供南芬營(yíng)銷型網(wǎng)站建設(shè)，南芬網(wǎng)站制作、南芬網(wǎng)頁設(shè)計(jì)、南芬網(wǎng)站官網(wǎng)定制、微信小程序開發(fā)服務(wù)，打造南芬網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供南芬網(wǎng)站排名全網(wǎng)營(yíng)銷落地服務(wù)。

所以對(duì)于遍歷而言是學(xué)習(xí)二叉樹的要點(diǎn)，今天就來總結(jié)一下。

假設(shè)二叉樹的結(jié)構(gòu)為：

template<class T>
struct BinaryTreeNode
{
	BinaryTreeNode(const T& x)
		:_data(x)
		,_left(NULL)
		,_right(NULL)
	{}

	T _data;
	BinaryTreeNode<T>* _left;
	BinaryTreeNode<T>* _right;
};

1. 前序遍歷：

void PrevOrder()
{
	_PrevOrder(_root);
	cout<<endl;
}
void _PrevOrder(BinaryTreeNode<T>* root)
{
	if (root==NULL)
    	    return;

	cout<<root->_data<<" ";
	_PrevOrder(root->_left);
	_PrevOrder(root->_right);
}

void PrevOrder_Non_R()
{
	stack<BinaryTreeNode<T>*> s;
	if (_root)
	s.push(_root);
	while(!s.empty())
	{
		BinaryTreeNode<T>* top = s.top();
		cout<<top->_data<<" ";
		s.pop();

		if (top->_right)
			s.push(top->_right);
			
		if (top->_left)
			s.push(top->_left);
	}

	cout<<endl;
}
	

2.中序遍歷：

	void InOrder()
	{
		_InOrder(_root);
		cout<<endl;
	}

        void _InOrder(BinaryTreeNode<T>* root)
	{
		if (root == NULL)
			return;

		_InOrder(root->_left);
		cout<<root->_data<<" ";
		_InOrder(root->_right);
	}

	void InOrder_Non_R()
	{
		stack<BinaryTreeNode<T>*> s;
		BinaryTreeNode<T>* cur = _root;

		while (cur || !s.empty())
		{
			// 1.壓左節(jié)點(diǎn)
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}

			// 取棧頂節(jié)點(diǎn)數(shù)據(jù)訪問
			// 前序遍歷top節(jié)點(diǎn)的右樹
			if (!s.empty())
			{
				BinaryTreeNode<T>* top = s.top();
				s.pop();
				cout<<top->_data<<" ";

				cur = top->_right;
			}
		}

		cout<<endl;
	}

3.后序遍歷：

       	void PostOrder()
	{
		_PostOrder(_root);
		cout<<endl;
	}
       
        void _PostOrder(BinaryTreeNode<T>* root)
	{
		if (root == NULL)
			return;

		_PostOrder(root->_left);
		_PostOrder(root->_right);
		cout<<root->_data<<" ";
	}
	
	void PostOrder_Non_R()
	{
		stack<BinaryTreeNode<T>*> s;
		BinaryTreeNode<T>* cur = _root;
		BinaryTreeNode<T>* prevVisited = NULL;

		while (cur || !s.empty())
		{
			// 1.壓左節(jié)點(diǎn)
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}

			BinaryTreeNode<T>* top = s.top();
			if (top->_right == NULL 
				|| top->_right == prevVisited)
			{
				cout<<top->_data<<" ";
				s.pop();
				prevVisited = top;
			}
			else
			{
				cur = top->_right;
			}
		}

		cout<<endl;
	}

4.層次遍歷

	void LevelOrder()
	{
		queue<BinaryTreeNode<T>* > q;
		if (_root)
			q.push(_root);

		while(!q.empty())
		{
			BinaryTreeNode<T>* front = q.front();
			cout<<front->_data<<" ";
			q.pop();

			if (front->_left)
				q.push(front->_left);

			if (front->_right)
				q.push(front->_right);

		}

		cout<<endl;
	}

以上

網(wǎng)站名稱：樹：二叉樹的前序/中序/后序/層次遞歸
本文URL：http://bm7419.com/article40/jjcpho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、網(wǎng)站排名、關(guān)鍵詞優(yōu)化、、云服務(wù)器、微信公眾號(hào)

廣告

聲明：本網(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í)需注明來源： 創(chuàng)新互聯(lián)