Hai bisogno di aiuto per tornare da un metodo ricorsivo

Question

Sto cercando di tracciare il percorso di un nodo in un albero binario (non un albero di ricerca binario). Dato un nodo, sto provando a stampare i valori del percorso dalla radice.

Ho scritto il seguente programma.

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

Sto ottenendo l'uscita correttamente. Ma è un po 'disordinato. Se vedi il metodo trace (Node, Node), sto stampando i valori che non dovrei fare. Voglio che il metodo trace sia completato correttamente. Almeno, dovrei uccidere la struttura ricorsiva nello stadio in cui incontro la condizione if.

Si prega di avvisare.

Answer 1

OK, è necessario eliminare la ricorsione una volta trovato il nodo. Abbastanza semplice Cambia il tuo metodo di traccia per restituire un booleano che ci dice se il nodo è stato trovato. In questo modo, torniamo subito all'albero subito dopo aver trovato il nodo.

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

Presumo che questo è compito, quindi fornirò alcuni puntatori anziché un codice.

• il metodo di traccia non una discesa ricorsiva, quindi lo stack non è necessaria - si può costruire la struttura del percorso mentre tornava da un nodo trovato
• se il metodo utilizza un valore di ritorno booleano o elenco, è possibile stampare il percorso mentre tornava, o di costruire una lista con i nodi per stampare dopo che il metodo di ricerca restituisce

Edit: Se il nodo percorso radice è voluto, un semplice ritorno booleano basta:

0.123.

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; 
} 

Se è necessario il percorso dalla radice al nodo, è possibile passare un elenco per ricevere i nodi in ordine:

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; 
} 

in alternativa si può costruire il percorso sulla via del ritorno e di ritorno, una lista.

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

Ritorna un valore booleano da traccia e decidere se continuare o meno la ricerca in base al valore viene restituito dalla chiamata ricorsiva.

Answer 4

Qualcosa di simile?

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

Ecco una funzione ricorsiva senza alcun utilizzo di stack. Una ricorsione equivale a impilare tecnicamente e non è necessario impilare quando si fa il recustion.

PS: Sto scrivendo uno pseudo codice. Riscrivilo tu stesso per farlo compilare :)

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 
}