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
0 comments:
Post a Comment