Реализация DFS для дерева в Java - PullRequest
Новая
       27

Реализация DFS для дерева в Java

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

Пожалуйста, найдите определение класса Tree ниже.

public class Tree<T>{

  private T head;

  private List<Tree<T>> leafs = new ArrayList<>();

  private Tree<T> parent = null;

  private Map<T, Tree<T>> locate = new HashMap<>();

  public Tree(T head) {
    this.head = head;
    locate.put(head, this);
  }


  public void addLeaf(T root, T leaf) {
    if (locate.containsKey(root)) {
     locate.get(root).addLeaf(leaf);
    } else {
      addLeaf(root).addLeaf(leaf);
    }
  }

  public Tree<T> addLeaf(T leaf) {
    Tree<T> t = new Tree<>(leaf);
    leafs.add(t);
    t.parent = this;
    t.locate = this.locate;
    locate.put(leaf, t);
    return t;
  }
}

Объект класса Tree создается в другом классе, и узлы добавляются прямым способом (с помощью функции addLeaf (node)).Этот процесс строит дерево в порядке.Кто-нибудь сможет предложить реализацию функции DFS на построенном дереве, придерживаясь приведенного выше определения класса?

Спасибо.

Это то, что я пробовал.Да, это дает мне бессмысленные результаты. 

protected void DFS() {
    for(Tree<T> child : leafs) {
        DFS();
        System.out.println(child);
    }
}

Код взят из третьего комментария на ссылка 

protected void DFS() {
  for(Tree<T> child : leafs) {
      child.DFS();
      System.out.println(child.head);
  }
}

решен!

1 Ответ

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

Ты рядом. Печать должна быть значением узла, а рекурсия должна быть на дочернем элементе.

...