二叉树的遍历是指通过一定顺序访问二叉树的所有结点。遍历方法一般有四种：先序遍历、中序遍历、后序遍历及层次遍历，其中，前三种一般使用深度优先搜索(DFS)实现，而层次遍历一般使用广度优先搜索(BFS).
无论是这三种遍历中的哪一种，左子树一定先于右子树遍历，且所谓的“先中后”都是指根结点root在遍历中的位置，因此
先序遍历的访问顺序是根结点→左子树→右子树，
中序遍历的访问顺序是左子树→根结点→右子树，
后序遍历的访问顺序是左子树→右子树→根结点。
1.先序遍历
对先序遍历来说，总是先访问根结点root，然后才去访问左子树和右子树，因此先序遍历的遍历顺序是根结点→左子树→右子树，为了实现递归的先序遍历，需要得到两样东西递归式和递归边界。其中递归式已经可以由先序遍历的定义直接得到，即先访问根结点（可以做任何事情），再递归访问左子树，最后递归访问右子树。那么这样一直递归访问左子树和右子树，递归边界是什么呢？二叉树的递归定义中的递归边界是二叉树为一棵空树，这一点同样可以用在这里，即在递归访问子树时，如果碰到子树为空，那么就说明到达死胡同。
void preorder(node* root){ if(root==NULL){ return; //到达空树，递归边界 } //访问根结点root，例如将其数据域输出 printf("%d\n",root->data); //访问左子树 preorder(root->lchild); //访问右子树 preorder(root->rchild); }
由于先序遍历先访问根结点，因此对一棵二叉树的先序遍历序列，序列的第一个一定是根结点。
对中序遍历来说，总是先访问左子树，再访问根结点（即把根结点放在中间访问），最后访问右子树，因此中序遍历的遍历顺序是左子树→根结点→右子树。中序遍历的实现思路和先序遍历完全相同，只不过把根结点的访问放到左子树和右子树中间了.
void inorder(node* root){ if(root==NULL){ return; //到达空树，递归边界 } //访问左子树 inorder(root->lchild); //访问根结点root，例如将其数据域输出 printf("%d\n",root->data); //访问右子树 inorder(root->rchild); }
由于中序遍历总是把根结点放在左子树和右子树中间，因此可利用先序遍历中第一个为根节点和后序遍历最后一个为根节点（且对于子树而言也满足），因此只要通过这种方法知道根结点，就可以通讨根结点在中序遍历序列中的位置区分出左子树和右子树。
对后序遍历来说，总是先访问左子树，再访问右子树，最后才访问根结点（即把根结点放在最后访问），因此后序遍历的遍历顺序是左子树→右子树→根结点。
void postorder(node* root){ if(root==NULL){ return; //到达空树，递归边界 } //访问左子树 postorder(root->lchild); //访问右子树 postorder(root->rchild); //访问根结点root，例如将其数据域输出 printf("%d\n",root->data); }
性质：
后序遍历总是把根结点放在最后访问，这和先序遍历恰好相反，因此对后序遍历序列来说，序列的最后一个一定是根结点。
总的来说，无论是先序遍历序列还是后序遍历序列，都必须知道中序遍历序列才能唯地确定一棵树。这是因为，通过先序遍历序列和后序遍历序列都只能得到根结点，而只有通过中序遍历序列才能利用根结点把左右子树分开，从而递归生成一棵二叉树。当然，这个做法需要保证在所有元素都不相同时才能使用。
层序遍历是指按层次的顺序从根结点向下逐层进行遍历，且对同一层的结点为从左到右遍历。需要从根结点开始从上往下逐层遍历，而对同一层进行从左到右的遍历。这个过程和BFS很像，因为BFS进行搜索总是以广度作为第一关键词，而对应到二叉树中广度又恰好体现在层次上，因此层次遍历就相当于是对二叉树从根结点开始的广度优先搜索，基本思路如下：
①将根结点root加入队列q。
②取出队首结点,访问它。
③如果该结点有左孩子，将左孩子入队。
④如果该结点有右孩子，将右孩子入队。
⑤返回②，直到队列为空。
于是可以按上面的过程写出代码：
//层次遍历 void LayerOrder(node* root) { queue<node*> q; //注意队列里是存地址 q.push(root); //将根结点地址入队 while(!q.empty()) { node* now = q.front(); //取队首元素 q.pop(); printf("%d",now->data); //访问队首元素 if(now->lchild!=NULL) //左子树非空 q.push(now->lchild); if(now->rchild!=NULL) //右子树非空 q.push(now->lrchild); } }
可以发现，这里使用的队列中元素是node*型而不是node型。这是因为在之前讲解广度优先搜索时提到过，队列中保存的只是原元素的一个副本，因此如果队列中直接存放node型，当需要修改队首元素时，就会无法对原元素进行修（即只修改了队列中的副本）,故让队列中存放node型变量的地址，也就是node*型变量。这样就可以通过访问地址去修改原元素，就不会有问题了。
另外还需要指出，很多题目当中要求计算出每个结点所处的层次，这时就需要在二叉树结点的定义中添加一个记录层次layer 的变量：
struct node{ int data; //数据域 int layer; //层次 node* lchild; //左指针域 node* rchild; //右指针域 };
需要在根结点入队前就先令根结点的layer为1来表示根结点是第一层（也可以令根结点的层号为0,由题意而定），之后在now->lchild和now->rchild入队前，把它们的层号都记为当前结点now的层号加1，即：
//层次遍历 void LayerOrder(node* root) { queue<node*> q; //注意队列里是存地址 root->layer = 1; //根结点的层号为 1 q.push(root); //将根结点地址入队 while(!q.empty()) { node* now = q.front(); //取队首元素 q.pop(); printf("%d ",now->data); //访问队首元素 if(now->lchild!=NULL){ //左子树非空 now->lchild->layer = now->layer+1; //左孩子的层号为当前层号+1 q.push(now->lchild); } if(now->rchild!=NULL){ //右子树非空 now->rchild->layer = now->layer+1; //右孩子的层号为当前层号+1 q.push(now->rchild); } } }
原文：https://www.cnblogs.com/migang/p/14675185.html