Модификация функции обхода дерева DFS - PullRequest
Новая
       37

Модификация функции обхода дерева DFS

1 голос
/ 08 марта 2012

Пожалуйста, найдите ниже мою реализацию для DFS.

protected void DFS(String search) {
    for(Tree<T> child : leafs) {
        if(child.value.equals(search))
            return;
        else 
            child.DFS(search);            
        System.out.println(child.value);     
    }
}

Цель - остановить обход при поиске узла, значение которого находится в поиске переменной.Однако указанная выше функция продолжает проходить по дереву даже за объявленным поисковым узлом.Может ли кто-нибудь помочь мне изменить вышеуказанную функцию?

Спасибо.

Изменить 1 

protected boolean DFS(String anaphorKey) {
    boolean found = false;
    for(Tree<T> child : leafs) {
        if(child.head.equals(anaphorKey))
            return true;
        found = child.DFS(anaphorKey);
        if(found == true)
            break;            
        System.out.println(child.head);     
        //System.out.println("anaphorKey: "+anaphorKey);
    }
    return found;
}

Попытка реализовать предложенное предложение ответа (@ SJuan76).Реализация выше не работает должным образом.Не могли бы вы указать мне место, где код не соответствует предложенной логике?

Ответы [ 2 ]

3 голосов
/ 08 марта 2012

новичок, могу ли я предложить реализацию, использующую классический цикл for (в отличие от расширенного цикла for, используемого сейчас), который позволяет немного лучше интегрировать ваше условие остановки, что-то вроде: 

protected boolean DFS(String key) {
    boolean found = false;

    for(int i = 0; i < leafs.size() && !found; i++) {
        Tree<T> child = leafs.get(i);

        if(child.head.equals(key))
            found = true;
        else
            found = child.DFS(key);
    }

    return found;
}

Так что, как только ваше условие найдено, «найдено» становится истинным, и ваш цикл останавливается.

То, что вы, возможно, забыли, - это часть рекурсии "found = child.DFS (ключ)", где вам нужно запомнить результат ваших рекурсивных вызовов, чтобы ВСЕ ваши циклы for в цепочке все разорвались, как вы вернетесь.

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

1 голос
/ 08 марта 2012

Опция A (Ницца): функция возвращает значение, когда узел найден, он возвращает другое значение, чем если узел не был найден. Когда вы вызываете метод, если вы получаете значение found, вы останавливаете цикл и возвращаете значение found.

Вариант B (Гадкий): если найдено, то исключение (лучше, если это ваша собственная реализация). Не забудьте поймать его.

Опция C (Uglier): то же самое с глобальными (статическими) переменными.

ОБНОВЛЕНИЕ 1:

Похоже, ваш метод должен работать нормально, можете ли вы проверить (System.out.println), найдено ли ваше значение?

В более личном мнении я бы нашел 

protected boolean DFS(String anaphorKey) { 
  for(Tree<T> child : leafs) { 
    if(child.head.equals(anaphorKey)) 
      return true; 
    if(child.DFS(anaphorKey))  // No need to store value. No need to check == true (it is implicit)
      return true;             // If we are in this line the value was found, always return true
    System.out.println(child.head);      
    //System.out.println("anaphorKey: "+anaphorKey); 
  } 
  return false;  // If the method did not exit previously it was because the value was not found, so in this line always return false
}

более читабельно (но оно должно работать точно так же, как ваша реализация)

...