/* related posts with thumb nails */

“in order”, “post order” and “pre order” traversals in binary trees:

4 A Binary tree is a non-linear data structure in which each node has maximum of two child nodes. The tree connections can be called as branches.
4 Binary tree provides six traversals, which include “in order”, “post order” and “pre order” traversals.
4 Inorder gives us elements in ascending order
In order traversal:
In order traversal follows LVR method (L- left, V- visit vertex, R- right). This order gives sorted order in ascending order.
1. Move to the root node of a tree.
2. Move to its left node if exists.
3. Repeat the second step till a node with no left encounters.
4. Now, print the element and move to right if it exists.
5. Repeat the above three steps for all pending-nodes in a stack manner.
LVR(tree t)
{
if(t)
{
LVR(t.left);
System.out.println(t.x);
LVR(t.right);
}
}
Pre order traversal:
Pre order traversal follows VLR method
1. Move to the root node of a tree.
2. Print the element and move to left node if exists.
3. Repeat the second step till a node with no left encounters.
4. Now, move to right if it exists and print element.
5. Repeat the above three steps for all pending-nodes in a stack manner.
VLR(tree t)
{
if(t)
{
System.out.println(t.x);
VLR(t.left);
VLR(t.right);
}
}
Post order traversal:
Post order traversal follows LRV method
1. Move to the root node of a tree.
2. Move to left node if exists.
3. Repeat the second step till a node with no left encounters.
4. Now, move to right if it exists.
5. Repeat from step 2 till a node with no left and no right encounters.
6. Print the element.
7. Repeat the above three steps for all pending-nodes in a stack manner.
LRV(tree t)
{ if(t)
{
LRV(t.left);
LRV(t.right);
System.out.println(t.x);
}
}
40
56
48
35

28
Binary Tree

Example:
A binary tree is shown for the elements
40, 56, 35, 48, 22, 65, 28
In order (LVR): 22, 28, 35, 40, 48, 56, 65
Pre order (VLR): 40, 35, 22, 28, 56, 48, 65
Post Order (LRV): 28, 22, 35, 48, 65, 56, 40


Related Topics:

0 comments:

Post a Comment