**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