我面临着经典的“它有效,但我不知道为什么!”的问题。我只是应用了我从另一个整数练习中知道的原则,但在这里我必须使用树。该方法测试成功。我应该计算一棵树的结,然后我会遍历它(在本例中:按顺序),每次我成功遍历(意思是:不面对空子树)时,我都会将其算作一棵树结。在这种情况下,我想知道为什么这段代码没有计算太多的结。例如,当我总是向左走并面对一棵空子树时,我不会一直向上直到到达一个可以向右走的结吗?为什么我的代码可以避免这种问题?
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());
}
最佳答案
你并没有真正在树上上下移动,你只需要向下移动并访问每个节点一次,并且你可以通过使你的树变得越来越简单来做到这一点。
考虑下面的树
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
关于java - 为什么我的计算树节的代码有效?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41747789/