2

在二叉树中输入以下值（{18, 26, 52, 78, 45, 16, 67, 58, 73, 11}）时，您会收到此树：

二叉树图像

PreOrder 和 InOrder 遍历都像我期望的那样工作。然而，当谈到 PostOrder (PO) 时，我收到的东西与我想象的不同。

据我了解，PO首先搜索左子树，然后搜索右子树，最后搜索节点（以根节点结尾）。

当通过这棵树在 PO 中遍历时，您最终会得到以下结果：{11, 16, 45, 58, 73, 67, 78, 52, 26, 18}。当写出这个结果背后的逻辑时，你会得到以下结果：从根开始，跟随完整的左，你最终在 11 这是你的第一个节点。之后，您上一层并获取其父级 (16)。你继续这样做直到你到达根（它不被包括在内，因为它不是一个leftChild）。一旦你通过了这个初始的左子树，你在右边向下一层并检查那里的 leftChilds。如果没有，你就往下一层，也就是我们找到 45 的地方。

此时我们有一个 {11, 16, 45} 的列表。我们继续这个并最终得到 58，这是我们在结果中的下一个值。这就是我困惑的地方：我们得到的下一个值是 73，与预期的 67 相反。为什么当找到另一个 leftChild（它的父级）时它会跳到 73？

以下代码负责遍历 PostOrder 中的树：

public void postorderTraversal(){
    postorderHelper(root);
}

private void postorderHelper(Node node){
    if(node != null){
        postorderHelper(node.getLeftNode());
        postorderHelper(node.getRightNode());
        System.out.print(node.getData() + " ");
    }
}

我猜这是因为值 73 的节点在 parentNode 之前处理（左右优先级），但为什么 45-52-78 三角形中不是这种情况呢？

4

1 回答 1

4

我猜这是因为值 73 的节点在 parentNode 之前处理（左右优先级），但为什么 45-52-78 三角形中不是这种情况呢？

是的，因为 45 在 78 之前，而在 52 之前。

左兄弟姐妹总是在右兄弟姐妹之前被访问，而右兄弟姐妹总是在父母之前被访问。它们之间还访问了什么将取决于左右兄弟姐妹有什么孩子。

树遍历的维基百科页面将其描述为：

要以后序遍历非空二叉树，请在每个节点处递归执行以下操作：

  • 遍历左子树。
  • 遍历右子树。
  • 访问根。

因此，如果您访问过它的所有子节点，您只会访问一个节点，并且您总是会在访问右子树之前访问左子树。结果中的所有内容都与此相关。

于 2013-01-03T14:18:06.447 回答