Potrzebujesz pomocy w powrocie z metody rekurencyjnej

Question

Próbuję prześledzić ścieżkę węzła w drzewie binarnym (a nie binarnym drzewie wyszukiwania). Biorąc pod uwagę węzeł, próbuję wydrukować wartości ścieżki z katalogu głównego.

Napisałem następujący program.

package dsa.tree; 

import java.util.Stack; 

public class TracePath { 
    private Node n1; 

    public static void main(String args[]){ 
     TracePath nodeFinder = new TracePath(); 
     nodeFinder.find(); 
    } 

    public void find(){ 
     Tree t = getSampleTree(); 
     tracePath(t,n1); 
    } 

    private Tree getSampleTree() { 
     Tree bsTree = new BinarySearchTree(); 
     int randomData[] = {43,887,11,3,8,33,6,0,46,32,78,76,334,45}; 
     for(int i=0;i<randomData.length;i++){ 
      bsTree.add(randomData[i]); 
     } 
     n1 = bsTree.search(76); 
     return bsTree; 
    } 

    public void tracePath(Tree t, Node node){ 
     trace(t,node); 
    } 

    Stack<Node> mainStack = new Stack<Node>(); 

    public void trace(Tree t, Node node){ 
     trace(t.getRoot(),node); 
    } 

    private void trace(Node parent, Node node){ 
     mainStack.push(parent); 
     if(node.data == parent.data){ 
      for(Node iNode:mainStack){ 
       System.out.println(iNode.data); 
      } 
      return; 
     } 
     if(parent.left != null){ 
      trace(parent.left, node); 
     } 
     if(parent.right!=null){ 
      trace(parent.right, node); 
     } 
     mainStack.pop(); 
    } 
} 

Dostaję poprawnie dane wyjściowe. Ale jego rodzaj bałaganu. Jeśli widzisz śledzenie metody (Węzeł, Węzeł), drukuję wartości, których nie powinienem robić. Chcę, aby metoda śledzenia została poprawnie ukończona. Przynajmniej powinienem zabić strukturę rekursywną na etapie, w którym napotykam warunek if.

Prosimy o radę.

Answer 1

Okej, musisz zabić rekursję, gdy znajdziesz swój węzeł. Wystarczająco proste. Zmień metodę śledzenia, aby zwrócić wartość boolowską informującą nas, czy węzeł został znaleziony. W ten sposób idziemy z powrotem do drzewa zaraz po znalezieniu węzła.

private boolean trace(Node parent, Node node){ 
    mainStack.push(parent); 
    if(node.data == parent.data){ 
     for(Node iNode:mainStack){ 
      System.out.println(iNode.data); 
     } 
     return true; 
    } 
    if(parent.left != null){ 
     if (trace(parent.left, node)) return true; 
    } 
    if(parent.right!=null){ 
     if (trace(parent.right, node)) return true; 
    } 
    mainStack.pop(); 
    return false; 
} 

Answer 2

Zakładam, że to praca domowa, więc podam kilka wskazówek zamiast jakiegoś kodu.

• metoda śladu nie rekurencyjny zejście, dlatego stos nie jest potrzebna - można zbudować strukturę ścieżki podczas powrotu z znalezionego węzła
• jeśli metoda wykorzystuje logiczną lub listy wartości zwracanej, można drukować ścieżka podczas powrotu, lub zbudować listę z węzłami do wydrukowania po metodę wyszukiwania zwraca

Edit: Jeśli węzeł ścieżka do korzenia jest poszukiwany, prosta logiczna powrót wystarczy:

private boolean trace(Node parent, Node node) { 
    boolean found = (node.data == parent.data) 

    if (!found && parent.left != null) { 
     found = trace(parent.left, node); 
    } 
    if (!found && parent.right != null){ 
     found = trace(parent.right, node); 
    } 

    if (found) { 
     System.out.println(parent.data); 
    } 

    return found; 
} 

Jeśli potrzebujesz ścieżkę od korzenia do węzła, można przekazać listę otrzymywać węzły w kolejności:

private boolean trace(Node parent, Node node, List path) { 
    boolean found = (node.data == parent.data) 

    if (!found && parent.left != null) { 
     found = trace(parent.left, node); 
    } 
    if (!found && parent.right != null){ 
     found = trace(parent.right, node); 
    } 

    if (found) { 
     path.add(0, parent); 
    } 

    return found; 
} 

alternatywnie można zbudować ścieżkę na drodze z powrotem i zwrócić w postaci listy.

private List trace(Node parent, Node node) { 
    List path = null; 

    if (null != node) { 
     if (node.data == parent.data) { 

      path = new ArrayList(); 
     } else { 
      path = trace(parent.left, node); 

      if (null == path) { 
       path = trace(parent.right, node); 
      } 
     } 
     if (null != path) { 
      path.add(0, parent); 
     } 
    } 
    return path; 
} 

Answer 3

Zwraca wartość logiczną ze śledzenia i decyduje, czy kontynuować wyszukiwanie w oparciu o wartość zwracaną przez wywołanie rekursywne.

Answer 4

Coś takiego?

public Stack<Node> findPath(Node src, Node dest, Stack<Node> alreadyCollected) { 
    if (src == dest) 
     return alreadyCollected; 
    if (src.left == null && src.right == null) 
     return null; 
    if (src.left != null) { 
     Stack<Node> toTheLeft = new Stack<Node>(alreadyCollected); 
     toTheLeft.push(src.left); 
     Stack<Node> result = findPath(src.left, dest, toTheLeft); 
     if (result != null) 
      return result; 
    } 
    List<Node> toTheRight = new Stack<Node>(alreadyCollected); 
    return findPath(src.right, dest, toTheRight); 
} 

Answer 5

Oto funkcja rekursywna bez użycia stosu. Rekursja jest równoważna stosowi w sposób techniczny i nie musisz używać stosu podczas robienia rekursji.

PS: Piszę pseudo kod. Przepisz sam, aby go skompilować :)

bool trace(Node curr, Node n, Path path){ 
    if(curr == null) 
     return; 
    if(n == curr){ 
     path.insertAtEnd(curr); 
     return true; 
    } 

    if(trace(curr.left, n, path)){ 
     path.insertAtEnd(curr); 
     return true; 
    } 
    if(trace(curr.right, n, path)){ 
     path.insertAtEnd(curr); 
     return true; 
    } 
    return false 
}