/** Iteratively traverses the binary tree in pre-order */
public void preorder( ) {
if( root == null ) return;
Stack<Node> stack = new Stack<Node>( );
stack.push( root );
while( ! stack.isEmpty( ) ) {
Node current = stack.pop( );
if( current.right != null ) stack.push( current.right );
if( current.left != null ) stack.push( current.left );
System.out.print( current.data + " " );
}
}
/** Iteratively traverses the binary tree in in-order */
public void inorder( ) {
Node node = root;
Stack<Node> stack = new Stack<Node>( );
while( ! stack.isEmpty( ) || node != null ) {
if( node != null ) {
stack.push( node );
node = node.left;
} else {
node = stack.pop( );
System.out.print( node.data + " " );
node = node.right;
}
}
}
/** Iteratively traverses the binary tree in post-order */
public void postorder( ) {
if( root == null ) return;
Stack<Node> stack = new Stack<Node>( );
Node current = root;
while( true ) {
if( current != null ) {
if( current.right != null ) stack.push( current.right );
stack.push( current );
current = current.left;
continue;
}
if( stack.isEmpty( ) ) return;
current = stack.pop( );
if( current.right != null && ! stack.isEmpty( ) && current.right == stack.peek( ) ) {
stack.pop( );
stack.push( current );
current = current.right;
} else {
System.out.print( current.data + " " );
current = null;
}
}
}
Wednesday, September 25, 2013
Iterative Binary Tree Traversal in Java
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment