树的遍历之中序遍历二叉树,C语言示例代码

2022-07-1716:12:58数据结构与算法Comments970 views字数 966阅读模式

1. 简介文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

依旧是下面的这三句话:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

先序遍历:根左右文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

中序遍历:左根右文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

后序遍历:左右根文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

在上文我们接触到了先序遍历,本文我们开始学习中序遍历,中序遍历采用左根右的遍历方式,如图,就一个最简单的二叉树遍历而言,中序遍历的遍历访问过程是先B再A再C。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

树的遍历之中序遍历二叉树,C语言示例代码文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

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

树的遍历之中序遍历二叉树,C语言示例代码文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

2. 代码实现文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

续上文的代码,巧妙利用递归,与前文的代码只有一个顺序的区别:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

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

3. 中缀表达式(常规算式)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

中缀表达式是一个通用的算术或逻辑公式表示方法。中缀表达式就是我们最常用的表达式形式,也是人最容易理解的表达式形式。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

如图,为常规表达式:(a+b)*c文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

其二叉树的表现形式为:树的遍历之中序遍历二叉树,C语言示例代码文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

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

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

树的遍历之中序遍历二叉树,C语言示例代码文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

请回答这一颗树的中序遍历是多少?文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

树的遍历之中序遍历二叉树,C语言示例代码文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

l  请回答这一刻二叉树的中序遍历是多少?文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

l  请回答((a+b)+(c+d))*e作为中缀表达式的二叉树如何,做图表示。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25166.html

  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/25166.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定