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

Question

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

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

, где c1 - левый дочерний элемент, а c2 - правый дочерний.

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

Вот что у меня есть: РЕДАКТИРОВАТЬ:

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.

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

---

Обновление:

Это должно быть 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;