Page 224 - DCAP407_DATA_STRUCTURE

Unit 12: Binary Tree Traversals and Operations

Consider the binary tree shown in the figure 12.2. The inorder traversing
traverses first the left sub-tree, then the node and then the right sub-tree.
Since, the traversing order is left sub-tree, root node and right sub-tree,
the alphabets L, N, R can be used for representing inorder traversal.
The term T1 LNR indicates that node T1 is the root node of the binary tree
and subscript LNR indicates inorder tree traversal.

T1 LNR---->T2 LNR T1 T3 LNR //After visiting T1 LNR
---->T4 LNR T2 µ T1 T3 LNR//After visiting T2 LNR

---->T7 LNR T4 T8 LNR T2 µ T1 T3 LNR//After visiting T4 LNR
---->µ T7 µ T4 T8 LNR T2 µ T1 T3 LNR//After visiting T7 LNR

---->T7 T4 µ T8 µ T2 µ T1 T3 LNR//After visiting T8 LNR
---->T7 T4 T8 T2 T1 T5 LNR T3 T6 LNR//After visiting T3 LNR

---->T7 T4 T8 T2 T1 µ T5T9 LNR T3 T6 LNR//After visiting T5 LNR
---->T7 T4 T8 T2 T1 T5µ T9µ T3 T6 LNR//After visiting T9 LNR

---->T7 T4 T8 T2 T1 T5T9T3 µ T6 µ//After visiting T6 LNR
---->T7 T4 T8 T2 T1 T5T9T3 T6
Hence, the inorder traversal for the tree shown in figure 12.2 is T7 T4 T8
T2 T1 T5T9T3 T6

Program for inserting elements into the tree and traversing in inorder
#include<stdio.h>

#include<conio.h>
/*Define tree as a structure with data and pointers to the left and right sub-tree*/
struct tree
{
long info;
struct tree *left;
struct tree *right;

};
/* bintree is declared as the datatype tree and initialized to Null*/
struct tree *bintree=NULL;
/*Global declaration of function insert which returns a pointer to the tree structure and accepts a
pointer to tree and a long digit as parameters */

struct tree *insert(struct tree*bintree,long digit);
/*Global declaration of function inorder which does not return any value and accepts a pointer to tree
as a parameter*/
void inorder(struct tree*bintree);
void main() // Define main function

LOVELY PROFESSIONAL UNIVERSITY 217