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

Question

我面临着经典的“它有效，但我不知道为什么!”的问题。我只是应用了我从另一个整数练习中知道的原则，但在这里我必须使用树。该方法测试成功。我应该计算一棵树的结，然后我会遍历它(在本例中:按顺序)，每次我成功遍历(意思是:不面对空子树)时，我都会将其算作一棵树结。在这种情况下，我想知道为什么这段代码没有计算太多的结。例如，当我总是向左走并面对一棵空子树时，我不会一直向上直到到达一个可以向右走的结吗？为什么我的代码可以避免这种问题？

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

你并没有真正在树上上下移动，你只需要向下移动并访问每个节点一次，并且你可以通过使你的树变得越来越简单来做到这一点。

考虑下面的树

  a
 / \
b   c
   / \
  d   e

因此，您从根开始并检查它是否为空(是否为空)，因此返回 1 + numberKnots(left) + numberKnots(right) 的结果。左右也是树，它们比a更简单

left  right
  b    c
      / \
     d   e

现在你检查 b 树，它是空的，所以它只返回 0。然后你检查 c 树，它不为空，所以你返回 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