CODEWITHSUNDEEP
javarecursiontreeantlr
djcmm476
djcmm476

Reputation: 1813

Traversing a tree recursively in depth first problems

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

Upvotes: 1

Views: 37293

Answers (3)

darijan
darijan

Reputation: 9775

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

Upvotes: 0

David Moles
David Moles

Reputation: 51093

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

Upvotes: 5

Thomas
Thomas

Reputation: 5094

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.

Upvotes: 2

Related Questions