Depth First Search DFS code using Binary Tree in C language

Depth First Search DFS code using Binary Tree in C language

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

1. Inorder Depth First Search
2. Preorder Depth First Search
3. 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 :

Depth First Search DFS code using Binary Tree in C language

Continue reading

Share:

Views:

Breadth First Search BFS Using Binary Tree Code in C language

This is the solution of Breadth First Search code in C language.
The code is completed using binary tree and with the Breadth First Search (BFS) algorithm.

Breadth First Search (BFS) algorithm :

Mark the starting node of the graph as visited and enqueue it into the queue
    While the queue is not empty
        Dequeue the next node from the queue to become the current node
        While there is an unvisited child of the current node
            Mark the child as visited and enqueue the child node into the queue

Breadth First Search (BFS) Code in C language using Binary Tree:

--------------------------------------------

/**
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;
    }
};

void printNode(struct node *root){
    if(root != NULL) {
        printf("%d ", root->data);
    }
}

/******** Queue ********/
void enqueue(struct node *root){
    if(root != NULL){
        rear++;
        queue[rear] = root;
    }
}
void dequeue(){
    if(rear>=front){
        struct node *root = queue[front];
        printNode(root);
        front++;
        enqueue(root->left);
        enqueue(root->right);
    }
}

/** BFS function **/
void bfs(struct node *root){
    if(root != NULL){
        enqueue(root);
        do{
            dequeue(root);
        }while(front <= rear);
    }
}


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 BFS \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("BFS traversal of that tree is : ");
            bfs(root);
            break;

        case 0:
            exit(0);
            break;
        }
    }
    /** My input

    node Number  : 7
    20 15 25 10 18 22 28

    /** My input **/

    return 0;
}

--------------------------------------------

Breadth First Search BFS Using Binary Tree Code Output:

Continue reading

Share:

Views:

BFS, DFS, DLS in Tree implementation in C

The solutions of these problems are here:

1. Breadth First Search program (BFS) using Binary Search tree implementation in C language
2.  Depth First Search program (DFS) using Binary Search tree implementation in C language
3. Depth Limited Search(DLS) using Binary Search tree implementation in C language

Algorithms:

Breadth First Search (BFS) algrorithm:

Mark the starting node of the graph as visited and enqueue it into the queue
While the queue is not empty
    Dequeue the next node from the queue to become the current node
       While there is an unvisited child of the current node
       Mark the child as visited and enqueue the child node into the queue

Breadth First Search, Depth First Search and Depth Limited Search Code :

-------------------------------

#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;
    }
};

void printNode(struct node *root){
    if(root != NULL) {
        printf("%d ", root->data);
    }
}

/******** Queue ********/
void enqueue(struct node *root){
    if(root != NULL){
        rear++;
        queue[rear] = root;
    }
}
void dequeue(){
    if(rear>=front){
        struct node *root = queue[front];
        printNode(root);
        front++;
        enqueue(root->left);
        enqueue(root->right);
    }
}

/** BFS function **/
void bfs(struct node *root){
    if(root != NULL){
        enqueue(root);
        do{
            dequeue(root);
        }while(front <= rear);
    }
}

/**DFS function **/
void dfs(struct node *root){
    if(root != NULL){
        dfs(root->left);
        dfs(root->right);
        printf("%d ", root->data);
    }
}


/**DLS function**/
void dls(struct node *root, int i, int limit){
    for(i = 0; i < limit; i++){
        if(root != NULL){
            if(limit > 0){
                dls(root->left, i, limit-1 );
                dls(root->right, i, limit-1 );
                printf("%d ", root->data);
            }

        }
        //printf("\n");
    }
}


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 BFS \n 3 for DFS\n 4 for DLS\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("BFS traversal of that tree is : ");
            bfs(root);
            break;

        case 3:
            printf("DFS traversal of that tree is : ");
            dfs(root);
            break;

        case 4:
            printf("Enter the depth limit for DLS: ");
            scanf("%d", &limit);
            dls(root, 0, limit);
            break;

        case 0:
            exit(0);
            break;
        }
    }
}

/** My input

node Number  : 7
20 15 25 10 18 22 28

/** My input **/

-------------------------------

Continue reading

Share:

Views: