Solved

Tree Traversal

Posted on 2006-06-12
20
349 Views
Last Modified: 2008-03-10
I have a k-ary tree in the form of

           or
         /    \
       and     i
      /   \
     a     e
 
 

where "or" and "and" are operators. i need to traverse the tree and display the values in infix notation. Example


(a and e) or i

If "or" is the root node then as per the API I am using
root.jjtGetChild(0) will give me "and"
root.jjtGetChild(1) will give me "i"
root.jjtGetChild(0).jjtGetChild(0) will give me "a"
root.jjtGetChild(0).jjtGetChild(1) will give me "e"

I have written a small program for this


 private StringBuffer traverse(Node aoTreeNode, StringBuffer aoInfix,
            boolean closeBraces) {
        String asCurrentNode = aoTreeNode.toString();
       
        int liChildCount = aoTreeNode.jjtGetNumChildren();
        if (liChildCount == 0) {
            aoInfix.append(asCurrentNode);
            if (closeBraces)
                aoInfix.append(")");
        } else if (liChildCount == 1) {
            aoInfix.append(" ");
            aoInfix.append(asCurrentNode);
            aoInfix.append("(");
            traverse(aoTreeNode.jjtGetChild(0), aoInfix, false);
            aoInfix.append(")");
            if (closeBraces)
                aoInfix.append(")");
        } else {
            for (int liBraceCntr = 0; liBraceCntr < liChildCount - 1; liBraceCntr++) {
                aoInfix.append("(");
            }
            for (int liChildCntr = 0; liChildCntr < liChildCount; liChildCntr++) {
                traverse(aoTreeNode.jjtGetChild(liChildCntr), aoInfix,
                        (liChildCntr >= 1 && liChildCount >= 2) ? true : false);
                if (liChildCntr < liChildCount - 1) {
                    aoInfix.append(" ");
                    aoInfix.append(asCurrentNode);
                    aoInfix.append(" ");
                }
            }
        }
        Logger.getInstance().writeLog("Infix Query in traverse() method - "+aoInfix);
        return aoInfix;
    }
The program works fine for the above scenario.
But if I change it to
 
           
           and
          /    \
         a      or
               /  \
              b    c
It gets messed up with unbalanced braces. I am unable to figure out the problem, please help me.
also its a k-ary tree and can be n levels deep.
Its very important to keep the braces. For instance I can't do something like "a and b or c".

Thanks
0
Comment
Question by:thomas908
  • 10
  • 7
  • 2
20 Comments
 
LVL 92

Expert Comment

by:objects
ID: 16891697
I'd be coding it more like this:

StringBuffer traverse(Node aoTreeNode)  {

       String asCurrentNode = aoTreeNode.toString();
       int liChildCount = aoTreeNode.jjtGetNumChildren();
        if (liChildCount == 0) {

            return new StringBuffer(asCurrentNode);

        } else if (liChildCount == 1) {

            StringBuffer buf = new StringBuffer();
            buf.append(asCurrentNode);
            buf.append("(");
            buf.append(traverse(aoTreeNode.jjtGetChild(0)));
            buf.append(")");
            return buf;

        } else {
           
            StringBuffer buf = new StringBuffer();
            for (int liChildCntr = 0; liChildCntr < liChildCount; liChildCntr++) {
               buf.append("(");
               buf.append(traverse(aoTreeNode.jjtGetChild(liChildCntr)));
               if (liChildCntr<liChildCount-1) buf.append(asCurrentNode);
               buf.append(")");
            }
            return buf;
       }
}
0
 

Expert Comment

by:vpaturu
ID: 16891768
see this link http://forum.java.sun.com/thread.jspa?threadID=541976&messageID=2628883

hope this helps

Regards,
Venkat.
0
 

Expert Comment

by:vpaturu
ID: 16891773
0
 
LVL 8

Author Comment

by:thomas908
ID: 17072050
I am sorry to not have replied earlier. Please give me acouple of days to update this.

thanks
0
 
LVL 8

Author Comment

by:thomas908
ID: 17079133
>> I'd be coding it more like this:
Sorry objects, tt does not work even the scenario I have postd above. Braces get all messed up
Also there can be urinary operators like NOT, so I have to take care of braces for them also.
Say the user entered

(a and e) or not i

It'll be stored in the database as

 OR (  AND ( 'a', 'e' ) ,  NOT ( 'i' )  )

corrsponding tree will be something like

               OR
               /   \
            AND  NOT
             / \     \
           a   e    i

