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遞歸二叉樹

回答

相關問題