Problem: Depth First Search Code in C language.
Note : This is in Binary Search tree. So, actual algorithm of DFS is not working here.
Depth First Search (DFS) actual algorithm:
Mark the starting node of the graph as visited and push it onto the stack
While the stack is not empty
Peek at top node on the stack
If there is an unvisited child of that node
Mark the child as visited and push the child node onto the stack
Else
Pop the top node off the stack
Now this is for graph traversal, But we are implementing it in Binary search tree.
In Binary Search Tree(BST) Depth first Search will be in Three order
- Inorder Depth First Search
- Preorder Depth First Search
- PostOrder Depth First Search
In these inorder, preorder and postorder in Binary search tree we will use Postorder Depth First Search(DFS).
Depth First Search DFS code using Binary Search Tree in C:
---------------------------------------
/**
Author : Maniruzzaman Akash <manirujjamanakash@gmail.com>
Code : Breadth First Search Using Binary Search Tree in C language
**/
#include<stdio.h>
#include<stdlib.h>
int queue[100];
int front=0;
int rear=-1;
struct node{
int data;
struct node *left;
struct node *right;
};
/**Insert data in the tree**/
struct node *insert(struct node *root, int value){
if(root == NULL){
root = (struct node*) malloc(sizeof(struct node));
root->left = root->right = NULL;
root->data = value;
return root;
}else{
if(value < root->data){
root->left = insert(root->left, value);
}else{
if(value > root->data){
root->right = insert(root->right, value);
}
}
return root;
}
};
/** DFS function **/
void dfs(struct node *root){
if(root != NULL){
dfs(root->left);
dfs(root->right);
printf("%d ", root->data);
}
}
int main(){
struct node *root = NULL;
int choose;
int n=0, i=0, insertNode, limit;
printf("Enter Your choice : \n 1 For insert a node \n 2 For DFS \n 0 for exit the program");
printf("\n---------------------------------");
while(1){
printf("\nEnter your option : ");
scanf("%d", &choose);
switch(choose){
case 1:
printf("How many nodes of the tree :");
scanf("%d", &n);
for(i = 0; i < n; i++ ){
printf("Enter root : ");
scanf("%d", &insertNode);
root = insert(root, insertNode);
}
break;
case 2:
printf("DFS traversal of that tree is : ");
dfs(root);
break;
case 0:
exit(0);
break;
}
}
/** My input
node Number : 7
20 15 25 10 18 22 28
/** My input **/
return 0;
}
---------------------------------------
This is the simple implementation Depth First Search DFS code using Binary Tree in C language
Output :
0 comments:
Post a Comment