樹搜索功能沒有給出預期的結果

Question

我想知道爲什麼我在此代碼中獲得與方法containsData和containsData2相同的結果。

package rr.fe.op.lab.proc; 

class TreeNode { 
    TreeNode left; 
    TreeNode right; 
    String data; 
} 

class TreeProgram { 
    public static void main(String[] args) { 
     TreeNode node = null; 
     node = insert(node, "Han"); 
     node = insert(node, "Luke"); 
     node = insert(node, "Leia"); 
     node = insert(node, "Padme"); 
     node = insert(node, "Vader"); 
     node = insert(node, "Yoda"); 

     System.out.println("Writing tree inorder:"); 
     writeTree(node); 

     node = reverseTreeOrder(node); 
     System.out.println("Writing reversed tree inorder:"); 

     writeTree(node); 
     int size = sizeOfTree(node); 
     System.out.println("Number of nodes in tree is "+size+"."); 

     boolean found = containsData(node, "Padme"); 
     System.out.println("Searched element is found: "+found); 

     boolean found1 = containsData2(node, "Padme"); 
     System.out.println("Searched element is found: "+found); 
    } 

    static boolean containsData(TreeNode treeRoot, String data) { 
     if(treeRoot == null) 
      return false; 
     else if(data.compareTo(treeRoot.data) == 0) 
     return true; 
     else if(data.compareTo(treeRoot.data) < 1) 
      return containsData(treeRoot.left,data); 
     else 
      return containsData(treeRoot.right,data); 
    } 

    static int sizeOfTree(TreeNode treeRoot) { 
     if(treeRoot == null) 
      return 0; 
     else 
      return 1 + sizeOfTree(treeRoot.right) + sizeOfTree(treeRoot.left); 
    } 

    static TreeNode insert(TreeNode treeRoot, String data) { 
     if(treeRoot == null){ 
      TreeNode newnode = new TreeNode(); 
      newnode.data = data; 
      newnode.left = null; 
      newnode.right = null; 
      return newnode; 
     } 
     else if (data.compareTo(treeRoot.data) < 1) 
      treeRoot.left = insert(treeRoot.left,data); 
     else 
      treeRoot.right = insert(treeRoot.right,data); 
     return treeRoot; 
    } 

    static void writeTree(TreeNode treeRoot) { 
     if(treeRoot != null){ 
      writeTree(treeRoot.left); 
      System.out.println(treeRoot.data); 
      writeTree(treeRoot.right); 
     } 
    } 

    static TreeNode reverseTreeOrder(TreeNode treeRoot) { 
     if(treeRoot == null) 
      return null; 

     TreeNode node = new TreeNode(); 
     node = treeRoot.left; 
     treeRoot.left = treeRoot.right; 
     treeRoot.right = node; 

     reverseTreeOrder(treeRoot.left); 
     reverseTreeOrder(treeRoot.right); 
     return treeRoot; 
    } 

    static boolean containsData2(TreeNode treeRoot,String data){ 
     if (treeRoot == null) { 
      return false; 
     } 

     if (treeRoot.data == data){ 
      return true; 
     } else { 
      return containsData2(treeRoot.left,data) || containsData2(treeRoot.right,data); 
     } 

    } 
} 

我知道在倒轉樹之前，方法containsData工作正常。當我倒轉樹時，它不工作，這是可以的。我寫了一個方法containsData2，想法該方法可以找到樹是否顛倒的元素。當然，複雜性會更高。但是，與containsData2，我得到了相同的結果containsData，即false。我做錯了什麼？

Answer 1

的主要問題是，你把錯誤的變量在print語句：

boolean found1 = containsData2(node, "Padme"); 
System.out.println("Searched element is found: "+found); 

這應該是：

boolean found1 = containsData2(node, "Padme"); 
System.out.println("Searched element is found: "+found1); 

另一個重要的問題是，您要比較使用==字符串，這通常不會給你想要的結果。在這種特殊情況下，它是有效的，因爲你只使用文字字符串。比較是在這裏完成：

if (treeRoot.data == data){ 
    return true; 
} else { 
    return containsData2(treeRoot.left,data) || containsData2(treeRoot.right,data); 
} 

相反，比較使用equals方法的字符串，像這樣：

if (treeRoot.data.equals(data)){ 
    return true; 
} else { 
    return containsData2(treeRoot.left,data) || containsData2(treeRoot.right,data); 
} 

或者，如果你想簡化代碼進一步：

return treeRoot.data.equals(data) || 
     containsData2(treeRoot.left,data) || containsData2(treeRoot.right,data); 

有關比較字符串的更多信息，請參閱this question。

Answer 2

您誤解了遞歸。你現在正在做的是，搜索樹：

漢（他是不是帕德梅，讓我們深入更多） - >
_____Luke（他是不是帕德梅，讓我們深入更多 - >
__________Padme（嘿，這是她的！）返回true！
_____Going回盧克，他不是帕德梅，所以我們返回false
去回漢，他是不是帕德梅，所以我們返回false。

最後，你得到的「False」布爾值，「這不是你要找的節點嗎？」

你應該嘗試找到解決這個問題的另一種方法。 目前，你應該嘗試擺脫遞歸，當你會找到一個合適的節點。最簡單的方法是創建一個全局變量，並設置

done = true;

當找到Padme，然後打印結果時： System.out.println（「Searched element is found：」+ done）;