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

公司主營(yíng)業(yè)務(wù)：成都網(wǎng)站制作、成都網(wǎng)站設(shè)計(jì)、移動(dòng)網(wǎng)站開(kāi)發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競(jìng)爭(zhēng)能力。創(chuàng)新互聯(lián)建站是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開(kāi)放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對(duì)我們的高要求，感謝他們從不同領(lǐng)域給我們帶來(lái)的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶帶來(lái)驚喜。創(chuàng)新互聯(lián)建站推出綏陽(yáng)免費(fèi)做網(wǎng)站回饋大家。

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

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

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

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

1. 前序遍歷：

void PrevOrder()
{
	_PrevOrder(_root);
	cout<* root)
{
	if (root==NULL)
    	    return;

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

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

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

	cout<
2.中序遍歷：
	void InOrder()
	{
		_InOrder(_root);
		cout<* root)
	{
		if (root == NULL)
			return;

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

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

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

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

				cur = top->_right;
			}
		}

		cout<
3.后序遍歷：
       	void PostOrder()
	{
		_PostOrder(_root);
		cout<* root)
	{
		if (root == NULL)
			return;

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

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

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

		cout<
4.層次遍歷
	void LevelOrder()
	{
		queue* > q;
		if (_root)
			q.push(_root);

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

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

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

		}

		cout<
以上
另外有需要云服務(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ù)的前序/中序/后序/層次遞歸-創(chuàng)新互聯(lián)            

            分享URL：http://weahome.cn/article/diepji.html