Первые проблемы рекурсивного обхода дерева

Я пытаюсь пройти по дереву с помощью команд дерева ANTLR и рекурсии. Код, который у меня сейчас есть:

public void traverseTree(Tree tree){
        int counter = 0;
        System.out.println(tree.toString());
        if (tree.getChildCount() > 0 && tree.getChild(0) != null){
            System.out.println(tree.toString() + counter++);
            tree = tree.getChild(0);
            traverseTree(tree);

        }
        while (tree.getParent().getChild(tree.getChildIndex() + 1) != null){
            System.out.println(tree.toString() + counter++);
            tree = tree.getParent().getChild(tree.getChildIndex() + 1);
            traverseTree(tree);

        }
    }

Но, ну, это не работает. Я получаю много записей в дереве, но не в явном порядке. Кто-нибудь может увидеть, где я иду не так?

Благодарю.

РЕДАКТИРОВАТЬ:

Комментарий, который я сделал ниже, должен был быть здесь для начала:

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

Мне удалось заставить код работать в итоге так:

public void traverseTree(Tree tree){
        System.out.println(tree);
        if (tree.getChild(0) != null){
            traverseTree(tree.getChild(0));
        }
        if(tree.getParent().getChildCount() > 1){
            if(tree.getParent().getChild(tree.getChildIndex() + 1) != null)
            traverseTree(tree.getParent().getChild(tree.getChildIndex() + 1));
        }
    }
Источник

3 ответа

Решение

Самый простой способ убедиться, что он никогда не поднимется на новый уровень, это убедиться, что вы никогда не звоните getParent(), Если вы не знаете, что есть верхний уровень, вы не можете туда попасть.

public void traverseTree(Tree tree) {

    // print, increment counter, whatever
    System.out.println(tree.toString());

    // traverse children
    int childCount = tree.getChildCount();
    if (childCount == 0) {
        // leaf node, we're done
    } else {
        for (int i = 0; i < childCount; i++) {
            Tree child = tree.getChild(i);
            traverseTree(child);
        }
    }
}

Весь смысл рекурсии в том, что вам не нужно возвращаться назад. когда traverseTree() на этом уровне заканчивается цикл предыдущего уровня, переходящий к следующему брату.

(Обратите внимание, что if на самом деле не требуется, если вы не хотите делать что-то особенное, когда достигнете конечного узла. Я просто поместил это там, чтобы комментарий прояснил, что происходит. Концептуально всегда полезно начинать с рекурсии, выясняя, как вы знаете, когда прекратить рекурсию.)

Источник

Похоже, вы печатаете одни и те же узлы несколько раз. Если вы просто хотите распечатать узлы, как вы идете вниз,

   1
 2   3
4 5   6

Depth first - 1 2 4 5 3 6
Breadth first - 1 2 3 4 5 6

//For depth first
public void traverseTree(Tree tree){        
    System.out.println(tree.toString());
    for (int x = 0; x < tree.getChildCount(); x++)
        traverseTree(tree.getChild(x));
}

Чтобы переключиться на 4 5 6 2 3 1, просто переместите println в после цикла for.

Источник

Попробуй это:

int counter = 0;
public void traverseTree(Tree tree) {

    for (int i=0; i<tree.getChildCount(); i++) {
        Tree child = tree.getChild(i);
        System.out.println(tree.toString() + counter++);
        traverseTree(tree);
    }
}
Источник
Другие вопросы по тегам