algorithm - Inorder 从 "leftmost left node"开始那么为什么 Preorder 不从 "leftmost middle node"开始？

Question

考虑这棵树:

           7
         /    \
       /        \
      /          \
     1            9
    /  \         /  \
   0    3       8   10 
       / \
      2   5
         / \
        4   6

顺序:

0、1、2、3、4、5、6、7、8、9、10

预购:

7、1、0、3、2、5、4、6、9、8、10

在进行中序遍历时，首先定位到最左边的节点，然后从那里开始遍历。但是当涉及到 Preorder 时，相同的逻辑(如 最左边的中间节点)不适用

在上面的树中，除了根节点 7 之外，还有 1 和 9 都是中间节点。 1 是最左边的中间节点，9 是最右边的中间节点。按照上面InOrder应用的逻辑，Preorder遍历应该是从节点1开始的，也就是最左边的中间节点，但不是这样，为什么？

为什么 Inorder 遍历从leftmost left node 而 PreOrder 遍历不是从leftmost middle node?

谢谢， 克里斯。

Answer 1

Preorder 总是将父级放在其后代之前(这是它的定义)，因此它必须从根开始。如果愿意，您可以使用术语“最中间的中间节点”来表示根。

preorder 的典型用法是标准函数符号:如果你有类似的东西

f(g(x, h(y, z)))

那么这是以下表达式树的预序符号，它使用内部节点的函数名称和变量作为离开节点:

      f
      |
      g
     / \
    x   h
       / \
      y   z

另一方面，+ 和 * 等运算符的常用符号使用中序:

a + b * c

是

的顺序符号

    +
   / \
  a   *
     / \
    b   c

如果我们使用 * 比 + 绑定(bind)更强的标准数学优先规则。

并在 reverse polish notation 中编写表达式将是 postorder 的一个例子。