Поиск в несортированном дереве рекурсивно

Question

Я пытаюсь выполнить поиск элемента e в дереве, однако, как вы видите, мой поиск (Позиция, E) не возвращает позицию. Однако когда я добавляю «return null»; в конце метода. Он работает только тогда, когда позиция, которую я ищу, находится слева от большинства дочерних элементов ее родителя, и она возвращает null в противном случае. Как я могу заставить его работать, пока он не дойдет до конца дерева?

public Position<E> search(E e) { 
    return search(root(), e); 
} 

public Position<E> search(Position<E> p, E e) { 
    if(p.getElement().equals(e)) 
     return p; 
    for(Position<E> c: children(p)) 
      return search(c, e); 
} 

Answer 1

Я думаю, что проблема в этом цикле:

for(Position<E> c: children(p)) 
     return search(c, e); 

Представьте, что элемент, который вы ищете во втором потомка узла, а не первый. С приведенным выше кодом, на первой итерации цикла, вы будете рекурсивно исследовать первый ребенок, который возвращает false, а затем сразу же возвращает false, не имея возможности исследовать второго ребенка. Другими словами, ваш метод рассматривает только самого первого ребенка, поэтому он может не найти то, что вы ищете.

Чтобы исправить это, попробуйте переписывания кода, как это:

if(p.getElement().equals(e)) 
    return p; 

for(Position<E> c: children(p)) { 
    Position<E> result = search(c, e); 
    if (result != null) return result; 
} 
return null; 

Это делает рекурсивный вызов в каждом поддереве. Если какой-либо вызов не находит элемент, это нормально - вы просто продолжаете переход к следующему. Если какой-либо вызов находит элемент, вы его возвращаете. Если ни один из вызовов не находит этот элемент, вы возвращаете значение null, чтобы указать сбой.

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

Answer 2

Вам нужно отслеживать каждое поддерево и его возвращаемое значение. Попробуйте что-то вроде следующего:

public Position<E> search(E e) { 
    return search(root(), e); 
} 

public Position<E> search(Position<E> p, E e) { 
    if(p.getElement().equals(e)) { 
     return p; 
    } 
    for(Position<E> c: children(p)) { 
     Position tmp = search(c, e); 
     if (tmp != null) { 
      return tmp; 
     } 
    } 
    return null; 
} 

Спасибо,

Юрий