C++数据结构-二叉树的三种遍历方法（进阶篇）

1. 遍历简介：

树作为非线性数据结构，在我们取出数据时就需要设计遍历，所谓遍历，就是按照一定的规则性，将数据结构中的所有数据全部依次访问，而二叉树本身并不具有天然的全局次序，故为实现遍历，需通过在各节点与其孩子之间约定某种局部次序，间接地定义某种全局次序，这便是我们常规定的先序，中序，后续遍历。

在开始前，请记住下面的这三句话：

先序遍历：根左右

中序遍历：左根右

后序遍历：左右根

2. 先序遍历：

先序遍历就是在访问二叉树的结点的时候采用，先根，再左，再右的方式，对于一个最简单的访问而言如图，先序遍历的访问顺序就是A，B，C

然而实际上的遍历访问并没有那么简单，往往是多个结点相互嵌套构成的二叉树，

如图所示，在访问遍历一开始的时候，先访问根结点A，次访问左节点B，由于左结点中嵌套了一组结点，因此左节点又作为下一个结点的根结点，因此就继续沿着B访问到了D，同样由于D中包含了一组新的结点，D又作为根节点继续访问，就又访问到了E，由于E没有后面的结点了，作为D为根的左结点E访问结束后，访问到F，这一组访问结束之后再回退访问G……

由此如下的访问规律：这一个二叉树的先序遍历访问顺序就是：ABDEFGCH

2.1. 代码实现

续上文的代码，实现先序遍历思路非常简单，只需要巧妙的利用“递归”即可。

//树的先序遍历 Preorder traversal
void preorder(Node* node){
    if (node != NULL)
    {
        printf("%d ",node->data);
        inorder(node->left);
        inorder(node->right);
    }
}

2.2. 扩展：前缀表达式（波兰式）

波兰式又称为前缀表达式，我们日常的运算表达式通常是如下形式，这种成为中缀表达式，也就是运算符在运算数的中间。这种表达式人类人容易识别，并根据其进行计算，但计算机识别这种表达式非常困难。

如图，为常规表达式：(a+b)*c

其二叉树的表现形式为：

而波兰式的表达方式就是 *+cab ，波兰式的一个特征就是符号迁移，常规的表达式是需要大量的括号表达先后顺序的，而这样的波兰式表达形式不需要，更容易让计算机处理，我们常规的表达式的计算是中序的，而计算机更方便对波兰式这样的方式进行理解，进行这样的转换首先思路要进行转换，在代码中我们实现这样的转换一般可以利用栈，熟练书些这样的转换就需要STL的掌握，这点作为扩展内容自行学习。

3. 中序遍历

中序遍历采用左根右的遍历方式，如图，就一个最简单的二叉树遍历而言，中序遍历的遍历访问过程是先B再A再C。

实际上的二叉树并没有这么简单，其应该是由多个结点构成的，如图所示，进行第一次访问的时候，我们在ABC中进行遍历，由左根右的顺序，我们遍历访问到B，这时候先别急，B同时又作为BDG的根结点，因此需要继续向下进行遍历，此时我们遍历到DEF，这时E属于这一组之中的左结点，因此我们根据根左右的先后顺序得到了最先的遍历效果，EDF，这EDF同时作为BDG中的左节点（把EDF看作一个整体）进行回溯，此时的访问的结点顺序为EDFBG同理, EDFBG作为ABC的左结点根据左根右的顺序EDFBGAC，左半部分访问完毕接着访问右半部分，我们将^CH（^表示空）看作一组左中右，而C就是由EDFBGAC组合而成，因此最终的遍历顺序为：EDFBGACH

3.1. 代码实现

续上文的代码，巧妙利用递归，与前文的代码只有一个顺序的区别：

//树的中序遍历 In-order traversal
void inorder(Node* node){
    if (node != NULL)
    {
        inorder(node->left);
        printf("%d ",node->data);
        inorder(node->right);
    }
}

3.2. 中缀表达式（常规算式）

中缀表达式是一个通用的算术或逻辑公式表示方法。中缀表达式就是我们最常用的表达式形式，也是人最容易理解的表达式形式。

如图，为常规表达式：(a+b)*c

其二叉树的表现形式为：

由前文可知波兰式的表达方式就是 *+cab ，我们常规的表达式的计算是中序的，其表达式就是(a+b)*c，我们可以理解为将表达式利用二叉树化，然后通过中序遍历的方式进行提取，如果需要发生组合时，需要我们借助括号的形式表示优先级，这样也有一个弊端，就是当多个嵌套的时候需要的括号较多。

4. 后序遍历

后序遍历就是在访问二叉树的结点的时候采用，先左，再右，再根的方式，对于一个最简单的访问而言如图，先访问左节点B，之后访问右结点C，最后访问根节点A，后序遍历的访问顺序就是BCA

然而实际上的遍历访问并没有那么简单，往往是多个结点相互嵌套构成的二叉树，

如图所示，在访问遍历一开始的时候，先访问左节点B再访问右结点C最后访问A，但由于B结点其中也包含了新的结点，就犹如之前介绍的那样，在面对处理的结点后还存在有与之相联的结点的时候，需要优先处理其的子结点，这也是“递归”的基本思路，因此，由于B属于DG的根结点，我们相较于B，应该先访问D结点，而又由于D结点属于EF的根结点，我们就又变成先访问E结点，E属于最末端了，根据后序遍历左右根的访问顺序，依次生成EFDGB作为一个整体，接着我们需要访问C，由于C又是^HC之中的根结点，我们先访问这个空结点，又因为其是一个空的结点，我们会跳过，就变成了HC的访问顺序，那么最后在汇总的时候EFDGB作为左节点，HC作为右结点，A作为根结点，完成我们最终的遍历顺序EFDGBHCA。

4.1.代码实现

续上文的代码，巧妙利用递归，与前文的代码只有一个顺序的区别：

4.2. 后缀表达式（逆波兰式）

逆波兰式与波兰式不同，波兰式采用先序遍历的方式遍历访问我们的公式顺序，常规式则就是我们熟悉的中序方式，而逆波兰式采用后续遍历的方式进行访问。

如图，为常规表达式：(a+b)*c

其二叉树的表现形式为：

而逆波兰式的表达方式就是ab+c* ，相较于波兰式，逆波兰式则就是将符号进行后移，其在计算机中的读取运算概念也符合栈的思路，因此没有什么特殊的不同，在考研/软考/算法竞赛中，比较常见的一类提醒就是波兰式，常规表达式，逆波兰式之间的互相转化和基本数学运算。