Non-Linear Data Structure 535
P
O
V W
(b)
Fig. 15.7{a) Tree representation (b) Linked representation
The structure for a tree node would be as follows.
struct node
{
int num;
struct node *ls;
struct node *rs
>
The pointers *ls and *rs point to the structure node. The pointer *ls contains the address of the left son
and rs is the pointer to the right son. If there are no left son and right son, then the pointers would be
NULL.
15.5 TRAVERSING BINARY TREES
As discussed earlier, three parameters are needed for formation of a binary tree. Passing through every
node of the tree is called traversing. Therefore, traversing of a tree means traversing of a node, left and
right subtrees. Assume that the root is indicated by O, left subtree as L and right subtree as R. Then, the
following traverse combinations are possible.
1) ORL: ROOT-RIGHT-LEFT
2) OLR: ROOT-LEFT-RIGHT
3) LOR: LEFT-ROOT-RIGHT
4) LRO: LEFT -RIGHT- ROOT
5) ROL: RIGHT-ROOT-LEFT
6) RLO: RIGHT-LEFT-ROOT
From the above six methods only three are standard and are discussed below. The right subtree is
always traversed after the left subtree. Hence, the OLR is preorder, LOR is inorder, and LRO is postorder.
536 Programming and Data Structures
Postorder: V-R-S-P-T-U-Q-O.
Fig. 15.8 A model tree
1) OLR traversal (preorder): As per Fig. 15.9, the nodes of Fig. 15.8 are traversed in preorder as
O-P-R-V-S-Q-T-U.
Go to the root
Traverse the left subtree
Traverse the right subtrees
Root I
Left subtree
Right subtree
Fig. 15.9 Preorder
2) LOR (inorder): As per Fig. 15.10, the nodes of Fig. 15.8 are traversed in inorder as
R-V-P-S-O-T-Q-U.
Traverse the left subtree
Go to the root
Traverse the right subtree
Fig. 15.10 Inorder
Non-Linear Data Structure 537
3) LRO ( postorder): As per Fig. 15.11 and Fig. 15.8, nodes are traversed in postorder as
V-R-S-P-T-U-Q-O.
Traverse the left subtree
Traverse the right subtree
Go to the root
Fig. 15.11 Postorder
Level order traversal: In this type of level order traversal, the nodes are accessed according to their
levels. The traversing starts from zero to n, where n is the last level number.
( O 1
Level 0
( p T
Level 1
(5 vD © (5)
Level 2
v v
Level 3
Fig. 15.12 Level order traversal
As per Fig. 15.12, the nodes are traversed in level order as O-P-Q-R-S-T-U-V.
Here is a program that implements different traversing methods.
15.1 Write a program to create tree structure. Perform insert, delete, and traverse the elements
with different methods.
# include <stdio.h>
# include <znalloc.h>
# include cconio.h>
# include <process.h>
struct nodes
{
int data;
struct nodes *ls;
struct nodes *rs;
538 Programming and Data Structures
}*tree;
mainQ
{
Int Insert (in t);
int del (in t);
int inorder (struct nodes +);
int preorder (struct nodes * );
int postorder (struct nodes * );
int show (struct nodes*,int);
int option, number;
tree=0;
clrscr();
while(1)
{
printf ("n");
printf (" 1. Insertn");
p rin tf("2.Delete
");
printf ("3. Inorder Traversal
");
printf ("4. Preorder Traversaln");
printf ("5.Postorder Traversal n");
printf ("6.Display
");
printf ("7.Exitn");
printf ("Enter your option: ") ;
scanf ("%d", fcoptian) ;
switch (option)
{
case 1:
printf ("Enter the number (0 to exit): ") ;
while(1)
{
scanf ( "%d", fcnumber) ;
i f (number==0) break;
insert (number);
}
break;
case 2:
prin tf ("Enter the number to be deleted: ") ;
scanf("%d",&number);
del (number);
break;
case 3:
inorder (tree) ;
break;
case 4:
preorder(tree);
Non-Linear Data Structure 539
break;
case 5:
postorder (t r e e );
break;
case 6:
shew (tree, 1) ;
break;
case 7:
e x it (0);
default:
printf ("Wrong qption
”) ;
}
}
search (int ele, struct nodes **p, struct nodes **1)
{
struct nodes *pr, *p_s;
if(tree==0)
{
*1-0 >
*p*0;
return 0;
}
if(ele==tree->data)
{
*l=tree;
*p=0;
return 0;
}
i f (ele<tree->data)
pr=tree->ls;
else
pr=tree->rs;
p s=tree;
while(prl=0)
{
i f (ele==pr-xiata)
{ *l= p r;
*p=p_s;
return 0;
>
p_s=pr;
if(ele<pr->data)
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.