Java递归二叉树

欢迎！我有一个名为less的递归公共静态方法，它需要一个树节点（原始二叉树，不是真正的搜索树）和一个int参数，如果树中的所有值都小于整数，则返回该参数。所以，我会用一个public class TN { public int value; public TN left, right; public TN(int v, TN l, TN r) {value = v; left = l; right = r;} } 所以，我的方法是这样的：Java递归二叉树

public static boolean less(TN s, int toFind){ 
if (s == null) 
    return true; 
else{ 
if(s.value <= toFind) 
    return less(s.left, toFind) && less(s.right, toFind); // right here do I return true? or do I have to somehow recall recursively 
else 
    return false; 
}

我在想，如果这是正确的还是我失去了一些东西???我必须返回真假吗？

来源

2009-10-16 Roxy

return less(s, toFind);

应该是：

return less(s.left, toFind) && less(s.right, toFind);

我不知道为什么功能是静态的。

正如前面提到的，你的第一个部分应该仅仅是：

if (s == null) return true;

（编辑：这将让你得到真正的结果，当所有节点满足条件你有一个==在那里，应该是一个<）。编辑：好吧，你有很多问题，而不仅仅是我提到的问题。你需要在逻辑上逐步完成你的代码。

你需要遍历你的树，所以你需要在你的子节点上调用你的函数。接下来，您需要返回true作为默认结果。这样，当您达到的数字大于您要查找的数字时，您可以立即返回错误而无需遍历任何子项。我希望我已经足够帮助你，让你自己完成其余的部分。

来源

2009-10-16 18:52:48 CookieOfFortune

因此，对于else语句，我可以只返回调用方法而不是返回错误的权利？ – Roxy 2009-10-16 19:21:11

那么，你需要有一个相对的全局变量，你在分支之前检查。例如。 “if（found == true）return false;”，然后将else改为“else {found = true; return false}”。这样，如果找到的数字大于要查找的数字，则会将其设置为true。然后每隔一个分支也会返回。您只需确保每次调用该函数都可以看到相同的“找到”。 – CookieOfFortune 2009-10-16 19:59:04

首先，if (s = null)应该是if (s == null)，因为您正在进行比较，未将s的值设置为null。

声明return less(null, toFind);一直在调用你的方法 - 你会溢出你的堆栈。

来源

2009-10-16 18:50:53

另外，'if（s = null）'不会编译。 – 2009-10-16 18:52:53

马特，在发布我的答案后刷新页面时对其进行了编辑。但是，是的。这段代码有多个问题。 – 2009-10-16 18:54:03

有很多更优雅的OO方法来写这个。我的建议是让less()成为TN类的非静态成员函数。这样，如果树的根节点被称为root，您只需拨打root.less()即可。然后，每次致电less()的电话将拨打left.less()和right.less()。

既然你发布的代码甚至不会编译，我想知道你是否使用IDE，或者甚至尝试使用javac来编译你的类。如果您不熟悉Java，我强烈建议您获取Eclipse，Netbeans或其他IDE。

来源

2009-10-16 18:56:24

请注意，您的函数无法返回true，因为每次终止递归时，都会返回false？问题在于你的第一次检查。你说“树中的所有值都小于整数”。那么，在一棵空树中，所有的值（其中都没有）确实小于任何整数，所以在这种情况下你应该返回true。

此外，虽然你说“小于”，你是比较平等，所以你实际上检查是否所有的值都等于整数，而不是小于它。

来源

2009-10-16 19:02:42 JaakkoK

Java递归二叉树

回答

相关问题