递归如何遍历树

Question

java version "1.8.0_92"

我正在研究树以及如何使用递归遍历它们。但我对它的工作感到困惑。

  public void preOrder(BinaryTree root) {
        if(root != null) {
            System.out.println(root);
            preOrder(root.leftChild);  <-- this gets called and will start from the top of the function
            preOrder(root.rightChild); <-- how can this get called if the top one will always calls itself?
        }
    }

我认为第二个 preOrder 永远不会被调用，因为上面的调用总是会调用自己，所以第二个 preOrder 永远不会被执行。

Answer 1

它并不总是调用自己。它会一直运行，直到它以空 leftChild 触底。然后什么都不做就执行returns——往回退一级，在最底层父节点的rightChild上递归。当该调用也用完子节点时，从处理这个最低级别的父节点执行 returns，再次备份一个调用，并执行 that 节点的 rightChild .. .直到遍历整棵树

Answer 2

一旦 root.leftChild 变为 null（即，当您到达树的叶子时），preOrder 将像这样调用：preOrder(null)。发生这种情况时，条件将计算为 false，递归展开并停止，此时将计算 preOrder(root.rightChild)。

这是调用跟踪（在 Scala 中）：

case class BinaryTree(nodeName: String, leftChild: Option[BinaryTree], rightChild: Option[BinaryTree]) {
    def preOrder(root: Option[BinaryTree], depth: Int = 0) {
        root match {
            case Some(root) => {
                println(" " * depth + root.nodeName)
                preOrder(root.leftChild, depth+4)
                preOrder(root.rightChild, depth+4)
            }
            case None => println(" " * depth + "leaf")
        }
    }
}


val tree = new BinaryTree(
    "root", 
    Some(new BinaryTree(
        "a",
         Some(new BinaryTree("aa", None, None)),
         Some(new BinaryTree("ab", None, None)))),
    Some(new BinaryTree(
        "b",
        Some(new BinaryTree("ba", None, None)),
        Some(new BinaryTree("bb", None, None)))))


tree.preOrder(Some(tree))

root
    a
        aa
            leaf
            leaf
        ab
            leaf
            leaf
    b
        ba
            leaf
            leaf
        bb
            leaf
            leaf

Answer 3

把它想象成打开一大堆门，直到找到你要找的东西，然后你必须回去 close/check 其他的。

public void preOrder(BinaryTree root) {
    if(root != null) {
        System.out.println(root);
        preOrder(root.leftChild);  <-- this gets called and will start from the top of the function
        preOrder(root.rightChild); <-- how can this get called if the top one will always calls itself?
    }
}

我们可以用匹配的代码替换 preOrder 调用，如下所示：

public void preOrder(BinaryTree root) {
    if(root != null) { <-- note the if check
        System.out.println(root);

        if(root.leftChild!= null) { <-- note the if check
            System.out.println(root.leftChild.leftChild);
            preOrder(root.leftChild.leftChild);  <- this expands into another if block
            preOrder(root.leftChild.rightChild); <- this also expands
        }

       if(root.rightChild!= null) { <-- note the if check
            System.out.println(root.rightChild.leftChild);
            preOrder(root.rightChild.leftChild);  
            preOrder(root.rightChild.rightChild);
        }

    }
}

它一直向外扩展...直到您遇到停止递归的特殊条件 "base"。在这种情况下，当您找到树的叶节点时，即 node == null，它会停止扩展，因为 if 条件不再为真，并且一切都开始自行崩溃，或者换句话说，它可以继续正常执行代码块。

Answer 4

递归刚开始学的时候可能会觉得一头雾水。首先，你可以考虑一个子问题。对于 preOder，它总是先打印出根节点，然后是左节点，然后是右节点。您所需要的只是解决一个子问题。（下面是一个基本的简单树）

     root
    /    \
  left  right
  /        \
...        ...

现在回头看代码：

 if(root != null) {
    System.out.println(root);
    preOrder(root.leftChild);  // the left node now becomes another root, and keep making the next left node root until the next left node is null.
    preOrder(root.rightChild); // this line of code won't be executed until the last preOrder function call its root == null(hit the condition.)
 }

信任递归；如果您的条件正确，它将始终为您完成其余部分。我同意运行调试模式以便更好地理解。当您尝试了解代码的工作原理时，学习如何使用 "step in" 非常有用。

递归如何遍历树

How does recursion traversing through trees

java

recursion

binary-tree

binary-search-tree