二叉樹的周遊（前序、中序、後序、層序）

1.二叉樹基礎

（1）定義：有且僅有一個根節點，除根節點以外，每個節點隻有一個父節點，最多有兩個子節點，子節點有左右之分。

（2）存儲結構：二叉樹的存儲結構可以采用順序存儲結構，也可以采用鍊式存儲結構，其中鍊式存儲更加靈活。

在鍊式存儲中，二叉樹的每個節點采用結構體表示，結構體包含三個域：資料域、左指針域、右指針域。

2.二叉樹周遊

“周遊”是二叉樹各種操作的基礎，二叉樹是一種非線性結構，周遊就是要讓樹的所有節點被且被通路一次，即按一定規律排列成一個線性隊列。二叉樹的周遊方式可以分為下面四種，分别為：“前序周遊”、“中序周遊”、“後序周遊”、“層序周遊”。下面依次介紹這幾種周遊方式：

（1）前序周遊

若二叉樹為空，則直接傳回。否則先通路根節點，然後前序周遊左子樹，再前序周遊右子樹。如下圖所示：

代碼如下：

//遞歸實作：
void PrevOrder()
	{
		_PrevOrder(_root);
		cout<<endl;
	}
	void _PrevOrder(Node* root)
	{
		if(root == NULL)
			return;
		cout<<root->_data<<" ";
		_PrevOrder(root->_left);
		_PrevOrder(root->_right);
	}
//非遞歸實作：
void PrevOrderNoR()
	{
		stack<Node*> s;
		Node* cur = _root;
		while(cur || !s.empty())
		{
			while(cur)
			{
				cout<<cur->_data<<" ";
				s.push(cur);
				cur = cur->_left;
			}

			//走到這兒，最左路節點已經通路
			Node* top = s.top();
			s.pop();
			cur = top->_right;
		}
	}
           

（2）中序周遊

若二叉樹為空，則直接傳回。否則從根節點開始（注意不是先通路根節點），中序周遊根節點的左子樹，然後是通路根節點，最後中序周遊右子樹。如下圖所示：

代碼如下：

//遞歸實作：
void InOrder()
	{
		_InOrder(_root);
		cout<<ednl;
	}
	void _InOrder(Node* root)
	{
		if(root == NULL)
			return;
		_InOrder(root->_left);
		cout<<root->_data<<" ";
		_InOrder(root->_right);
	}
//非遞歸實作：
void InOrderNoR()
	{
		stack<Node*> s;
		Node* cur = _root;
		while(cur || !s.empty())
		{top
			while(cur)
			{
				s.push(cur);
				cur = cur->_left;
			}
			Node* top = s.top();
			cout<<top->_data<<" ";
			s.pop();
			cur = top->_right;
		}
	}
           

（3）後序周遊

若二叉樹為空，則直接傳回。否則從左到右先葉子後結點的方式周遊通路左右子樹，最後通路根節點。如下圖所示：

代碼如下：

//遞歸如下：
void PostOrder()
	{
		_PostOrder(_root);
		cout<<endl;
	}
	void _PostOrder(Node* root)
	{
		if(root == NULL)
			return ;
		_PostOrder(root->_left);
		_PostOrder(root->_right);
		cout<<root->_data<<" ";
	}
//非遞歸如下：
PostOrderNoR()
	{
		stack<Node*> s;
		Node* prev = NULL;
		Node* cur = _root;
		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<<" ";
				prev = top;
				s.pop();
			}
			else
			{
				cur = top->_right;
			}
		}
	}
           

（4）層序周遊

層序周遊，顧名思義就是一層一層的周遊，習慣上我們都是每一層按照從左往右的順序去周遊。代碼如下：

//層序周遊的非遞歸實作：
void LevelOrder()
	{
		queue<Node*> q;
		if(_root)
			q.push(_root);
		while(!q.empty())
		{
			Node* front = q.front();
			cout<<front->_data<<" ";
			if(front->_left)
			{
				q.push(front->_left);
			}
			if(front->_right)
			{
				q.push(front->_right);
			}
			q.pop();
		}
	}
           

好啦，二叉樹的周遊就是這麼簡單~~~