Friday, 24 November 2017

Linked Representation of Tree: A Non-Linear Data Structure

As we say, sequential representation is acceptable for complete binary trees, but it wastes space for many other binary trees.  In, addition, this representation suffers from the general inadequacies of other sequential representations.  Thus, insertion or deletion of nodes from the middle of a tree requires the movement of potentially many nodes to reflect the change in the level of these nodes.  We can easily overcome these problems by using a linked representation.  Each node has three fields, left_child, data, and right_child as two pictures show the node representation of the binary tree below:


Binary Tree Traversals:
There are many operations that we can perform on tree, but one that arises frequently is traversing a tree, that is, visiting each node in the tree exactly once.  A full traversal produces a linear order for the information in a tree.

Binary Tree Traversals Types: 
1. In_order Traversal (Left, Parent, Right)
2. Pre_order Traversal (Parent, Left, Right)
3. Post_order Traversal (Left, Right, Parent)
Level Order Traversal (Top to Bottom, Left to Right)

Example of Binary Tree taken into consideration :


Different Binary tree traversals functions are discussed below:

In_order Tree Traversal Recursive function:
void    in_order(ptr_node  ptr)
{
if (ptr)
{
in_order(ptr->left_child);
cout << ptr->data;
in_order(ptr->right_child);
}
}

In_order traversal of the above tree example is:
H, D, I, B, J, E, K, A, L, F, M, C, N, G, O

Pre_order Tree Traversal Recursive function:
void    pre_order(ptr_node  ptr)
{
if  (ptr)
{
cout << ptr->data;
pre_order(ptr->left_child);
pre_order(ptr->right_child);
}
}

Pre_order traversal of the above tree example is:
A, B, D, H, I, E, J, K, C, F, L, M, G, N, O

Post_order Tree Traversal Recursive function:
void    Post_order(ptr_node  ptr)
{
if  (ptr)
{
Post_order(ptr->left_child);
Post_order(ptr->right_child);
cout << ptr->data;
}
}

Post_order traversal of the above tree example is:
H, I, D, J, K, E, B, L, M, F, N, O, G, C, A


Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput