Нужна помощь при возврате из рекурсивного метода

Question

Я пытаюсь отслеживать путь узла в двоичном дереве (а не двоичном дереве поиска). Учитывая узел, я пытаюсь напечатать значения пути из корня.

Я написал следующую программу.

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

Я получаю выход правильно. Но его беспорядок. Если вы видите трассировку метода (Node, Node), я печатаю значения, которые я не должен делать. Я хочу, чтобы метод трассировки был правильно завершен. По крайней мере, я должен убить рекурсивную структуру на этапе, в котором я сталкиваюсь с условием if.

Просьба сообщить.

Answer 1

Хорошо, вам нужно убить рекурсию, как только вы найдете свой узел. Достаточно просто. Измените метод трассировки, чтобы вернуть логическое сообщение, если узел был найден. Таким образом, мы сразу же вернемся к дереву сразу после нахождения узла.

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

Я предполагаю, что это домашняя работа, поэтому я дам несколько указателей вместо некоторого кода.

• ваш метод трассировка делает рекурсивный спуск, поэтому стек не требуется - вы можете построить структуру пути, возвращаясь из найденного узла
• если ваш метод использует логическое или список возвращаемого значения, вы можете распечатать путь во время возвращения, или создать список с узлами для печати после того, как метод поиска возвращает

Edit: Если узел пути к корню желанное, простое логическое возвращение достаточно:

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

Если вам необходим путь от корня до узла, вы можете передать список, чтобы получить узлы в следующем порядке:

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

в качестве альтернативы вы можете построить путь на обратном пути и вернуться в список.

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

Возвращение булева от следа и решить, следует ли продолжать поиск на основе значения возвращается из рекурсивного вызова.

Answer 4

Что-то вроде этого?

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

Рекурсивная функция без использования стека. Рекурсия эквивалентна стеку techincally, и вам не нужно создавать стек при выполнении recusrion.

PS: Я пишу псевдокод. Перепишите его сами, чтобы скомпилировать его :)

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 
}