i need the traverse the tree in infix notation  and get back what the user entered, that is,  "(a and e) or not i"
Braces should be matching. Gettng some extra pais of braces is not a problem, such as getting
"(a and e) or not (i)" or "((a and e) or not (i))" is OK but getting "(a and e) or not i)" is not (as braces are not matching).
Also, "a and e or not i" (user is not allowed to enter this, so braces need to be shown) won't work, precendence needs to be  defined using braces, so it has to be "(a and e) or not i".  
Thank You all for your patience
0
 
LVL 92

Expert Comment

by:objects
ID: 17080101
how exactly would what i suggested not work?
and how could it generate non-matching braces, everywhere a ( is added a ) is also added.
0
 
LVL 8

Author Comment

by:thomas908
ID: 17080937
Thanks for replying

>> how exactly would what i suggested not work?

Say the user entered, "(a and e) or i"
It would be converted to "OR (  AND ( 'a', 'e' ) , 'i' )"
Now we need to get it back to the infix notaion (by traversing the tree)
Your program is giving the follwoing result

((Word<a>And)(Word<e>)Or)(Word<i>)
0
 
LVL 92

Expert Comment

by:objects
ID: 17086858
so have u implemented the code I posted above?
where is that output coming from?
0
 
LVL 8

Author Comment

by:thomas908
ID: 17087832
>> so have u implemented the code I posted above?
>>where is that output coming from?

Yes, I have implemented your code. The output is the one posted above

((Word<a>And)(Word<e>)Or)(Word<i>)

It is coming from the code you have posted.

Thank You
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 92

Accepted Solution

by:
objects earned 500 total points
ID: 17087893
well it wasn't tested (nor could be) :)
For a start it looks like the toString() method for a node does not return what you need, so you'll need to call whatever method does.

looks like i put the closing brace in the wrong spot in the >1 child case

            StringBuffer buf = new StringBuffer();
            for (int liChildCntr = 0; liChildCntr < liChildCount; liChildCntr++) {
               buf.append("(");
               buf.append(traverse(aoTreeNode.jjtGetChild(liChildCntr)));
               buf.append(")");
               if (liChildCntr<liChildCount-1) buf.append(asCurrentNode);
            }
0
 
LVL 8

Author Comment

by:thomas908
ID: 17089280
Thanks you so much, objects. It works great.

"a and (b or cde)" entered by the user, and converted to a tree, is converted back to
 ( (a) And ( (b) Or (cde) ) )

Is it possible to make it
( a And ( b Or cde ) )   // removing the braces around the input

If it can be done then it'll be excellent. But even if it cannot be done, I think I can write a regular expression to strip the additional braces around the words(immediately preceding and following).

Thank You
 
0
 
LVL 92

Expert Comment

by:objects
ID: 17095682
to do that you'd need to check if the child nodes had leaves or not.
0
 
LVL 8

Author Comment

by:thomas908
ID: 17096782
Something like this...
StringBuffer traverse(Node aoTreeNode)  {

        String asCurrentNode = aoTreeNode.toString();
        int liChildCount = aoTreeNode.jjtGetNumChildren();
        if (liChildCount == 0) {
             return new StringBuffer(asCurrentNode);
         } else if (liChildCount == 1) {
             StringBuffer buf = new StringBuffer();
             buf.append(asCurrentNode);
             buf.append(" ");
             if(aoTreeNode.jjtGetChild(0) != null) {
                  buf.append("(");
             }
             buf.append(traverse(aoTreeNode.jjtGetChild(0)));
             if(aoTreeNode.jjtGetChild(0) != null) {
                 buf.append(")");
             }
             buf.append(" ");
             return buf;
         } else {        
             StringBuffer buf = new StringBuffer();
             for (int liChildCntr = 0; liChildCntr < liChildCount; liChildCntr++) {
                buf.append(" ");
                if(aoTreeNode.jjtGetChild(0) != null) {
                    buf.append("(");
                }
                buf.append(traverse(aoTreeNode.jjtGetChild(liChildCntr)));
                if(aoTreeNode.jjtGetChild(0) != null) {
                    buf.append(")");
                }
                buf.append(" ");
                if (liChildCntr<liChildCount-1)
                    buf.append(asCurrentNode);
             }
             
             
             Logger.getInstance().writeLog("Buffer Value - "+buf);
             return buf;
        }
 }

0
 
LVL 8

Author Comment

by:thomas908
ID: 17097615
The code I posted above doesn't work, can you please tell me where should I make the changes.
Thank You
0
 
LVL 92

Expert Comment

by:objects
ID: 17097686
u need to be checking the number of children of the node you are adding , something like:

             StringBuffer buf = new StringBuffer();
             buf.append(asCurrentNode);
             buf.append(" ");
             Node child = aoTreeNode.jjtGetChild(0);
             if(child.jjtGetNumChildren()>0) {
                  buf.append("(");
             }
             buf.append(traverse(child));
             if(child.jjtGetNumChildren()>0) {
                 buf.append(")");
             }
             buf.append(" ");
             return buf;
