1

I'm trying to traverse a tree using ANTLR tree commands and recursion. The code I currently have is:

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

        }
    }

But, well, it's not working. I'm getting a lot of the entries in the tree, but in no obvious order. Can anyone see where I'm going wrong?

Thanks.

EDIT:

Comment I made below that should have been here to begin with:

Sorry, I should have removed the print statements, they were just there to try and debug it. The problem I'm encountering is that it should only search the node it starts on and any siblings of that node, it shouldn't go up a level, but it does, it prints everything. (I'll edit this into the main, it should have been there to begin with, sorry).

I managed to get the code working eventually like so:

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));
        }
    }
djcmm476
  • 1,723
  • 6
  • 24
  • 46
  • "In depth first"... do you mean level order? Reverse level order? I'm confused.. Other possibilities are preorder, inorder, postorder – varatis Mar 15 '12 at 17:02

3 Answers3

5

The easiest way to ensure it never goes up a level is to ensure you never call getParent(). If you have no idea there's an upper level, you can't go there.

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

The whole point of recursion is that you don't need to go back up. When traverseTree() at this level finishes, the loop in the previous level will continue on to the next sibling.

(Note that the if isn't actually necessary, unless you want to do something special when you reach a leaf node. I just put it there so the comment would make it obvious what's going on. Conceptually, it's always a good idea in recursion to start by figuring out how you know when to stop recursing.)

David Moles
  • 48,006
  • 27
  • 136
  • 235
  • But that's the thing, I never use getParent() except when I'm doing getParent.getChild(getChildIndex() + 1) which is just to move it to the next sibling (there doesn't seem to be another way to do this). – djcmm476 Mar 15 '12 at 17:49
  • You don't need to move to the next sibling. The loop at the parent's level takes care of that. – David Moles Mar 15 '12 at 17:53
  • (Of course, you actually have to have a loop. I imagine it's possible to do it without a loop, but I don't know why you'd want to.) – David Moles Mar 15 '12 at 17:55
  • Okay, on closer examination I see what's going on. You're looping over your siblings instead of looping over your children. Since you have to go up to the parent to get your siblings, there's no way (without extra information) to stop the traversal from crawling all the way up to the root of the tree. – David Moles Mar 15 '12 at 17:59
  • I'm going to mark your answer as right, as you helped me with a couple of bugs. The thing that was causing the real trouble was actually a little bit earlier in the code. I'll post up the working code in case anyone runs into a similar problem. Thanks! – djcmm476 Mar 15 '12 at 18:13
  • No problem! Still think you want to be traversing children rather than siblings, though. :) – David Moles Mar 15 '12 at 18:25
2

It looks like you're printing out the same nodes several times. If you just want to print out the nodes as you go down, 

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

To switch to 4 5 6 2 3 1, just move the println to after the for loop.

Thomas
  • 5,074
  • 1
  • 16
  • 12
  • Sorry, I should have removed the print statements, they were just there to try and debug it. The problem I'm encountering is that it should only search the node it starts on and any siblings of that node, it shouldn't go up a level, but it does, it prints everything. (I'll edit this into the main, it should have been there to begin with, sorry). – djcmm476 Mar 15 '12 at 17:28
  • @Incredidave Thomas' solution (almost) works at whatever node you give it (it should have null exit statements). If you want to start at a child, just pass it that instead of the root. You really need to be more specific about how you're trying to visit each node, what you intend to do there, and in what order. – varatis Mar 15 '12 at 18:04
  • I was assuming the children were non-null, so it would terminate due to getChildCount() being 0. In any case, it doesn't answer the actual question. – Thomas Mar 15 '12 at 21:00
0

Try this:

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);
    }
}
David Kroukamp
  • 36,155
  • 13
  • 81
  • 138
darijan
  • 9,725
  • 25
  • 38