Building and Searching a Binary Search Tree in C Language
Introduction
A Binary Search Tree (BST) is a special type of binary tree that has the following properties:
- Each node has a value.
- For each node, all values in its left subtree are less than the value of that node.
- For each node, all values in its right subtree are greater than the value of that node.
This structure allows us to efficiently perform insertion, deletion, and search operations. This article will detail how to build a simple binary search tree in C language and implement basic search functionality.
Data Structure Definition
First, we need to define a data structure that represents a node in the binary search tree. Each node contains three parts: the stored data, a pointer to the left subtree, and a pointer to the right subtree.
#include <stdio.h>#include <stdlib.h>// Define the binary search tree nodetypedef struct Node { int data; // Node data struct Node* left; // Pointer to the left child struct Node* right; // Pointer to the right child} Node;Creating a New Node
Next, we need a function to create new nodes. This function will allocate memory and initialize the newly created node.
// Create a new nodeNode* createNode(int value) { Node* newNode = (Node*)malloc(sizeof(Node)); // Allocate memory newNode->data = value; // Set the data field newNode->left = NULL; // Initialize left pointer to NULL newNode->right = NULL; // Initialize right pointer to NULL return newNode;}Insertion Operation
Now let’s implement the insertion operation. When inserting, we need to compare the current value with the root node to decide whether to place it on the left or right.
// Insert an element into the binary search treeNode* insert(Node* root, int value) { if (root == NULL) { // If the current root is NULL, create a new node and return it as the new root return createNode(value); } if (value < root->data) { // If the value to be inserted is less than the current root, recursively insert into the left subtree root->left = insert(root->left, value); } else { // Otherwise, recursively insert into the right subtree root->right = insert(root->right, value); } return root; // Return the unchanged new root }Search Operation
Next is the search operation. If the target value is found, return the corresponding pointer; if not found, return <span>NULL</span>.
// Check if an element exists in the binary search treeint search(Node* root, int value) { if (root == NULL) { // If the current root is NULL, the target element is not found return 0; } if (value == root->data) { // Found the target element return 1; } else if (value < root->data) { // Continue searching in the left subtree return search(root->left, value); } else { // Continue searching in the right subtree return search(root->right, value); }}Main Program Example
Finally, we write the main program to test our code, including building a BST and performing some search operations.
int main() { Node* root = NULL; /* Insert some data */ int values[] = {50, 30, 20, 40, 70, 60, 80}; // Insert each number from the array into the BST for(int i=0;i<7;i++) { root = insert(root, values[i]); } /* Search for some numbers */ int toSearch[] = {25, 40}; for(int i=0;i<2;i++) { printf("Searching for %d: ", toSearch[i]); if(search(root,toSearch[i])) { printf("Found\n"); } else { printf("Not Found\n"); } } return 0;}Example Output:
After running the above code, you might see the following output:
Searching for 25: Not Found Searching for 40: Found Conclusion
This article introduced how to build and use a simple binary search tree in C language, including basic functionalities such as creation, insertion, and searching. This data structure is very suitable for fast searching and ordered data storage. In practical applications, more functionalities can be extended based on needs, such as deletion and traversal. I hope this article helps you better understand and use binary search trees.