Поиск узла в дереве в Java

Question

У меня есть бинарное дерево, сделанное с помощью следующего конструктора:

public Person(String name, int age, char gender, Person c1, Person c2) 

где c1 является левым потомком и c2 является правильным ребенком.

Я хочу написать метод, который ищет определенное имя в пределах максимальной генерации. Например, a.depthFirstSearch(Eva, 1);, где Eva - это имя для поиска, а 1 - максимальное количество поколений (или уровней), на которые я могу смотреть.

Вот что у меня есть: EDIT:

public Person depthFirstSearch(String name, int maxGeneration) 
{ 
    { 
Person temp; 
if (maxGeneration>1){ 
    if (this.name.equals(name)){ 
     temp=this; 
     return temp; 
     } 
    else{ 
    if (child1!=null) 
     temp=child1.depthFirstSearch(name, maxGeneration-1); 
    if (child2!=null) 
     temp=child1.depthFirstSearch(name, maxGeneration-1); 
    } 
} 
return null; 
} 
} 

Там две проблемы здесь. Я думаю, что глубина сбрасывается до 0 каждый раз, когда функция вызывает себя, поэтому я знаю, что могу либо отслеживать глубину где-то еще, либо находить альтернативу. Другая проблема, я думаю, в том, что child2 никогда не достигается, так как я возвращаюсь к child1. Я не совсем уверен, как это работает, если кто-то может это объяснить, это было бы здорово. Любые предложения по некоторым исправлениям?

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

Answer 1

Поскольку вы уменьшаете maxGeneration в каждом рекурсивном вызове, вам не нужен переменная depth вообще: когда maxGeneration == 0 вы просто не найти больше и вернуться null.

Что касается вашей другой проблемы, вместо прямого возврата значения child1.depthFirstSearch(...) сохраните значение во временной переменной. Если это не null, вы нашли узел, поэтому немедленно верните его, в противном случае продолжите поиск под child2.

---

Update:

Это должно быть if (maxGeneration >= 1) ... (больше или равно), в противном случае последний звонок с maxGeneration == 1 всегда возвращает нуль. Кроме того, вы можете просто проверить 0 и обратно нуль:

if (maxGeneration == 0) 
    return null; 

// rest of your code 

Кроме того, вы еще не используете возвращаемое значение, чтобы проверить, если узел был на самом деле находится в левом поддереве или нет. Прямо сейчас, даже если вы найдете узел под child1, вы по-прежнему выглядите под child2, и вы в конечном итоге вернете нуль, что неверно. Вам нужно искать под child2 только если левый поиск дал нуль:

Person temp; 
if (child1 != null) { 
    temp = child1.depthFirstSearch(name, maxGeneration-1); 
    if (temp != null) 
    return temp; // found the node, just return 
} 
// otherwise the following code will execute 
if (child2 != null) { 
    temp = child2.depthFirstSearch(name, maxGeneration-1); 
    if (temp != null) 
    return temp; // found the node, just return 
} 
// didn't find node under either child 
return null;