Первые проблемы рекурсивного обхода дерева - PullRequest
Новая
       12

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

1 голос
/ 15 марта 2012

Я пытаюсь пройти по дереву, используя команды дерева 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);

        }
    }

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

Спасибо.

EDIT:

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

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

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

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 ]

5 голосов
/ 15 марта 2012

Самый простой способ убедиться, что он никогда не поднимется на новый уровень, это убедиться, что вы никогда не звоните 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 на самом деле не является необходимым, если вы не хотите делать что-то особенное, когда достигнете конечного узла. Я просто поместил это там, чтобы комментарий прояснил, что происходит. Хорошая идея рекурсии - начать с выяснения того, как вы знаете, когда прекратить рекурсию.)

2 голосов
/ 15 марта 2012

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

   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.

0 голосов
/ 15 марта 2012

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

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