не может остановить рекурсивную java

Question

Я пытаюсь найти узел с помощью его метки и добавить новый узел под целевым узлом, , когда я попытался использовать рекурсивный поиск, он всегда возвращает неверную цель или вернуть null. Кто-нибудь знает, как это исправить?

public TreeNode getNodeReference(String label){ 

    if(left!=null){ 
     if(check(left,label)==true) 
      return left; 
     left.getNodeReference(label); 
    } 

    if(middle!=null){ 
     if(check(middle,label)==true) 
      return middle; 
     middle.getNodeReference(label); 
    } 
    if(right!=null) 
    { if(check(right,label)==true) 
      return right; 
     right.getNodeReference(label); 
    } 
    return null; 
} 


public boolean check(TreeNode tree,String label){ 

    if(tree.getLabel().equals(label)) 
     return true; 
    else return false; 
} 

Answer 1

Если вы действительно просматриваете свой код, вы можете довольно четко понять, почему он вернет неверный результат. Я пометил путь кода ниже, если ни один из детей первого уровня дерева не соответствуют ярлыку (предположит, что левый/среднее/право являются всеми непустым):

public TreeNode getNodeReference(String label){ 

    if(left!=null){ // 1: left is not null 
    if(check(left,label)==true) // 2: no match, proceed to 3 
     return left; 
    left.getNodeReference(label); // 3: called, but why? no side effect, no return. 
    } 

    if(middle!=null){ // 4 
    if(check(middle,label)==true) // 5 
     return middle; 
    middle.getNodeReference(label); // 6 
    } 

    if(right!=null) { // 7 
    if(check(right,label)==true) // 8 
     return right; 
    right.getNodeReference(label); // 9 
    } 

    return null; // 10: and finally we're here and we return null 
} 

По сути, вы называете ребенок. getNodeReference (label), но это все, что вы делаете. Вы это называете. Затем вы отбрасываете возвращаемое значение и продолжаете, и поэтому ваш поиск эффективно никогда не опускается за пределы первого уровня узла, изначально называемого getNodeReference.

Так что для начала, это общая закономерность, что вы хотите:

if (child != null) { 
    if (check(child, label)) 
     return child; // match found 
    TreeNode childResult = child.getNodeReference(label); 
    if (childResult != null) 
     return childResult; // match found deeper in tree; this is what you did not do. 
} 

Это говорит, вот короче реализации (имейте в виду, что это не точно как то, что вы были, как и вашей реализации также пропущенной проверки фактического узла, который getNodeReference был первым призвал):

public TreeNode getNodeReference (String label) { 

    if (check(this, label)) 
     return this; 

    TreeNode childResult = null; 
    if (left != null) 
     childResult = left.getNodeReference(label); 
    if (childResult == null && middle != null) 
     childResult = middle.getNodeReference(label); 
    if (childResult == null && right != null) 
     childResult = right.getNodeReference(label); 

    return childResult; 

} 

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

Надеюсь, что это поможет.

Answer 2

Проблема в следующем: Вы ничего не делаете с возвращенным значением из внутреннего вызова.

Для Exemple:

1. левый не нулевой
2. чека возврата ложного
3. вызова getNodeReference с меткой
4. левой не является нулевым
5. проверки возвращающих
   (возврата верный первому вызову, но вам нечего его поймать)
6. средний не является нулевым

7. проверка ...
   ...

   X. Возвращение нуль;
   
   BOOM!