Обход дерева не выводит желаемое решение

Question

(java)

У меня есть класс с именем Узел , который имеет следующие поля:

1. значение (целое число)
2. connectedNodes (массив объектов Node , всегда имеет одинаковый размер = 2)
3. комбинация (объект Combination class)

Combination class имеет одно поле с именем messageContext , давайте просто скажем, что это сообщение, которое должно отображаться на экране, когда что-то происходит (описано позже).

Также у нас есть одно дерево объект, который имеет только одно поле: root ( Узел объект)

Теперь предположим, что у нас есть одна строка с именем комбинацияStr = "1121 ». Теперь мы используем Tree метод с именем addCombination :

public void addCombination(Combination finalCombination, Node current, String combination, int counter) {

    if(counter==combination.length()) {
        return;
    }

    int value = combination.charAt(counter)-48;
    if(current.connectedNodes[value-1]==null) {
        current.connectedNodes[value-1] = new Node(value);
    }
    if(counter==combination.length()-1) {
        current.combination = finalCombination;
        return;
    }
    addCombination(finalCombination,current.connectedNodes[value-1],combination,counter+1);

}

finalCombination объект - это объект, который будет назначен последнее Узел поле комбинация , добавленное в Дерево для одной комбинацияСтр . Итак, мы используем эту функцию для создания древовидной структуры, которая имеет путь: -1 (root) -> 1 -> 1 -> 2 -> 1 Когда мы подходим к последнему, обходим дерево , должно появиться сообщение. Это messageContext из finalCombination .

Хорошо, теперь давайте используем while (true) l oop, которое позволит нам ввести число, которое будет похоже на выбор пути. Если мы введем 1, мы будем go к узлу 1 и будем иметь другие варианты выбора.

Пока l oop выглядит следующим образом:

    Scanner scanner = new Scanner(System.in);
    Node currentNode = tree.root;
    while(true) {
        for(Node node: currentNode.connectedNodes) {
            if(node!=null) {
                System.out.print(node.value + " ");
                continue;
            }
            System.out.print("nullnode ");
        }
        System.out.println("");
        if(currentNode.combination!=null) {
            System.out.println(currentNode.combination.messageContext);
        }
        if(currentNode.connectedNodes[0]==null && currentNode.connectedNodes[1]==null) {
            currentNode = tree.root;
            System.out.println("root");
        }
        int x = scanner.nextInt();
        currentNode = tree.takeStep(currentNode,x);
    }

Итак, что мы делаем здесь фактически выводится значение текущего узла, затем печатать значения узлов мы можем go. Если Node не существует, мы печатаем nullnode . Метод takeStep () выглядит следующим образом:

public Node takeStep(Node current, int value) {
    if(current.connectedNodes[value-1]!=null) {
        return current.connectedNodes[value-1];
    }
    return this.root;
}

Он просто проверяет, существует ли узел, к которому мы хотим go, и возвращает этот узел, если он это делает. Если он не существует, он вернет нас к root.

Но в чем проблема с этим кодом?

Хорошо, посмотрите на весь основной класс:

    Tree tree = new Tree(new Node(-1));
    String[] combination = {"1121","11","2212"};
    for(String s: combination) {
        Combination tempCombination = new Combination();
        tempCombination.messageContext = s + " ova poruka";
        tree.addCombination(tempCombination,tree.root,s,0);
        tree.traverse(tree.root);
        System.out.println("END");
    }

    Scanner scanner = new Scanner(System.in);
    Node currentNode = tree.root;

    while(true) {
        System.out.println(currentNode.value);
        for(Node node: currentNode.connectedNodes) {
            if(node!=null) {
                System.out.print(node.value + " ");
            }
            else {
                System.out.print("nullnode ");
            }
        }
        int x = scanner.nextInt();
        if(currentNode.combination!=null) {
            System.out.println(currentNode.combination.messageContext);
            if(currentNode.connectedNodes[0]==null && currentNode.connectedNodes[1]==null) {
                currentNode = tree.root;
                break;
            }
        }
        currentNode = tree.takeStep(currentNode,x);
    }

Когда мы введем номер x, мы позвоним takeStep и проверим, существует ли этот узел, связанный с текущим. Но проблема в том, что когда мы вводим 1, он печатает все нормально, когда мы снова вводим 1, он печатает все нормально, когда мы вводим 2, он печатает все нормально ... но когда мы вводим 1 снова, он говорит, что есть 2 нулевые узлы, и по какой-то причине он не меняется на root. Кто-нибудь может мне помочь? Вот полные классы:

УЗЕЛ:

public class Node {
    int value;
    Node[] connectedNodes = {null,null};
    Combination combination;

    public Node(int value) {
        this.value = value;
        this.combination = null;
    }
}

ДЕРЕВО:

public class Tree {
    Node root;

    public Tree(Node root) {
        this.root = root;
    }

    public void addCombination(Combination finalCombination, Node current, String combination, int counter) {

        if(counter==combination.length()) {
            return;
        }

    int value = combination.charAt(counter)-48;
    if(current.connectedNodes[value-1]==null) {
        current.connectedNodes[value-1] = new Node(value);
    }
    if(counter==combination.length()-1) {
        current.combination = finalCombination;
        return;
    }
    addCombination(finalCombination,current.connectedNodes[value-1],combination,counter+1);

}

public void traverse(Node current) {
    System.out.print(current.value+ " ");
    for(Node node: current.connectedNodes) {
        if(node!=null) {
            traverse(node);
        }
    }
}

public Node takeStep(Node current, int value) {
    if(current.connectedNodes[value-1]!=null) {
        return current.connectedNodes[value-1];
    }
    return this.root;
}}

КОМБИНАЦИЯ :

public class Combination {
     String messageContext;
}

Не могли бы вы мне помочь? Я просто хочу сбросить на root, когда еще нет места на go? Заранее спасибо!

Answer 1

Я запустил ваш код и обнаружил, что вы сохраняете контекст сообщения в родительском узле вместо фактического узла, который отмечает конец комбинации. Таким образом, я изменил этот кусок кода в addCombination .

    public void addCombination(Combination finalCombination, Node current, String combination, int counter) {

    if (counter == combination.length()) {
        //Storing at the original node.
        current.combination = finalCombination;
        return;
    }

    int value = combination.charAt(counter) - 48;
    if (current.connectedNodes[value - 1] == null) {
        current.connectedNodes[value - 1] = new Node(value);
    }
    addCombination(finalCombination, current.connectedNodes[value - 1], combination, counter + 1);

}

И изменил следующее в основном коде.

 while (true) {
        System.out.println(currentNode.value);
        //Moved it up now as the node it self has the message context.
        if (currentNode.combination != null) {
            System.out.println(currentNode.combination.messageContext);
            if (currentNode.connectedNodes[0] == null && currentNode.connectedNodes[1] == null) {
                currentNode = tree.root;
                continue;
            }
        }
        for (Node node : currentNode.connectedNodes) {
            if (node != null) {
                System.out.print(node.value + " ");
            } else {
                System.out.print("nullnode ");
            }
        }
        int x = scanner.nextInt();
        currentNode = tree.takeStep(currentNode, x);
    }

Теперь попробуйте код, для которого он сбрасывается root как и ожидалось.