Binary Search Tree operations in C

-

               Binary Search Tree is a binary Tree which follows a unique key and tree ordering. It strictly follows the left and right nodes values should be in order in such that it satisfies the binary tree condition.

Let us implement the searching in Binary Search Tree in C language.

Program implementation:

  • It includes the header files.
  • The Node is created first. It has a data, left child and right child.
  • To create a node, memory should be allocated. The data, left, right node pointers are assigned with the node.
  • Next, insert function is created. It reads the data and assigns the left and right pointer.
  • Search function is implemented. It gets the value from the user. It checks the value in the tree. If the value is found, it displays the found message.
  • Otherwise, it displays not found message.
  • Finally, it prints the value.

 C Code:

#include <stdio.h>

#include <stdlib.h>

struct BST_Node {

    int b_data;

    struct BST_Node *b_left, *b_right;

};

//It is the function to create a new node

struct BST_Node* create_Node(int value) {

    struct BST_Node* new_Node = (struct BST_Node*)malloc(sizeof(struct BST_Node));

    new_Node->b_data = value;

    new_Node->b_left = new_Node->b_right = NULL;

    return new_Node;

}

//Function to Insert values

struct BST_Node* insertIt(struct BST_Node* root, int value) {

    if (root == NULL) {

        return create_Node(value);

    }

    if (value <root->b_data) {

        root->b_left = insertIt(root->b_left, value);

    } else if (value > root->b_data) {

        root->b_right = insertIt(root->b_right, value);

    }

    return root;

}

// Search function

struct BST_Node* search(struct BST_Node* root, int key) {

    if (root == NULL || root->b_data == key) {

        return root;

    }

    if (key < root->b_data) {

        return search(root->b_left, key);

    }

    return search(root->b_right, key);

}

// Search a value

void in_order(struct BST_Node* root) {

    if (root != NULL) {

        in_order(root->b_left);

        printf("%d ", root->b_data);

        in_order(root->b_right);

    }

}

int main() {

    struct BST_Node* root = NULL;

    root = insertIt(root, 65);

    insertIt(root, 13);

    insertIt(root, 87);

    insertIt(root, 25);

    insertIt(root, 42);

    insertIt(root, 69);

    insertIt(root, 110);

    printf("Inorder traversal: ");

    in_order(root);

    int key;

    printf("\nEnter the search value:");

    scanf("%d",&key);

    struct BST_Node* result = search(root, key);

    if (result != NULL) {

        printf("\nThe Element %d found in BST.\n", key);

    } else {

        printf("\nThe Element %d not found in BST.\n", key);

    }

    return 0;

}

Output:

Inorder traversal: 13 25 42 65 69 87 110

Enter the search value:87

The Element 87 found in BST.

That’s all. The C Program to implement the operations in Binary Search Tree was successful. Keep Coding!!!!

Comments

Post a Comment

Popular posts from this blog

How to create a XML DTD for displaying student details

-
Image
XML  is    e X tensible M arkup L anguage which is used to create used defined tags.  It has Elements  ( <STUDENT>) Attributes (<STUDENT id="21it21">) To create a XML file, create three files 1 ->  XML file (used to declare the user defined tags) 2 ->  DTD file (used to define the user defined tags) 3 ->  HTML file(used to display the xml file as web page) create these three files using any editor like notepad.  Student.Xml <?xml version="1.0"?> <!DOCTYPE STUDENTS SYSTEM "E:\XML1\STUDENT.dtd"> <STUDENTS>  <STUDENT>  <STUDENTDATA>     <NAME> SUTHA </NAME>     <ID>  2007IT51 </ID>     <AGE> 20 </AGE>     <ADDRESS> 12, SATHY ROAD , GOBI </ADDRESS>   </STUDENTDATA> </STUDENT> </STUDENTS> Student.dtd <?xml version="1.0"?> <!ELEMENT STU...
Read more

Employee record management in C

-
               Let us create a employee record management in C. A employee record has name, id and salary. The operations are adding the details, search an employee, delete a record and display the employee records. Program implementation: #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 100 struct Employee {     int e_id;     char e_name[50];     float e_salary; }; struct Employee emp[MAX]; int count = 0; void addEmployee() {     printf("\nEnter the Employee id: ");     scanf("%d", &emp[count].e_id);     printf("Enter the Employee Name: ");     scanf(" %[^\n]", emp[count].e_name);     printf("Enter the salary: ");     scanf("%f", &emp[count].e_salary);     count++;     printf("Employee details ar...
Read more

File handling in C++

-
                 Files are important feature in any programming language. File handling refers to reading and writing information in the files. Files have some formats like .txt,.csv and so on. C++ has lot of standard library files to handles file management. Eg: < fstream > header file   has ofstream , ifstream ,fstream. It also has ifstream(input file stream) and   ofstream(output file stream). Let us create objects and open the file as follows… Eg: ‘ifstream’ : ifstream filein("sample .txt "); ‘ofstream’ : ofstream fileout("sample.txt"); Where filein ,fileout are objects accordingly. If you are using ‘fstream’, it needs to open a file like this. ‘fstream fstr("sample.text", mode);’ Here, fstr is the object of fstream. “sample.txt” is the file name. Mode is   the purpose of operation going to be performed in the file. It has variety of types. Modes: ‘ ios::app ’ – append the contents to the en...
Read more