Come implementare la ricerca in profondità (DFS) su un albero binario in java?

Question

Secondo quanto spiegato in the wikipedia article about depth-first search, penso che DFS su un albero binario sia identico a un preorder traversal root - left - right (sto bene?).

Ma ho appena fatto una piccola ricerca e ho ottenuto questo codice, l'autore di cui afferma che DFS ha bisogno di una struttura per registrare se il nodo è stato visitato prima (o ne abbiamo bisogno nel caso di un grafico?).

// 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(); 
} 

Qualcuno potrebbe spiegarlo?

Answer 1

Penso dps su un albero binario è la stessa con la radice di preordine traversal - sinistra -. A destra (dico bene?)

ricerca profondità prima può essere pre-, in -, o attraversamento post-ordine. Non è necessario uno stack: è più semplice implementarlo in modo ricorsivo, nel qual caso non è necessario contrassegnare i nodi come visitati.

Answer 2

Sì, è preordinato. Ma, non mi piace dire che è una traversata visto che potresti non attraversare l'albero, ti fermi non appena trovi il tuo elemento. Il programma che hai stampato non è una ricerca, è un attraversamento: stai stampando tutto. Una funzione di ricerca per cercare in un albero binario potrebbe essere:

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 
}