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

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

Я получаю вывод правильно. Но это немного грязно. Если вы видите метод trace (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

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

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

Редактировать : Если нужен путь к корневому узлу, достаточно простого логического возврата:

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

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

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
}

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

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