Jak zaimplementować wyszukiwanie z głębokim początkiem (DFS) w drzewie binarnym w języku Java?

Question

Zgodnie z wyjaśnieniem w the wikipedia article about depth-first search, myślę, że DFS na drzewie binarnym jest identyczny z preorder traversal root - left - right (mam rację?).

Ale właśnie zrobiłem małe wyszukiwanie i otrzymałem ten kod, którego autor twierdzi, że DFS potrzebuje drzewa do zapisania, czy węzeł był wcześniej odwiedzany (czy też potrzebujemy tego w przypadku wykresu?).

// copyright belongs to the original author 
public void dfs() { 
    // DFS uses Stack data structure 
    Stack stack = new Stack(); 
    stack.push(this.rootNode); 
    rootNode.visited=true; 
    printNode(rootNode); 
    while(!stack.isEmpty()) { 
     Node node = (Node)s.peek(); 
     Node child = getUnvisitedChildNode(n); 
     if(child != null) { 
      child.visited = true; 
      printNode(child); 
      s.push(child); 
     } 
     else { 
      s.pop(); 
     } 
    } 
    // Clear visited property of nodes 
    clearNodes(); 
} 

Czy ktoś może to wyjaśnić?

Answer 1

myślę dps na binarne drzewo jest tym samym jednym z korzenia preorder przemierzania -. Lewy - prawy (mam rację?)

głębokość pierwszego wyszukiwania może być przed-, w - lub przechodzenie po zamówieniu. Nie potrzebujesz stosu: łatwiej jest go realizować rekursywnie, w takim przypadku nie musisz oznaczać węzłów jako odwiedzanych.

Answer 2

Tak, jest w przedsprzedaży. Ale, tak naprawdę nie lubię mówić, że jest to przejście, ponieważ nie możesz przemierzać drzewa, zatrzymujesz się, gdy tylko znajdziesz swój element. Program, który wydrukowałeś, nie jest wyszukiwaniem, jest przejściem: drukujesz wszystko. Funkcja wyszukiwania, aby szukać w binarnym drzewie byłoby:

public boolean search(Tree t, int i) { 
    if(t == null) 
     return false; 
    elif(t.value() == i) 
     return true; 
    else 
     for(child in t.children()) { 
      if(search(child,i)) 
       return true; 
     } 
     return false; 
     //return search(t.leftTree(), i) or search(t.rightTree(),i) binary tree case 
}