树的后根遍历与中序遍历的关系是什么?

发布网友发布时间：2024-04-17 12:11

共1个回答

热心网友时间：2024-04-21 08:15

原话应该是这样的：一棵树的后根遍历与这棵树所对应的二叉树的中序遍历相同。因为树转化为二叉树后是没有右子树的，所以最后访问的是树的根结点。

先根遍历、中根遍历、后根遍历。

先序遍历、中序遍历、后序遍历。

是对同一种问题的两种说法。二叉树的先根遍历序列与其对应的二叉树的中序序列相同，仅有一种特例：即该二叉树的各结点仅有右子树，也就是一棵退化了的右偏的线性序列。

扩展资料：

与那些基本上都有标准遍历方式（通常是按线性顺序）的线性数据结构（如链表、一维数组）所不同的是，树结构有多种不同的遍历方式。从二叉树的根节点出发，节点的遍历分为三个主要步骤：对当前节点进行操作（称为“访问”节点）、遍历左边子节点、遍历右边子节点。这三个步骤的先后顺序也是不同遍历方式的根本区别。

由于从给定的某个节点出发，有多个可以前往的下一个节点（树不是线性数据结构），所以在顺序计算（即非并行计算）的情况下，只能推迟对某些节点的访问——即以某种方式保存起来以便稍后再访问。常见的做法是采用栈（LIFO）或队列（FIFO）。

百度百科-中序遍历

参考资料：百度百科-遍历