二叉树的遍历（深度优先+广度优先）
二叉树的遍历分为两类，一类是深度优先遍历，一类是广度优先遍历。
1.深度优先遍历
二叉树的深度优先遍历有三种方式，先序（先根次序）、中序（中根次序）和后序（后根次序）遍历。
因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在三种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点。下面一一讲解具体的递归和非递归实现。
1.1 先序遍历
先根次序遍历按照“根结点 > 左孩子 > 右孩子”的顺序进行访问。
- 递归实现
//先根递归遍历
void preOrderRecursion(BinaryTreeNode* root)
{
if(root==NULL) return;
cout<< " " << root->m_key;
preOrderRecursion(root->m_pLeft);
preOrderRecursion(root->m_pRight);
}- 非递归实现
根据先序遍历的顺序，首先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问完左子树时，再访问它的右子树。因此其处理过程如下：
给定二叉树的根节点 R：
（a）并将根节点 R 入栈；
（b）判断栈是否为空，若不为空，取栈顶元素 cur 访问并出栈。然后先将 cur 的右子节点入栈，再将 cur 的左子节点入栈；
（c）重复（b）直到栈为空，则遍历结束。
// 先序非递归遍历，需要使用栈
void preOrderStack(BinaryTreeNode* root)
{
if(root==NULL) return;
stack<BinaryTreeNode*> stack;
stack.push(root);
BinaryTreeNode* cur=NULL;
while(!stack.empty())
{
cur=stack.top();
cout<<" "<<cur->m_key; //visit
stack.pop();
if(cur->m_pRight!=NULL)
{
stack.push(cur->m_pRight);
}
if(cur->m_pLeft!=NULL)
{
stack.push(cur->m_pLeft);
}
}
}1.2 中序遍历
中序遍历按照“左孩子 > 根结点 > 右孩子”的顺序进行访问。
- 递归实现
//中序递归遍历
void midOrderRecursion(BinaryTreeNode* root){
if(root==NULL)
return;
midOrderRecursion(root->m_pLeft);
cout<<" "<<root->m_key; //visit
midOrderRecursion(root->m_pRight);
}- 非递归实现
根据中序遍历的顺序，对于任一结点，先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。因此其处理过程如下：
对于给定的二叉树根节点 R，
（a）若其左孩子不为空，循环将R以及R左子树中的所有节点的左孩子入栈；
（b）取栈顶元素 cur，访问 cur 并将 cur 出栈。然后对 cur 的右子节点进行步骤（a）那样的处理；
（c）重复（a）和（b）的操作，直到 cur 为空切栈为空。
// 中根非递归遍历，需要使用栈
void midOrderStack(BinaryTreeNode* root)
{
if(root==NULL) return;
stack<BinaryTreeNode*> stack;
BinaryTreeNode* cur=root;
while(!stack.empty()||cur!=NULL)
{
while(cur)
{
stack.push(cur);
cur=cur->m_pLeft;
}
cur=stack.top();
cout<<" "<<cur->m_key; //visit
stack.pop();
cur=cur->m_pRight;
}
}1.3 后序遍历
后序遍历按照“左孩子 > 右孩子 > 根结点”的顺序进行访问。
- 递归实现
// 后根递归遍历
void postOrderRecursion(BinaryTreeNode* root)
{
if(root==NULL) return;
postOrderRecursion(root->m_pLeft);
postOrderRecursion(root->m_pRight);
cout << " " << root->m_key;
}- 非递归实现
后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子要在右孩子前被访问，才能访问根节点。这就为流程的控制带来了难题。下面介绍两种思路。
第一种思路：对于任一结点 P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。
// 非递归后序遍历，版本1
void postOrderStack1(BinaryTreeNode* root)
{
if(root==NULL) return;
stack<pair<BinaryTreeNode*, bool>> s;
pair<BinaryTreeNode*,bool> cur=make_pair(root,true);
while(cur.first!=NULL||!s.empty())
{
//沿左子树一直往下搜索，直至出现没有左子树的结点
while(cur.first!=NULL)
{
s.push(cur);
cur=make_pair(cur.first->m_pLeft,true);
}
if(!s.empty())
{
//表示是第一次出现在栈顶
if(s.top().second==true)
{
s.top().second=false;
cur=make_pair(s.top().first->m_pRight,true); //将当前节点的右节点入栈
}
else
{
// 第二次出现在栈顶
cout << s.top().first->m_key << " ";
s.pop();
}
}
}
}第二种思路：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点R，
（a）先将R入栈。如果P不存在左孩子和右孩子，则可以直接访问它并出栈；
（b）如果R存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点并出栈；
（c）若非上述两种情况，则将R的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在父结点前面被访问。
// 非递归后序遍历，版本 2
void postOrderStack2(BinaryTreeNode* root)
{
if(root==NULL) return;
stack<BinaryTreeNode*> s;
BinaryTreeNode* cur; //当前结点
BinaryTreeNode* pre=NULL; //前一次访问的结点
s.push(root);
while(!s.empty())
{
cur=s.top();
//在判断当前结点时，左孩子和右孩子都在根结点前已经被访问
if((cur->m_pLeft==NULL&&cur->m_pRight==NULL) || (pre!=NULL&&(pre==cur->m_pLeft || pre==cur->m_pRight)))
{
cout<<cur->m_key<<" "; //如果当前结点没有孩子结点或者孩子节点都已被访问过
s.pop();
pre=cur;
}
else
{
if(cur->m_pRight!=NULL) s.push(cur->m_pRight);
if(cur->m_pLeft!=NULL) s.push(cur->m_pLeft);
}
}
}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);
}
} 3.验证结果
以上面介绍的各种遍历，验证代码如下：
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
// 二叉树节点结构体
struct BinaryTreeNode
{
int m_key;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
/****************************************
func:根据前序序列和中序序列构建二叉树
para:preOrder:前序序列;midOrder:中序序列;len:节点数
****************************************/
BinaryTreeNode* construct(int* preOrder,int* midOrder,int len)
{
if(preOrder==NULL||midOrder==NULL||len<=0) return NULL;
//先序遍历的第一个值是根结点的键值
int rootKey=preOrder[0];
BinaryTreeNode* root=new BinaryTreeNode;
root->m_key=rootKey;
root->m_pLeft=root->m_pRight=NULL;
//只有一个节点
if(len==1 && *preOrder == *midOrder) return root;
//在中序遍历中找到根节点的值
int* rootMidOrder=midOrder;
int leftLen=0; //左子树节点数
while(*rootMidOrder!=rootKey&&rootMidOrder<=(midOrder+len-1))
{
++rootMidOrder;
++leftLen;
}
//在中序序列未找到根结点，输入错误
if(*rootMidOrder!=rootKey) return NULL;
//构建左子树
if(leftLen>0)
{
root->m_pLeft=construct(preOrder+1,midOrder,leftLen);
}
//构建右子树
if(len-leftLen-1>0)
{
root->m_pRight=construct(preOrder+leftLen+1,rootMidOrder+1,len-leftLen-1);
}
return root;
}
int main()
{
// 先序序列
int preOrder[8]={1,2,4,7,3,5,6,8};
// 中序序列
int midOrder[8]={4,7,2,1,5,3,8,6};
// 建树
BinaryTreeNode* root=construct(preOrder, midOrder, 8);
cout<<"---preOrder---"<<endl;
cout<<"recursion version: ";
preOrderRecursion(root);
cout<<endl<<"stack version: ";
preOrderStack(root);
cout<<endl<<endl<<"---midOrder---"<<endl;
cout<<"recursion version: ";
midOrderRecursion(root);
cout<<endl<<"stack version1: ";
postOrderStack1(root);
cout<<endl<<"stack version2: ";
postOrderStack2(root);
cout<<endl<<endl<<"---postOrder---"<<endl;
cout<<"recursion version: ";
postOrderRecursion(root);
cout<<endl<<"stack version: ";
postOrderStack1(root);
cout<<endl<<endl<<"---Breadth First Order---"<<endl;
breadthFirstOrder(root);
}实验结果如下：
---preOrder---
recursion version: 1 2 4 7 3 5 6 8
stack version: 1 2 4 7 3 5 6 8
---midOrder---
recursion version: 4 7 2 1 5 3 8 6
stack version: 4 7 2 1 5 3 8 6
---postOrder---
recursion version: 7 4 2 5 8 6 3 1
stack version1: 7 4 2 5 8 6 3 1
stack version2: 7 4 2 5 8 6 3 1
---Breadth First Order---
1 2 3 4 5 6 7 8
参考文献
1(https://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html)