-
January 25th, 2010, 08:20 AM
#1
Binary tree traversal using stack
I need a description of non-recursive algorithm using stack (inorder,preorder,postorder).
-
January 25th, 2010, 10:39 AM
#2
Re: Binary tree traversal using stack
Non-recursive algorithms are written with loops. Search Google for non recursive tree.
I know stacks. They can be simulated with areas. But I don't know "inorder, preorder, postorder", and I am not sure they are needed for stacks.
-
January 25th, 2010, 10:45 AM
#3
Re: Binary tree traversal using stack
its ok i figured it out myself
public void printPreOrder()
{stack s = new stack();
BinaryNodeWithSize cnode;
s.push ( root);
while ( !s.isEmpty())
{
cnode=s.topAndPop();
BinaryNodeWithSize right = cnode.getRight();
if (right !=null)
s.push(right);
BinaryNodeWithSize left =cnode.getLeft();
if (left!=null)
s.push(left);
System.out.println(cnode.getdata());
}
}
public void printPostOrder()
{
stack s=new stack();
BinaryNodeWithSize cnode;
s.push(root);
while (!s.isEmpty())
{ cnode=s.top();
if ((cnode.getLeft()!=null)&& (cnode.getLeft().visited==false))
{s.push(cnode.getLeft());}
else
{if ((cnode.getRight()!=null)&& (cnode.getRight().visited==false))
{s.push(cnode.getRight());}
else
{System.out.println(cnode.getdata());
cnode.visited=true;
s.pop();}}
}
}
public void printInOrder()
{
stack s=new stack();
BinaryNodeWithSize cnode;
s.push(root);
while (!s.isEmpty())
{ cnode=s.top();
if ((cnode.getLeft()!=null)&& (cnode.getLeft().visited==false))
{s.push(cnode.getLeft());}
else
{if ((cnode.getRight()!=null)&& (cnode.getRight().visited==false))
{ System.out.println(cnode.getdata());
cnode.visited=true;
s.pop();
s.push(cnode.getRight());}
else
{System.out.println(cnode.getdata());
cnode.visited=true;
s.pop();}}
}
}
}
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|