This process when implemented iteratively also requires a stack and a boolean to prevent the execution from traversing any portion of a tree twice. The general process of in-order traversal follows the following steps:
1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then
a) Pop the top item from stack.
b) Print the popped item, set current = current->right
c) Go to step 3.
5) If current is NULL and stack is empty then we are done.
This iterative solution requires quite a few statements. Recursively, the processing occurs between the two recursive calls.
Non recursive solution using stack
Another solution is to use Morris Traversal, which do not use stack, but inorder successor of the node to traverse.
1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then
a) Pop the top item from stack.
b) Print the popped item, set current = current->right
c) Go to step 3.
5) If current is NULL and stack is empty then we are done.
This iterative solution requires quite a few statements. Recursively, the processing occurs between the two recursive calls.
// Recursive Inorder
void inorder(node *root)
{
if(root)
{
inorder(root->left);
printf("[%d] ", root->value);
inorder(root->right);
}
}
// Iterative Inorder using array as stack
void iterativeInorder (node *root)
{
node *save[100];
int top = 0;
while(root != NULL)
{
while (root != NULL)
{
if (root->right != NULL)
{
save[top++] = root->right;
}
save[top++] = root;
root = root->left;
}
root = save[--top];
while(top != 0 && root->right == NULL)
{
printf("[%d] ", root->value);
root = save[--top];
}
printf("[%d] ", root->value);
root = (top != 0) ? save[--top] : (mynode *) NULL;
}
}
Non recursive solution using stack
public static <T> void inOrderNonRecursiveStack(BSTNode<T> root) { BSTNode<T> current = root; Stack<BSTNode<T>> s = new Stack<BSTNode<T>>(); boolean done = false; while (!done) { if(current != null){ s.push(current); current = current.left; } else { if (!s.empty()) { current = s.pop(); System.out.print( current.data+" "); current = current.right; } else done = true; } } }
Another solution is to use Morris Traversal, which do not use stack, but inorder successor of the node to traverse.
0 comments:
Post a Comment