二叉树的遍历(深度优先+广度优先)

二叉树的遍历分为两类，一类是深度优先遍历，一类是广度优先遍历。

1.深度优先遍历

二叉树的深度优先遍历有三种方式，先序（先根次序）、中序（中根次序）和后序（后根次序）遍历。

因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在三种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点。下面一一讲解具体的递归和非递归实现。

1.1 先序遍历

先根次序遍历按照“根结点 > 左孩子 > 右孩子”的顺序进行访问。

递归实现
//先根递归遍历
void preOrderRecursion(BinaryTreeNode* root)
{
	if(root==NULL) return;
	cout<< " " << root->m_key;
	preOrderRecursion(root->m_pLeft);
	preOrderRecursion(root->m_pRight);
}

1.2 中序遍历

中序遍历按照“左孩子 > 根结点 > 右孩子”的顺序进行访问。

递归实现
//中序递归遍历
void midOrderRecursion(BinaryTreeNode* root)
{
	if(root==NULL)
		return;
	midOrderRecursion(root->m_pLeft);
	cout<<" "<<root->m_key;   //visit
	midOrderRecursion(root->m_pRight);
}

1.3 后序遍历

后序遍历按照“左孩子 > 右孩子 > 根结点”的顺序进行访问。

递归实现
// 后根递归遍历
void postOrderRecursion(BinaryTreeNode* root)
{
	if(root==NULL) return;
	postOrderRecursion(root->m_pLeft);
	postOrderRecursion(root->m_pRight);
	cout << " " << root->m_key;
}

2. 广度优先遍历

广度优先周游的方式是按层次从上到下，从左到右的逐层访问，不难想到，可以利用一个队列来实现。基本思想如下：

1.首先把二叉树的根节点送入队列；

2.队首的节点出队列并访问之，然后把它的右子节点和左子节点分别入队列；

3.重复上面两步操作，直至队空。

// 广度优先遍历二叉树，使用队列实现
void breadthFirstOrder(BinaryTreeNode* root)
{
	if(root==NULL) return;
	queue<BinaryTreeNode*> queue;
	queue.push(root);
	while(!queue.empty())
	{
		BinaryTreeNode* cur=queue.front();
		cout<<" "<<cur->m_key;//visit
		queue.pop();
		if(cur->m_pLeft!=NULL) queue.push(cur->m_pLeft);
		if(cur->m_pRight!=NULL) queue.push(cur->m_pRight);
	}
}