Page 1 of 1
Non-recursive binary tree traversal
Posted: 2004-01-27 09:54pm
by Pu-239
I'm doing trees in computer science, and I'm trying to figure out how to do traversals non-recursively. Here's my grossly messy code (in java). What obvious errors are there, and how could I make inorder more clean?
public Queue preOrder() {
TreeNode pointer = root;
Stack tr = new Stack();
Queue ret = new Queue();
boolean done = false;
//int counter = 0;
while (!done) {
if (pointer.getRight() != null) {
tr.push(pointer.getRight());
}
ret.enqueue(pointer.getValue());
//S.O.Pn((String)pointer.getValue()+ " " + counter);
//counter++;
if (pointer.getLeft() != null) {
pointer = pointer.getLeft();
} else if (tr.size() != 0) {
pointer = (TreeNode) tr.pop();
} else {
done = true;
}
}
return ret;
//return null;
}
public Queue inOrder() {
TreeNode pointer = root;
Stack tr = new Stack();
Queue ret = new Queue();
boolean done = false;
while (!done) {
if (pointer.getLeft() != null) {
tr.push(pointer);
pointer = pointer.getLeft();
} else if(pointer.getRight() != null){
ret.enqueue(pointer.getValue());
pointer = pointer.getRight();
} else if(tr.size() != 0){
ret.enqueue(pointer.getValue());
pointer = (TreeNode)tr.pop();
ret.enqueue(pointer.getValue());
if(pointer.getRight() != null){
pointer = pointer.getRight();
}else{
done = true;
}
}else if(tr.size() == 0 && pointer.getRight() == null && pointer.getLeft() == null){
S.O.Pn(((Integer)pointer.getValue()).intValue());
done = true;
}
}
return ret;
}
Posted: 2004-01-28 01:23am
by Crayz9000
Ah, binary trees... been there, done that. Lemme clean up your code first and then I'll look through it a bit.
Posted: 2004-01-28 11:44am
by phongn
If you're writing code, use the code tag and indent.
Posted: 2004-01-28 12:02pm
by Crayz9000
Well, here's the cleaned-up code.
Code: Select all
public Queue preOrder()
{
TreeNode pointer = root;
Stack tr = new Stack();
Queue ret = new Queue();
boolean done = false; //int counter = 0;
while (!done)
{
if (pointer.getRight() != null)
{
tr.push(pointer.getRight());
}
ret.enqueue(pointer.getValue());
//S.O.Pn((String)pointer.getValue()+ " " + counter);
//counter++;
if (pointer.getLeft() != null)
{
pointer = pointer.getLeft();
}
else if (tr.size() != 0)
{
pointer = (TreeNode)tr.pop();
}
else
{
done = true;
}
}
return ret;
//return null;
}
public Queue inOrder()
{
TreeNode pointer = root;
Stack tr = new Stack();
Queue ret = new Queue();
boolean done = false;
while (!done)
{
if(pointer.getLeft() != null)
{
tr.push(pointer);
pointer = pointer.getLeft();
}
else if(pointer.getRight() != null)
{
ret.enqueue(pointer.getValue());
pointer = pointer.getRight();
}
else if(tr.size() != 0)
{
ret.enqueue(pointer.getValue());
pointer = (TreeNode)tr.pop();
ret.enqueue(pointer.getValue());
if (pointer.getRight() != null)
{
pointer = pointer.getRight();
}
else
{
done = true;
}
}
else if(tr.size() == 0 && pointer.getRight() == null && pointer.getLeft() == null)
{
System.out.println(((Integer)pointer.getValue()).intValue());
done = true;
}
}
return ret;
}
I have a few things, though.
First, it doesn't pay to be lazy and write System.out.println() as S.O.Pn(). It can confuse the hell out of anyone looking at your code, and more importantly, Java won't have a clue what you're doing.
Secondly, you shouldn't have to do much typecasting if you know what sort of thing is getting returned. Did you write the TreeNode, Queue, and Stack classes? Or did your professor?
Posted: 2004-01-28 12:29pm
by Pu-239
The professor( teacher really, I'm in HS, gave the template, and we had to fill it in for Queue and Stack, and TreeNode was provided). I pulled it out straight from previous projects, and they were written for generic usage, hence the typecasting. We were actually supposed to do this w/ recursion which would be easy, but I wanted to see how it could be done w/o.
I made a wrapper for System.out.println with inner classes and such, so S.O.Pn() actually does work. People abbreviate like this when writing on overhead, so it's fairly obvious.
Clarification: I'm not concerned with the physical appearance of the code, but the size of inOrder, which is 50% more lines of code than preorder. I'm happy w/ preorder, but inorder just feels inefficient and buggy and more complicated than it has to be. Then there's postorder, which after spending many hours on inorder instead of required homework I'm not even going to bother trying to do nonrecursively.
Posted: 2004-01-28 12:48pm
by Crayz9000
Pu-239 wrote:We were actually supposed to do this w/ recursion which would be easy, but I wanted to see how it could be done w/o.
That's the usual excuse, but frankly, IMO it's often not worth it when you're in a class. Save the extra ideas for summer and winter breaks, when you don't have class committments to worry about.
As for the size of your code, the general rule is, if works, don't fix it. Fixing a perceived problem can often create more problems than it solves, although just cleaning up code is usually harmless.
I actually got into problems in my assembly language class last semester because I figured I'd do a bit more than I needed to on this one quiz/project. I inserted some code that I basically had memorized, but in doing so it did something to one of the registers and I never figured out what. Had to rewrite the whole damned thing because my apparently normal stack was anything but.
Uh, by the way, did you try flowcharting this? Getting a visualization of the problem generally helps when coding.
Posted: 2004-01-28 01:30pm
by Pu-239
Crayz9000 wrote:
Uh, by the way, did you try flowcharting this? Getting a visualization of the problem generally helps when coding.
Sort of, sketched a tree on paper and jumped around, and sort of visualized a flowchart in my head. Most painful part is the off by one errors when actually coding.
Posted: 2004-01-28 01:56pm
by phongn
You may want to write down your (flowcharted) algorithm in some detail before you go back and tackle the problem. Yeah, it takes time, and I hated doing that in HS as well, but it works.