树的遍历之中序遍历二叉树

点击打开在线编译器,边学边练

1. 简介

依旧是下面的这三句话:

先序遍历:根左右

中序遍历:左根右

后序遍历:左右根

      

        在上文我们接触到了先序遍历,本文我们开始学习中序遍历,中序遍历采用左根右的遍历方式,如图,就一个最简单的二叉树遍历而言,中序遍历的遍历访问过程是先B再A再C。


 1.png   



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

2.png


2. 代码实现

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

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

3. 中缀表达式(常规算式)

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

如图,为常规表达式:(a+b)*c

       其二叉树的表现形式为:3.png


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

 

4. 相关问题

l  二叉树的遍历习题:https://www.dotcpp.com/oj/problem1734.html

4.png

请回答这一颗树的中序遍历是多少?


5.png


l  请回答这一刻二叉树的中序遍历是多少?

l  请回答((a+b)+(c+d))*e作为中缀表达式的二叉树如何,做图表示。


第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记