Функция поиска дерева не дает ожидаемого результата

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

Основная проблема заключается в том, что вы поставили неправильный переменную в вашем операторе печати:

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 (эй, это ее !) возвращает истину!
_____Going назад к Люку, он не Падм, поэтому мы возвращаем ложные
Возвращаясь к Хань, он не Падм, поэтому мы возвращаем ложь.

в конце концов, ваш получить «False» boolean, «Это не тот узел, который вы ищете?»

Вы должны попытаться найти другой подход к этой проблеме. На данный момент вы должны попытаться выйти из рекурсии, когда найдете подходящий узел. Самый простой способ - создать глобальную переменную и установить

done = true;

Когда найдено Падме, а затем при печати результата: System.out.println («найден найденный элемент:« + сделано »);