here's an example of C code for implementing and performing operations on a binary search tree, including creating, inserting, deleting, searching, tree traversals (preorder, inorder, postorder), level-order traversal using a queue, counting leaf, non-leaf, and total nodes, copying, and mirroring:
scss
Copy code
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Definition of binary search tree node
struct BSTNode {
int data;
struct BSTNode* left;
struct BSTNode* right;
};
// Function to create a new node
struct BSTNode* createNode(int data) {
struct BSTNode* newNode = (struct BSTNode*)malloc(sizeof(struct BSTNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function to insert a new node in BST
struct BSTNode* insertNode(struct BSTNode* root, int data) {
if (root == NULL) {
return createNode(data);
} else if (data <= root->data) {
root->left = insertNode(root->left, data);
} else {
root->right = insertNode(root->right, data);
}
return root;
}
// Function to search a node in BST
bool searchNode(struct BSTNode* root, int data) {
if (root == NULL) {
return false;
} else if (root->data == data) {
return true;
} else if (data <= root->data) {
return searchNode(root->left, data);
} else {
return searchNode(root->right, data);
}
}
// Function to delete a node from BST
struct BSTNode* deleteNode(struct BSTNode* root, int data) {
if (root == NULL) {
return root;
} else if (data < root->data) {
root->left = deleteNode(root->left, data);
} else if (data > root->data) {
root->right = deleteNode(root->right, data);
} else {
// Case 1: No child
if (root->left == NULL && root->right == NULL) {
free(root);
root = NULL;
}
// Case 2: One child
else if (root->left == NULL) {
struct BSTNode* temp = root;
root = root->right;
free(temp);
} else if (root->right == NULL) {
struct BSTNode* temp = root;
root = root->left;
free(temp);
}
// Case 3: Two children
else {
struct BSTNode* temp = findMinNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
}
return root;
}
// Function to find the minimum node in BST
struct BSTNode* findMinNode(struct BSTNode* root) {
while (root->left != NULL) {
root = root->left;
}
return root;
}
// Function to perform preorder traversal of BST
void preorderTraversal(struct BSTNode* root) {
if (root != NULL) {
printf("%d ", root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
// Function to perform inorder traversal of BST
void inorderTraversal(struct BSTNode* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
Binary Search Tree (BST) is a type of binary tree, where the value of each node in the left subtree is less than or equal to the value of the root node, and the value of each node in the right subtree is greater than or equal to the value of the root node.
Here is the definition of the BSTNode structure:
arduino
Copy code
struct BSTNode {
int data;
struct BSTNode* left;
struct BSTNode* right;
};
data holds the value of the node.
left is a pointer to the left child node.
right is a pointer to the right child node.
Create a new node
To create a new node, we need to allocate memory dynamically using malloc() function and initialize its data, left and right fields. Here is the code for creating a new node:
c
Copy code
struct BSTNode* createNode(int data) {
struct BSTNode* newNode = (struct BSTNode*)malloc(sizeof(struct BSTNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
Insert a node
To insert a node in the BST, we need to follow the following steps:
If the root is NULL, create a new node with the given data and return it.
If the data is less than or equal to the value of the root node, recursively insert the data in the left subtree.
If the data is greater than the value of the root node, recursively insert the data in the right subtree.
Here is the code for inserting a node:
kotlin
Copy code
struct BSTNode* insertNode(struct BSTNode* root, int data) {
if (root == NULL) {
return createNode(data);
} else if (data <= root->data) {
root->left = insertNode(root->left, data);
} else {
root->right = insertNode(root->right, data);
}
return root;
}
Search a node
To search a node in the BST, we need to follow the following steps:
If the root is NULL, return false.
If the data is equal to the value of the root node, return true.
If the data is less than the value of the root node, recursively search in the left subtree.
If the data is greater than the value of the root node, recursively search in the right subtree.
Here is the code for searching a node:
kotlin
Copy code
bool searchNode(struct BSTNode* root, int data) {
if (root == NULL) {
return false;
} else if (root->data == data) {
return true;
} else if (data <= root->data) {
return searchNode(root->left, data);
} else {
return searchNode(root->right, data);
}
}
Delete a node
To delete a node from the BST, we need to follow the following steps:
If the root is NULL, return it.
If the data is less than the value of the root node, recursively delete from the left subtree.
If the data is greater than the value of the root node, recursively delete from the right subtree.
If the data is equal to the value of the root node:
If the node has no child, simply delete it.
If the node has one child, replace it with its child.
If the node has two children, find the minimum node in the right subtree, replace the node with it, and recursively delete the minimum node from the right subtree.
Here is the code for deleting a node:
arduino
Copy code
struct BSTNode
, Level-order traversal using queue, Counting leaf, non-leaf and total nodes, Copy, Mirror.){kind=link}
0 Comments