Java'da ikili ağaçta derinlikli ilk arama (DFS) nasıl uygulanır?

Question

the wikipedia article about depth-first search belgesinde anlatılanlara göre, ikili bir ağaç üzerindeki DFS'nin bir önyüklemenin kök - sol - sağıyla aynı olduğunu düşünüyorum (doğru muyum?).

Ama biraz daha arama yaptım ve bu kodu aldım, yazar DFS'nin daha önce ziyaret edilmişse kayıt için bir ağaca ihtiyacı olduğunu iddia ediyor (ya da bir grafikte buna ihtiyacımız var mı?).

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

Bunu açıklayan olabilir mi?

Answer 1

Ben bir ikili ağaç üzerinde dps ön sipariş geçişi kökü ile aynı olduğunu düşünüyorum - sol -. Doğru (sağ am i?)

Derinlik öncelikli arama içinde, önceden olabilir - veya sipariş sonrası geçiş. Bir yığına ihtiyacınız yoktur: yinelemeli olarak uygulamak daha kolaydır, bu durumda düğümleri de ziyaret edildiği şekilde işaretlemeniz gerekmez.

Answer 2

Evet, ön sipariştir. Ancak, ağacın üzerinden geçemeyeceğinizden beri bir geçişin olduğunu söylemekten hoşlanmıyorum, elemanınızı bulduğunuz anda durursunuz. Yazdırdığınız program bir arama değil, bir geçiş: herşeyi yazdırıyorsunuz. bir ikili ağaçta aramak için bir arama fonksiyonu olacaktır:

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 
}