C Program to Traverse the Tree Recursively
Posted by Superadmin on December 09 2015 04:04:18

---

The following C program, using recursion, performs traversal operation across the nodes in a tree. The tree we have used is the binary search tree. The user generates a tree by inserting integers. The user is also asked to select one of the three modes of traversal, ie, infix, prefix and postfix. The user can use any of the three options to see the result. A binary search tree follows a concept of the nodes whose numbers are lesser than the parent/pointed node are linked to the left and the nodes whose number are greater than the parent/pointed node are linked to the right.


Here is the source code of the C program to traverse in a tree iteratively. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
* C Program to Traverse the Tree Recursively
*/
#include <stdio.h>
#include <stdlib.h>

struct node
{
int a;
struct node *left;
struct node *right;
};

void generate(struct node **, int);
void infix(struct node *);
void postfix(struct node *);
void prefix(struct node *);
void delete(struct node **);

int main()
{
struct node *head = NULL;
int choice = 0, num, flag = 0, key;

do
{
printf("\nEnter your choice:\n1. Insert\n2. Traverse via infix\n3.Traverse via prefix\n4. Traverse via postfix\n5. Exit\nChoice: ");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter element to insert: ");
scanf("%d", &num);
generate(&head, num);
break;
case 2:
infix(head);
break;
case 3:
prefix(head);
break;
case 4:
postfix(head);
break;
case 5:
delete(&head);
printf("Memory Cleared\nPROGRAM TERMINATED\n");
break;
default: printf("Not a valid input, try again\n");
}
} while (choice != 5);
return 0;
}

void generate(struct node **head, int num)
{
struct node *temp = *head, *prev = *head;

if (*head == NULL)
{
*head = (struct node *)malloc(sizeof(struct node));
(*head)->a = num;
(*head)->left = (*head)->right = NULL;
}
else
{
while (temp != NULL)
{
if (num > temp->a)
{
prev = temp;
temp = temp->right;
}
else
{
prev = temp;
temp = temp->left;
}
}
temp = (struct node *)malloc(sizeof(struct node));
temp->a = num;
if (num >= prev->a)
{
prev->right = temp;
}
else
{
prev->left = temp;
}
}
}

void infix(struct node *head)
{
if (head)
{
infix(head->left);
printf("%d ", head->a);
infix(head->right);
}
}

void prefix(struct node *head)
{
if (head)
{
printf("%d ", head->a);
prefix(head->left);
prefix(head->right);
}
}

void postfix(struct node *head)
{
if (head)
{
postfix(head->left);
postfix(head->right);
printf("%d ", head->a);
}
}

void delete(struct node **head)
{
if (*head != NULL)
{
if ((*head)->left)
{
delete(&(*head)->left);
}
if ((*head)->right)
{
delete(&(*head)->right);
}
free(*head);
}
}


$ pgm36.c
$ a.out

Enter your choice:
1. Insert
2. Traverse via infix
3. Traverse via prefix
4. Traverse via postfix
5. Exit
Choice: 1
Enter element to insert: 5

Enter your choice:
1. Insert
2. Traverse via infix
3. Traverse via prefix
4. Traverse via postfix
5. Exit
Choice: 1
Enter element to insert: 3

Enter your choice:
1. Insert
2. Traverse via infix
3. Traverse via prefix
4. Traverse via postfix
5. Exit
Choice: 1
Enter element to insert: 4

Enter your choice:
1. Insert
2. Traverse via infix
3. Traverse via prefix
4. Traverse via postfix
5. Exit
Choice: 1
Enter element to insert: 6

Enter your choice:
1. Insert
2. Traverse via infix
3. Traverse via prefix
4. Traverse via postfix
5. Exit
Choice: 1
Enter element to insert: 2

Enter your choice:
1. Insert
2. Traverse via infix
3. Traverse via prefix
4. Traverse via postfix
5. Exit
Choice: 2
2 3 4 5 6
Enter your choice:
1. Insert
2. Traverse via infix
3. Traverse via prefix
4. Traverse via postfix
5. Exit
Choice: 3
5 3 2 4 6
Enter your choice:
1. Insert
2. Traverse via infix
3. Traverse via prefix
4. Traverse via postfix
5. Exit
Choice: 4
2 4 3 6 5
Enter your choice:
1. Insert
2. Traverse via infix
3. Traverse via prefix
4. Traverse via postfix
5. Exit
Choice: 5
Memory Cleared
PROGRAM TERMINATED