java - 二叉树的 PostOrder 遍历不一致地跳转到兄弟或父节点

Question

在二叉树中输入以下值({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}。写出此结果背后的逻辑时，您会得到以下内容:从根开始，在 full left 之后，您最终到达 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 三角形中不是这样呢？

Answer 1

I'm guessing this is because the node with value 73 is processed before the parentNode (left-right-top priority), but why isn't this the case in the 45-52-78 triangle then?

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

左兄弟总是在右兄弟之前被访问，右兄弟总是在父节点之前被访问。访问哪些else将取决于左右 sibling 的 child 。

wikipedia page on tree traversal将其描述为:

To traverse a non-empty binary tree in postorder, perform the following operations recursively at each node:

• Traverse the left subtree.
• Traverse the right subtree.
• Visit the root.

因此，只有当您访问了一个节点的所有 个子节点时，您才会访问该节点，并且您将始终在访问右子树之前访问左子树。结果中的所有内容都符合这一点。