Necesito ayuda para regresar de un método recursivo

Question

Estoy intentando rastrear la ruta de un nodo en un árbol binario (no un árbol de búsqueda binario). Dado un nodo, estoy tratando de imprimir los valores de la ruta desde la raíz.

He escrito el siguiente programa.

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

Estoy recibiendo la salida correctamente. Pero es un poco desordenado. Si ve el método trace (Node, Node), estoy imprimiendo los valores que no debo hacer. Quiero que el método de seguimiento se complete correctamente. Al menos, debería matar a la estructura recursiva en la etapa en la que encuentro la condición if.

Por favor, asesorar.

Answer 1

De acuerdo, tiene que matar la recursión una vez que encuentre su nodo. Suficientemente simple. Cambie su método de seguimiento para devolver un booleano que nos diga si se encontró el nodo. De esa manera, volvemos al árbol inmediatamente después de encontrar el 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

Supongo que esto es tarea, así que daré algunos punteros en lugar de algunos códigos.

• su método de trazo no un descenso recursivo, por lo tanto, no es necesaria la pila - se puede construir la estructura de ruta cuando regresaba de un nodo encontrado
• si su método utiliza un valor de retorno booleano o la lista, puede imprimir la ruta de acceso al regresar, o crear una lista con los nodos para imprimir después de que el método de búsqueda devuelve

Editar: Si se quería que el nodo de ruta a la raíz, un simple retorno booleano es suficiente:

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

Si necesita la ruta desde la raíz hasta el nodo, se puede pasar una lista para recibir los nodos en orden:

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

, alternativamente, se puede construir el camino en su camino de ida y retorno en forma de 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

devolver un valor booleano desde trazas y decidir si continuar o no con la búsqueda basada en el valor que se devuelve desde la llamada recursiva.

Answer 4

¿Alló como esto?

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

Aquí hay una función recursiva sin uso de la pila. Una recursión es equivalente a la pila techincally y no debe necesitar pila cuando se hace recusrion.

PD: Estoy escribiendo un pseudo código. Reescríbelo usted mismo para obtenerlo compilado :)

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 
}