Tree Traversals
Example Tree
(a) Inorder
(b) Preorder
(c) Postorder
Breadth First or Level Order Traversal
Please see this post for Breadth First Traversal.
Inorder Traversal:
Algorithm Inorder(tree)
1. Traverse the left subtree, i.e., call Inorder(left-subtree)
2. Visit the root.
3. Traverse the right subtree, i.e., call Inorder(right-subtree)
Uses of InorderIn case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing (Increasing) order. Lets say we have BInary Search Tree as Below
4
/ \
/ \
2 7
Inorder Traversal Gives 2 , 4 and 7.
To get nodes of BST in non-increasing order, a variation of Inorder traversal where
Inorder itraversal s reversed, can be used.
Example: Inorder traversal for the above given figure is 4 2 5 1 3.
Preorder Traversal:
Algorithm Preorder(tree)
1. Visit the root.
2. Traverse the left subtree, i.e., call Preorder(left-subtree)
3. Traverse the right subtree, i.e., call Preorder(right-subtree)
Uses of PreorderPreorder traversal is used to create a copy of the tree.
Preorder traversal is also used to get prefix expression on of an expression tree.
Please see http://en.wikipedia.org/wiki/Polish_notation to know why prefix expressions are useful.
Example: Preorder traversal for the above given figure is 1 2 4 5 3.
Postorder Traversal:
Algorithm Postorder(tree)
1. Traverse the left subtree, i.e., call Postorder(left-subtree)
2. Traverse the right subtree, i.e., call Postorder(right-subtree)
3. Visit the root.
Uses of PostorderPostorder traversal is used to delete the tree. Postorder traversal is also useful to get the postfix expression of an expression tree.
Example: Postorder traversal for the above given figure is 4 5 2 3 1.
#include <stdio.h> #include <stdlib.h> /* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { int data; struct node* left; struct node* right; }; /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode(int data) { struct node* node = (struct node*) malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return(node); } /* Given a binary tree, print its nodes according to the "bottom-up" postorder traversal. */ void printPostorder(struct node* node) { if (node == NULL) return; // first recur on left subtree printPostorder(node->left); // then recur on right subtree printPostorder(node->right); // now deal with the node printf("%d ", node->data); } /* Given a binary tree, print its nodes in inorder*/ void printInorder(struct node* node) { if (node == NULL) return; /* first recur on left child */ printInorder(node->left); /* then print the data of node */ printf("%d ", node->data); /* now recur on right child */ printInorder(node->right); } /* Given a binary tree, print its nodes in inorder*/ void printPreorder(struct node* node) { if (node == NULL) return; /* first print data of node */ printf("%d ", node->data); /* then recur on left sutree */ printPreorder(node->left); /* now recur on right subtree */ printPreorder(node->right); } /* Driver program to test above functions*/ int main() { struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); printf("\n Preorder traversal of binary tree is \n"); printPreorder(root); printf("\n Inorder traversal of binary tree is \n"); printInorder(root); printf("\n Postorder traversal of binary tree is \n"); printPostorder(root); getchar(); return 0; }
Iterative Preorder TraversalTo convert an inherently recursive procedures to iterative, we need an explicit stack .
Following is a simple stack based iterative process to print Preorder traversal.
1) Create an empty stack nodeStack and push root node to stack. 2) Do following while nodeStack is not empty. ….a) Pop an item from stack and print it. ….b) Push right child of popped item to stack ….c) Push left child of popped item to stack Sample Code : |
// An iterative process to print preorder traversal of Binary tree void iterativePreorder(node *root) { // Base Case if (root == NULL) return; // Create an empty stack and push root to it stack<node *> nodeStack; nodeStack.push(root); /* Pop all items one by one. Do following for every popped item a) print it b) push its right child c) push its left child Note that right child is pushed first so that left is processed first */ while (nodeStack.empty() == false) { // Pop the top item from stack and print it struct node *node = nodeStack.top(); printf ("%d ", node->data); nodeStack.pop(); // Push right and left children of the popped node to stack if (node->right) nodeStack.push(node->right); if (node->left) nodeStack.push(node->left); } }
Iterative Inorder Traversal :
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.
Let us consider the below tree for example
1
/ \
2 3
/ \
4 5
Step 1 Creates an empty stack: S = NULL
Step 2 sets current as address of root: current -> 1
Step 3 Pushes the current node and set current = current->left until current is NULL
current -> 1
push 1: Stack S -> 1
current -> 2
push 2: Stack S -> 2, 1
current -> 4
push 4: Stack S -> 4, 2, 1
current = NULL
Step 4 pops from S
a) Pop 4: Stack S -> 2, 1
b) print "4"
c) current = NULL /*right of 4 */ and go to step 3
Since current is NULL step 3 doesn't do anything.
Step 4 pops again.
a) Pop 2: Stack S -> 1
b) print "2"
c) current -> 5/*right of 2 */ and go to step 3
Step 3 pushes 5 to stack and makes current NULL
Stack S -> 5, 1
current = NULL
Step 4 pops from S
a) Pop 5: Stack S -> 1
b) print "5"
c) current = NULL /*right of 5 */ and go to step 3
Since current is NULL step 3 doesn't do anything
Step 4 pops again.
a) Pop 1: Stack S -> NULL
b) print "1"
c) current -> 3 /*right of 5 */
Step 3 pushes 3 to stack and makes current NULL
Stack S -> 3
current = NULL
Step 4 pops from S
a) Pop 3: Stack S -> NULL
b) print "3"
c) current = NULL /*right of 3 */
Traversal is done now as stack S is empty and current is NULL.
/* Iterative function for inorder tree traversal */
void inOrder(struct tNode *root)
{
/* set current to root of binary tree */
struct tNode *current = root;
struct sNode *s = NULL; /* Initialize stack s */
bool done = 0;
while (!done)
{
/* Reach the left most tNode of the current tNode */
if(current != NULL)
{
/* place pointer to a tree node on the stack before traversing
the node's left subtree */
push(&s, current);
current = current->left;
}
/* backtrack from the empty subtree and visit the tNode
at the top of the stack; however, if the stack is empty,
you are done */
else
{
if (!isEmpty(s))
{
current = pop(&s);
printf("%d ", current->data);
/* we have visited the node and its left subtree.
Now, it's right subtree's turn */
current = current->right;
}
else
done = 1;
}
} /* end of while */
}
Iterative Post order Traversal :
Iterative postorder traversal is discussed which is more complex than the other two traversals (due to its nature of non-tail recursion, there is an extra statement after the final recursive call to itself).The postorder traversal can easily be done using two stacks though. The idea is to push reverse postorder traversal to a stack. Once we have reverse postorder traversal in a stack, we can just pop all items one by one from the stack and print them, this order of printing will be in postorder because of LIFO property of stacks.
Now the question is, how to get reverse post order elements in a stack – the other stack is used for this purpose. For example, in the following tree, we need to get 1, 3, 7, 6, 2, 5, 4 in a stack. If take a closer look at this sequence, we can observe that this sequence is very similar to preorder traversal.The only difference is right child is visited before left child and therefore sequence is “root right left” instead of “root left right”.
So we can do something like iterative preorder traversal with following differences.
a) Instead of printing an item, we push it to a stack.
b) We push left subtree before right subtree.
Following is the complete algorithm.
After step 2, we get reverse postorder traversal in second stack.
We use first stack to get this order.
1. Push root to first stack.
2. Loop while first stack is not empty
2.1 Pop a node from first stack and push it to second stack
2.2 Push left and right children of the popped node to first stack
3. Print contents of second stack
Following are the steps to print postorder traversal of the above tree using two stacks.
1. Push 1 to first stack.
First stack: 1
Second stack: Empty
2. Pop 1 from first stack and push it to second stack.
Push left and right children of 1 to first stack
First stack: 2, 3
Second stack: 1
3. Pop 3 from first stack and push it to second stack.
Push left and right children of 3 to first stack
First stack: 2, 6, 7
Second stack:1, 3
4. Pop 7 from first stack and push it to second stack.
First stack: 2, 6
Second stack:1, 3, 7
5. Pop 6 from first stack and push it to second stack.
First stack: 2
Second stack:1, 3, 7, 6
6. Pop 2 from first stack and push it to second stack.
Push left and right children of 2 to first stack
First stack: 4, 5
Second stack:1, 3, 7, 6, 2
7. Pop 5 from first stack and push it to second stack.
First stack: 4
Second stack: 1, 3, 7, 6, 2, 5
8. Pop 4 from first stack and push it to second stack.
First stack: Empty
Second stack: 1, 3, 7, 6, 2, 5, 4
// An iterative function to do post order traversal of a given binary tree void postOrderIterative(struct Node* root) { // Create two stacks struct Stack* s1 = createStack(MAX_SIZE); struct Stack* s2 = createStack(MAX_SIZE); // push root to first stack push(s1, root); struct Node* node; // Run while first stack is not empty while (!isEmpty(s1)) { // Pop an item from s1 and push it to s2 node = pop(s1); push(s2, node); // Push left and right children of removed item to s1 if (node->left) push(s1, node->left); if (node->right) push(s1, node->right); } // Print all elements of second stack while (!isEmpty(s2)) { node = pop(s2); printf("%d ", node->data); } }
With Single Stack :
The idea is to move down to leftmost node using left pointer. While moving down, push root and root’s right child to stack. Once we reach leftmost node, print it if it doesn’t have a right child. If it has a right child, then change root so that the right child is processed before.
Following is detailed algorithm.
1.1 Create an empty stack
2.1 Do following while root is not NULL
a) Push root's right child and then root to stack.
b) Set root as root's left child.
2.2 Pop an item from stack and set it as root.
a) If the popped item has a right child and the right child
is at top of stack, then remove the right child from stack,
push the root back and set root as root's right child.
b) Else print root's data and set root as NULL.
2.3 Repeat steps 2.1 and 2.2 while stack is not empty.
// An iterative function to do postorder traversal of a given binary tree void postOrderIterative(struct Node* root) { // Check for empty tree if (root == NULL) return; struct Stack* stack = createStack(MAX_SIZE); do { // Move to leftmost node while (root) { // Push root's right child and then root to stack. if (root->right) push(stack, root->right); push(stack, root); // Set root as root's left child root = root->left; } // Pop an item from stack and set it as root root = pop(stack); // If the popped item has a right child and the right child is not // processed yet, then make sure right child is processed before root if (root->right && peek(stack) == root->right) { pop(stack); // remove right child from stack push(stack, root); // push root back to stack root = root->right; // change root so that the right // child is processed next } else // Else print root's data and set root as NULL { printf("%d ", root->data); root = NULL; } } while (!isEmpty(stack)); }
No comments:
Post a Comment