0
 
LVL 8

Author Comment

by:thomas908
ID: 17097785
thanks for replying
Still same result

 StringBuffer traverse(Node aoTreeNode)  {

        String asCurrentNode = aoTreeNode.toString();
        int liChildCount = aoTreeNode.jjtGetNumChildren();
        if (liChildCount == 0) {
             return new StringBuffer(asCurrentNode);
         } else if (liChildCount == 1) {
             StringBuffer buf = new StringBuffer();
             buf.append(asCurrentNode);
             buf.append(" ");
             if(aoTreeNode.jjtGetNumChildren()>0) {
                 buf.append("(");
             }
   
             buf.append(traverse(aoTreeNode.jjtGetChild(0)));

             if(aoTreeNode.jjtGetNumChildren()>0) {
                  buf.append(")");
             }
             buf.append(" ");
             return buf;
         } else {        
             StringBuffer buf = new StringBuffer();
             for (int liChildCntr = 0; liChildCntr < liChildCount; liChildCntr++) {
                buf.append(" ");
                if(aoTreeNode.jjtGetNumChildren()>0) {
                    buf.append("(");
                }
                buf.append(traverse(aoTreeNode.jjtGetChild(liChildCntr)));
                if(aoTreeNode.jjtGetNumChildren()>0) {
                   buf.append(")");
                }
                buf.append(" ");
                if (liChildCntr<liChildCount-1)
                    buf.append(asCurrentNode);
             }
             
             
             Logger.getInstance().writeLog("Buffer Value - "+buf);
             return buf;
        }
 }
0
 
LVL 92

Expert Comment

by:objects
ID: 17097812
your checking the number of childeren on the wroong tree node, you need to check if the node thats potentially in the braces.
ie. if its a leaf then no braces, o'wise add braces.
0
 
LVL 8

Author Comment

by:thomas908
ID: 17097840
Thank You so much, objects. You are simply incredible.
0
 
LVL 8

Author Comment

by:thomas908
ID: 17097848
Here is the updated code

 StringBuffer traverse(Node aoTreeNode)  {

        String asCurrentNode = aoTreeNode.toString();
        int liChildCount = aoTreeNode.jjtGetNumChildren();
        if (liChildCount == 0) {
             return new StringBuffer(asCurrentNode);
         } else if (liChildCount == 1) {
             StringBuffer buf = new StringBuffer();
             buf.append(asCurrentNode);
             buf.append(" ");
             if(aoTreeNode.jjtGetChild(0).jjtGetNumChildren()>0) {
                 buf.append("(");
             }
   
             buf.append(traverse(aoTreeNode.jjtGetChild(0)));

             if(aoTreeNode.jjtGetChild(0).jjtGetNumChildren()>0) {
                  buf.append(")");
             }
             buf.append(" ");
             return buf;
         } else {        
             StringBuffer buf = new StringBuffer();
             for (int liChildCntr = 0; liChildCntr < liChildCount; liChildCntr++) {
                buf.append(" ");
                if(aoTreeNode.jjtGetChild(liChildCntr).jjtGetNumChildren()>0) {
                    buf.append("(");
                }
                buf.append(traverse(aoTreeNode.jjtGetChild(liChildCntr)));
                if(aoTreeNode.jjtGetChild(liChildCntr).jjtGetNumChildren()>0) {
                   buf.append(")");
                }
                buf.append(" ");
                if (liChildCntr<liChildCount-1)
                    buf.append(asCurrentNode);
             }
             
             
             Logger.getInstance().writeLog("Buffer Value - "+buf);
             return buf;
        }
 }
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
splitOdd10 challenge 5 74
allswap challenge 6 75
ArrayIndexOutOfBoundException 9 66
split string containing \r\n in Java 46 38
For beginner Java programmers or at least those new to the Eclipse IDE, the following tutorial will show some (four) ways in which you can import your Java projects to your Eclipse workbench. Introduction While learning Java can be done with…
Java functions are among the best things for programmers to work with as Java sites can be very easy to read and prepare. Java especially simplifies many processes in the coding industry as it helps integrate many forms of technology and different d…
Video by: Michael
Viewers learn about how to reduce the potential repetitiveness of coding in main by developing methods to perform specific tasks for their program. Additionally, objects are introduced for the purpose of learning how to call methods in Java. Define …
The viewer will learn how to implement Singleton Design Pattern in Java.

943 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

1 Experts available now in Live!

Get 1:1 Help Now