为什么我计算树节的代码有效？

Question

我面临着经典的 "It works, but I don't know why!" 问题。我只是应用了我从另一个整数练习中知道的原则，但在这里我必须使用树。方法测试成功。我应该数一棵树的结数，我这样做是遍历它（在本例中：有序），每次我成功遍历（意思是：不面对空子树），我把它算作结。在这种情况下，我想知道为什么这段代码没有计算太多结。例如，当我总是向左走并面对一个空的子树时，我不会一直向上走直到我到达一个可以向右走的结点吗？为什么我的代码可以避免这种问题？

public static int numberKnots (Tree b) {

  int count = 0;

  if (b.empty()) {
    return 0;
  }

  else {

  traverse.inorder(b.left());
  traverse.inorder(b.right());
  count = 1;
  }

  return count + numberKnots(b.left()) + numberKnots(b.right());

}

Answer 1

由于您使用的是递归，它不会遍历相同的节点twice.So 您的代码完美运行fine.consider (A) 有两个 child 节点 (B)&(C)此外 (B) 有两个 childs (B1)&(B2)。当通过递归遍历时，它使用堆栈。“（将 s 视为我们的堆栈）”。首先控制到达节点（A），因为它已经离开child（A）被推入堆栈并且控制被转移到（B）现在控制被转移到（B）的左边child（ B1) 和 (B) 被压入堆栈，因为 (B1) 没有任何 childs 它被计算并且控制被转移到堆栈顶部，即 (B) 和 (B) 被计算现在控制被转移到 (B) 的右边 child 它 (B2) 和 (B2) 被计算并且控制权被转移到 (B)。现在 (B) 没有任何代码剩余因此它从堆栈中弹出并且控制被转移到 (A) 并且 (A) 被计数并且控制被转移到它的右边 child (c)。同样地所有节点被计数而不重复。

希望对您有所帮助

Answer 2

你并不是真的在树上上下移动，你只是向下移动并访问每个节点一次，你通过让你的树越来越简单来做到这一点。

考虑以下树

  a
 / \
b   c
   / \
  d   e

所以你从根开始，检查它是否为空，它不是，所以你 return 1 + numberKnots(left) + numberKnots(right) 的结果。 left 和 right 也是树，比 a

简单

left  right
  b    c
      / \
     d   e

所以现在你检查 b 树，它是空的所以它只是 returns 0。然后你检查 c 树，它不是空的所以你 return 1 + countKnots(left (of c)) + countKnots(right (of c)) 等等。

计算的每一步都是：

countKnots(a) 
 = 1 + countKnots(b) + countKnots(c) 
 = 1 + 0 + countKnots(c) 
 = 1 + 0 + 1 + countKnots(d) + countKnots(e) 
 = 1 + 0 + 1 + 0 + countKnots(e) 
 = 1 + 0 + 1 + 0 + 0
 = 2

您的代码可以简化为

public static int numberKnots (Tree b) {
  if (b.empty()) {
    return 0;
  } else {
    return 1 + numberKnots(b.left()) + numberKnots(b.right());
  }
}

但是好像不能处理不包含左右节点的树节点，所以下面的树会报错

a
 \
  c

为什么我计算树节的代码有效？

Why does my code for counting the knots of a tree work?

java

recursion

tree

tree-traversal