树的遍历之后序遍历二叉树，C语言示例代码VS后缀表达式（逆波兰式）

2022-07-1716:15:15数据结构与算法Comments1,755 views字数 1025阅读模式

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

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

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

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

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

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

后序遍历就是在访问二叉树的结点的时候采用，先左，再右，再根的方式，对于一个最简单的访问而言如图，先访问左节点B，之后访问右结点C，最后访问根节点A，后序遍历的访问顺序就是BCA。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25172.html

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

然而实际上的遍历访问并没有那么简单，往往是多个结点相互嵌套构成的二叉树，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25172.html

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

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

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

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

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

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

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

3. 后缀表达式（逆波兰式）文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25172.html

逆波兰式与波兰式不同，波兰式采用先序遍历的方式遍历访问我们的公式顺序，常规式则就是我们熟悉的中序方式，而逆波兰式采用后续遍历的方式进行访问。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25172.html

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

其二叉树的表现形式为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25172.html

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

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

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

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

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

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

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

l 请回答（（a+b）+（c+d））*e作为转换成后缀表达式如何，如何表示。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25172.html

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

Qr code