0

考虑这棵树：

           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 中遍历从最左边的节点开始，但 PreOrder 遍历不是从最左边的中间节点开始？

谢谢，克里斯。

4

2 回答 2

3

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

preorder的一个典型用法是标准函数表示法：如果你有类似的东西

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

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

      f
      |
      g
     / \
    x   h
       / \
      y   z

另一方面，带有运算符的常用表示法+和*使用中序：

a + b * c

是的有序符号

    +
   / \
  a   *
     / \
    b   c

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

以逆波兰表示法编写表达式将是postorder的一个示例。

于 2013-08-29T21:22:06.867 回答
1

中序：遍历左子树；访问当前节点；遍历右子树；

预购：访问当前节点；遍历左子树；遍历右子树；

后序：遍历左子树；遍历右子树；访问当前节点；

请注意，除非缺少左子树，否则 Inorder 和 Preorder 中永远不会有相同的节点。

但是，如果存在左子树，您可以在 Inorder 和PostOrder表示中拥有相同的节点。

于 2013-08-29T21:45:31.877 回答