PostOder Iterator in a Binary Search Tree
Hi!
i am programming iterator's for a binary search tree, that for performance must use a stack.
i have managed to make the class for PrefixIterator, but i am not getting to PostOrderIterator....
Anyone knows how to make it ?
I leave the code for de PrefixOrder that works, in case anyone needs it.
best regars,
cokkas
///////////////////// PrefixIterator //////////////////////
private class PrefixIterator implements Iterator{
private GenericStackArray<Node> stack = new GenericStackArray<Node>(10);
PrefixIterator()
{
Node x = root;
if (x != null) {
stack.push(x);
x = x.left;
}
}
public boolean hasNext() {
return !stack.isEmpty();
}
public Object next() {
if (!hasNext())
{
System.out.println("n existem mais elementos!");
return null;
}
Node node = stack.pop ();
if (node.right != null)
stack.push (node.right);
if (node.left != null)
stack.push (node.left);
return node.item;
}
public void remove() {
// TODO Auto-generated method stub
}
}
///////////////////// Fim PrefixIterator //////////////////////
[1280 byte] By [
cokkasa] at [2007-11-27 9:13:51]
This is a brazilian university teacher web site. http://www.ime.usp.br/~pf/Here u ll find everything related to graphs, math, and basic structures such as treesBoa sorte!!!
didnt help....thanks anywayanyone knows how to do it ?
> didnt help....thanks anyway> > anyone knows how to do it ?Pseudo code and examples of the traversals can be found here: http://en.wikipedia.org/wiki/Tree_traversal
this is different, because it is no a simple tree trasversal, ... the purpose is to make a Iterator, that uses PostOrder, and because of that it must use a stack...
it must be something like the code i have made and posted above in the post, but i am not getting there... :S
Anyone actually knows or as already made de code ?
So is there a PostOdor code smell?
> this is different, because it is no a simple tree
> trasversal, ... the purpose is to make a Iterator,
> that uses PostOrder, and because of that it must use
> a stack...
>
> it must be something like the code i have made and
> posted above in the post, but i am not getting
> there... :S
>
> Anyone actually knows or as already made de code ?
Here's a push in the right direction:
import java.util.Iterator;
import java.util.Stack;
public class PostOrderIterator implements Iterator {
private Stack stack;
public PostOrderIterator(Node root) {
'stack' <- new stack
'finger' <- 'root'
WHILE 'finger' does not equal null
push 'finger' on 'stack'
IF left node of 'finger' does not equal null
'finger' <- left node of 'finger'
ELSE
'finger' <- right node of 'finger'
END IF
END WHILE
}
public boolean hasNext() {
return !stack.isEmpty();
}
public Object next() {
'current' <- pop a node from 'stack'
'returnValue' <- 'current'
IF 'stack' is not empty
'finger' <- peek from 'stack'
IF 'current' equals the left node of 'finger'
WHILE 'current' does not equal null
push 'current' on 'stack'
IF the left node of 'current' equals null
'current' <- the left node of 'current'
ELSE
'current' <- the right node of 'current'
END IF
END WHILE
END IF
END IF
return 'returnValue'
}
public void remove() throws UnsupportedOperationException {
throw new UnsupportedOperationException();
}
}
Try to finish it.
hey.thanks, it must be something like that, bue i cant get it to work well, did you managed ta make it work ;)thanks
> hey.
>
> thanks, it must be something like that
It is like that for sure.
; )
> , bue i cant get it to work well,
That's a shame.
If only you posted some code or a specific question I could help you with...
> did you managed ta make it work ;)
Yes, I did.
>> , bue i cant get it to work well,>That's a shame.>If only you posted some code or a specific question I could help you with...Maybe if you posted a complete Java solution, Corkie could compare it to, ahem, his code.
> Maybe if you posted a complete Java solution, Corkie> could compare it to, ahem, his code.I predict Corkie's code would be a good bit shorter. ;)
and it's for his datastructure homework...=.=
> prometheuzz
what i cant understand is how to make the next() method...
this is the code i made so far:
private class PostfixIterator implements Iterator{
private GenericStackArray<Node> stack = new GenericStackArray<Node>(10);
Node x=null;
PostfixIterator() {
Node x = root;
while (x != null) {
stack.push(x);
x = x.left;
}
}
public boolean hasNext() {
return !stack.isEmpty();
}
public Object next() {
if (!hasNext())
{
System.out.println("n more elements!");
return null;
}
...
}
public void remove() {
// TODO Auto-generated method stub
}
}
can you (or anyone) explain to me how to make the next() using a stack on a binary search tree ?
Next time when posting code, please use code tags:
http://forum.java.sun.com/help.jspa?sec=formatting
> what i cant understand is how to make the next()
> method...
>
> this is the code i made so far:
And it's wrong: the constructor is not pushing the correct initial Nodes on the stack. What if your binary Tree looks like this:
A
\
B
/ \
CD
According to your logic, the traversal would start with A, which is incorrect. You did not study the constructor from the pseudo code I posted well enough.
And what is the Node x=null; good for inside your class? You only need the stack as a class variable.
> can you (or anyone) explain to me how to make the
> next() using a stack on a binary search tree ?
I already did! I still have not seen a decent attempt to implement the pseudo code I posted, which practically is a dead give-away!
>And it's wrong: the constructor is not pushing the correct initial Nodes on the stack. What if your binary Tree looks like this...
i agree. i have changed to the pseudo code that you provided, and that i post above:
private class PostfixIterator implements Iterator{
private GenericStackArray<Node> stack = new GenericStackArray<Node>(10);
Node x=null;
PostfixIterator() {
while(root!=null)
{
stack.push(root);
if(root.left!=null)
root=root.left;
else
root=root.right;
}
}
public boolean hasNext() {
return !stack.isEmpty();
}
public Object next() {
Node current=stack.pop();
Item it = current.item;
if(!stack.isEmpty())
{
Node finger=stack.peek();
if(current.item.equals(finger.item))
{
while(current==null)
{
stack.push(current);
if(current.left==null)
current=current.left;
else
current=current.right;
}
}
}
return it;
}
public void remove() {
// TODO Auto-generated method stub
}
}
but it dos not work, it enters in a loop.
The Item that i am using is an Integer.
i am not understanding you while cicle:
while(current==null)
{
stack.push(current);
if(current.left==null)
current=current.left;
else
current=current.right;
}
why do you want to push up current ? does that not enters in a loop ?
other question , if the left is already null, why do you try to proceed further to left ? (the same with the right).
if you can help, show me your code that works, because this one does not work.
thanks for all your help.
best regards,
cokkas
From my previous reply:Next time when posting code, please use code tags: http://forum.java.sun.com/help.jspa?sec=formattingand:And what is the Node x=null; good for inside your class? You only need the stack as a class variable.
> PostfixIterator() {
> while(root!=null)
> {
> stack.push(root);
> if(root.left!=null)
>root=root.left;
> else
>root=root.right;
> }
> }
Watch it there! You don't want to go changing the root of the tree!
public PostOrderIterator() {
// Let 'finger' point to 'root' and then work with that finger reference
// that way you leave the actual root of the tree in tact
Node finger = root;
while(finger != null) {
// your code
}
}
> Watch it there! You don't want to go changing the root of the tree!
ok, it is a good advice, i have changed to your sugestion.
> the Node x= null, was from a previous implementation i have tried, so it wasnt making nothing over there, i have deleted it.
From my previous reply:
i am not understanding you while cicle:
while(current==null)
{
stack.push(current);
if(current.left==null)
current=current.left;
else
current=current.right;
}
why do you want to push up current ? does that not enters in a loop ?
other question , if the left is already null, why do you try to proceed further to left ? (the same with the right).
Now, i run the program and it only shows me the root of mi tree, 3 trimes in a row.
Sorry i didnt put identation in my post, i am new at this forum.
can you show me your working code ?
best regards,
cokkas
