thomas908
asked on
Tree Traversal
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).jjtGet Child(0) will give me "a"
root.jjtGetChild(0).jjtGet Child(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.jjtGetNumChildr en();
if (liChildCount == 0) {
aoInfix.append(asCurrentNo de);
if (closeBraces)
aoInfix.append(")");
} else if (liChildCount == 1) {
aoInfix.append(" ");
aoInfix.append(asCurrentNo de);
aoInfix.append("(");
traverse(aoTreeNode.jjtGet Child(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.jjtGet Child(liCh ildCntr), aoInfix,
(liChildCntr >= 1 && liChildCount >= 2) ? true : false);
if (liChildCntr < liChildCount - 1) {
aoInfix.append(" ");
aoInfix.append(asCurrentNo de);
aoInfix.append(" ");
}
}
}
Logger.getInstance().write Log("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
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).jjtGet
root.jjtGetChild(0).jjtGet
I have written a small program for this
private StringBuffer traverse(Node aoTreeNode, StringBuffer aoInfix,
boolean closeBraces) {
String asCurrentNode = aoTreeNode.toString();
int liChildCount = aoTreeNode.jjtGetNumChildr
if (liChildCount == 0) {
aoInfix.append(asCurrentNo
if (closeBraces)
aoInfix.append(")");
} else if (liChildCount == 1) {
aoInfix.append(" ");
aoInfix.append(asCurrentNo
aoInfix.append("(");
traverse(aoTreeNode.jjtGet
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.jjtGet
(liChildCntr >= 1 && liChildCount >= 2) ? true : false);
if (liChildCntr < liChildCount - 1) {
aoInfix.append(" ");
aoInfix.append(asCurrentNo
aoInfix.append(" ");
}
}
}
Logger.getInstance().write
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
see this link http://forum.java.sun.com/thread.jspa?threadID=541976&messageID=2628883
hope this helps
Regards,
Venkat.
hope this helps
Regards,
Venkat.
Check this link too...
http://www.devhardware.com/forums/programming-82/level-order-tree-traversal-java-66605.html
http://www.devhardware.com/forums/programming-82/level-order-tree-traversal-java-66605.html
ASKER
I am sorry to not have replied earlier. Please give me acouple of days to update this.
thanks
thanks
ASKER
>> 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
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
how exactly would what i suggested not work?
and how could it generate non-matching braces, everywhere a ( is added a ) is also added.
and how could it generate non-matching braces, everywhere a ( is added a ) is also added.
ASKER
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>)
>> 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)(
so have u implemented the code I posted above?
where is that output coming from?
where is that output coming from?
ASKER
>> 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
>>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)(
It is coming from the code you have posted.
Thank You
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
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
"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
to do that you'd need to check if the child nodes had leaves or not.
ASKER
Something like this...
StringBuffer traverse(Node aoTreeNode) {
String asCurrentNode = aoTreeNode.toString();
int liChildCount = aoTreeNode.jjtGetNumChildr en();
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(aoTree Node.jjtGe tChild(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(aoTree Node.jjtGe tChild(liC hildCntr)) );
if(aoTreeNode.jjtGetChild( 0) != null) {
buf.append(")");
}
buf.append(" ");
if (liChildCntr<liChildCount- 1)
buf.append(asCurrentNode);
}
Logger.getInstance().write Log("Buffe r Value - "+buf);
return buf;
}
}
StringBuffer traverse(Node aoTreeNode) {
String asCurrentNode = aoTreeNode.toString();
int liChildCount = aoTreeNode.jjtGetNumChildr
if (liChildCount == 0) {
return new StringBuffer(asCurrentNode
} else if (liChildCount == 1) {
StringBuffer buf = new StringBuffer();
buf.append(asCurrentNode);
buf.append(" ");
if(aoTreeNode.jjtGetChild(
buf.append("(");
}
buf.append(traverse(aoTree
if(aoTreeNode.jjtGetChild(
buf.append(")");
}
buf.append(" ");
return buf;
} else {
StringBuffer buf = new StringBuffer();
for (int liChildCntr = 0; liChildCntr < liChildCount; liChildCntr++) {
buf.append(" ");
if(aoTreeNode.jjtGetChild(
buf.append("(");
}
buf.append(traverse(aoTree
if(aoTreeNode.jjtGetChild(
buf.append(")");
}
buf.append(" ");
if (liChildCntr<liChildCount-
buf.append(asCurrentNode);
}
Logger.getInstance().write
return buf;
}
}
ASKER
The code I posted above doesn't work, can you please tell me where should I make the changes.
Thank You
Thank You
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;
StringBuffer buf = new StringBuffer();
buf.append(asCurrentNode);
buf.append(" ");
Node child = aoTreeNode.jjtGetChild(0);
if(child.jjtGetNumChildren
buf.append("(");
}
buf.append(traverse(child)
if(child.jjtGetNumChildren
buf.append(")");
}
buf.append(" ");
return buf;
ASKER
thanks for replying
Still same result
StringBuffer traverse(Node aoTreeNode) {
String asCurrentNode = aoTreeNode.toString();
int liChildCount = aoTreeNode.jjtGetNumChildr en();
if (liChildCount == 0) {
return new StringBuffer(asCurrentNode );
} else if (liChildCount == 1) {
StringBuffer buf = new StringBuffer();
buf.append(asCurrentNode);
buf.append(" ");
if(aoTreeNode.jjtGetNumChi ldren()>0) {
buf.append("(");
}
buf.append(traverse(aoTree Node.jjtGe tChild(0)) );
if(aoTreeNode.jjtGetNumChi ldren()>0) {
buf.append(")");
}
buf.append(" ");
return buf;
} else {
StringBuffer buf = new StringBuffer();
for (int liChildCntr = 0; liChildCntr < liChildCount; liChildCntr++) {
buf.append(" ");
if(aoTreeNode.jjtGetNumChi ldren()>0) {
buf.append("(");
}
buf.append(traverse(aoTree Node.jjtGe tChild(liC hildCntr)) );
if(aoTreeNode.jjtGetNumChi ldren()>0) {
buf.append(")");
}
buf.append(" ");
if (liChildCntr<liChildCount- 1)
buf.append(asCurrentNode);
}
Logger.getInstance().write Log("Buffe r Value - "+buf);
return buf;
}
}
Still same result
StringBuffer traverse(Node aoTreeNode) {
String asCurrentNode = aoTreeNode.toString();
int liChildCount = aoTreeNode.jjtGetNumChildr
if (liChildCount == 0) {
return new StringBuffer(asCurrentNode
} else if (liChildCount == 1) {
StringBuffer buf = new StringBuffer();
buf.append(asCurrentNode);
buf.append(" ");
if(aoTreeNode.jjtGetNumChi
buf.append("(");
}
buf.append(traverse(aoTree
if(aoTreeNode.jjtGetNumChi
buf.append(")");
}
buf.append(" ");
return buf;
} else {
StringBuffer buf = new StringBuffer();
for (int liChildCntr = 0; liChildCntr < liChildCount; liChildCntr++) {
buf.append(" ");
if(aoTreeNode.jjtGetNumChi
buf.append("(");
}
buf.append(traverse(aoTree
if(aoTreeNode.jjtGetNumChi
buf.append(")");
}
buf.append(" ");
if (liChildCntr<liChildCount-
buf.append(asCurrentNode);
}
Logger.getInstance().write
return buf;
}
}
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.
ie. if its a leaf then no braces, o'wise add braces.
ASKER
Thank You so much, objects. You are simply incredible.
ASKER
Here is the updated code
StringBuffer traverse(Node aoTreeNode) {
String asCurrentNode = aoTreeNode.toString();
int liChildCount = aoTreeNode.jjtGetNumChildr en();
if (liChildCount == 0) {
return new StringBuffer(asCurrentNode );
} else if (liChildCount == 1) {
StringBuffer buf = new StringBuffer();
buf.append(asCurrentNode);
buf.append(" ");
if(aoTreeNode.jjtGetChild( 0).jjtGetN umChildren ()>0) {
buf.append("(");
}
buf.append(traverse(aoTree Node.jjtGe tChild(0)) );
if(aoTreeNode.jjtGetChild( 0).jjtGetN umChildren ()>0) {
buf.append(")");
}
buf.append(" ");
return buf;
} else {
StringBuffer buf = new StringBuffer();
for (int liChildCntr = 0; liChildCntr < liChildCount; liChildCntr++) {
buf.append(" ");
if(aoTreeNode.jjtGetChild( liChildCnt r).jjtGetN umChildren ()>0) {
buf.append("(");
}
buf.append(traverse(aoTree Node.jjtGe tChild(liC hildCntr)) );
if(aoTreeNode.jjtGetChild( liChildCnt r).jjtGetN umChildren ()>0) {
buf.append(")");
}
buf.append(" ");
if (liChildCntr<liChildCount- 1)
buf.append(asCurrentNode);
}
Logger.getInstance().write Log("Buffe r Value - "+buf);
return buf;
}
}
StringBuffer traverse(Node aoTreeNode) {
String asCurrentNode = aoTreeNode.toString();
int liChildCount = aoTreeNode.jjtGetNumChildr
if (liChildCount == 0) {
return new StringBuffer(asCurrentNode
} else if (liChildCount == 1) {
StringBuffer buf = new StringBuffer();
buf.append(asCurrentNode);
buf.append(" ");
if(aoTreeNode.jjtGetChild(
buf.append("(");
}
buf.append(traverse(aoTree
if(aoTreeNode.jjtGetChild(
buf.append(")");
}
buf.append(" ");
return buf;
} else {
StringBuffer buf = new StringBuffer();
for (int liChildCntr = 0; liChildCntr < liChildCount; liChildCntr++) {
buf.append(" ");
if(aoTreeNode.jjtGetChild(
buf.append("(");
}
buf.append(traverse(aoTree
if(aoTreeNode.jjtGetChild(
buf.append(")");
}
buf.append(" ");
if (liChildCntr<liChildCount-
buf.append(asCurrentNode);
}
Logger.getInstance().write
return buf;
}
}
StringBuffer traverse(Node aoTreeNode) {
String asCurrentNode = aoTreeNode.toString();
int liChildCount = aoTreeNode.jjtGetNumChildr
if (liChildCount == 0) {
return new StringBuffer(asCurrentNode
} else if (liChildCount == 1) {
StringBuffer buf = new StringBuffer();
buf.append(asCurrentNode);
buf.append("(");
buf.append(traverse(aoTree
buf.append(")");
return buf;
} else {
StringBuffer buf = new StringBuffer();
for (int liChildCntr = 0; liChildCntr < liChildCount; liChildCntr++) {
buf.append("(");
buf.append(traverse(aoTree
if (liChildCntr<liChildCount-
buf.append(")");
}
return buf;
}
}