Here’s a detailed implementation of a Binary Tree in C, covering essential operations like insertion, traversal, and deletion.
1. Node Structure
The structure of a binary tree node in C:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
- data: Stores the value of the node.
- left: Pointer to the left child.
- right: Pointer to the right child.
2. Creating a New Node
A function to create a new node dynamically:
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf(“Memory allocation failed.\n”);
exit(1);
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
3. Inserting Nodes
A simple insertion into a binary tree:
Node* insert(Node* root, int data) {
if (root == NULL) {
return createNode(data); // Create a new node if tree is empty
}
if (data < root->data) {
root->left = insert(root->left, data); // Insert into the left subtree
} else {
root->right = insert(root->right, data); // Insert into the right subtree
}
return root;
}
4. Traversing a Binary Tree
Traversal means visiting all nodes in a specific order:
- In-order Traversal: Left → Root → Right
void inorderTraversal(Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf(“%d “, root->data);
inorderTraversal(root->right);
}
}
- Pre-order Traversal: Root → Left → Right
void preorderTraversal(Node* root) {
if (root != NULL) {
printf(“%d “, root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
- Post-order Traversal: Left → Right → Root
void postorderTraversal(Node* root) {
if (root != NULL) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf(“%d “, root->data);
}
}
5. Searching for a Node
A function to search for a node with a given value:
Node* search(Node* root, int key) {
if (root == NULL || root->data == key) {
return root;
}
if (key < root->data) {
return search(root->left, key);
}
return search(root->right, key);
}
6. Deleting a Node
Deleting a node in a binary tree involves:
- Finding the node.
- Replacing it appropriately.
- Handling children (if any).
Node* findMin(Node* root) {
while (root->left != NULL) {
root = root->left;
}
return root;
}
Node* deleteNode(Node* root, int key) {
if (root == NULL) {
return root;
}
if (key < root->data) {
root->left = deleteNode(root->left, key);
} else if (key > root->data) {
root->right = deleteNode(root->right, key);
} else {
// Node with one child or no child
if (root->left == NULL) {
Node* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
Node* temp = root->left;
free(root);
return temp;
}
// Node with two children
Node* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
7. Main Function
A simple demonstration of the above functions:
int main() {
Node* root = NULL;
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 70);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 60);
root = insert(root, 80);
printf(“In-order Traversal: “);
inorderTraversal(root);
printf(“\n”);
printf(“Pre-order Traversal: “);
preorderTraversal(root);
printf(“\n”);
printf(“Post-order Traversal: “);
postorderTraversal(root);
printf(“\n”);
root = deleteNode(root, 50);
printf(“In-order Traversal after deletion: “);
inorderTraversal(root);
printf(“\n”);
return 0;
}
Output Example
For the above program:
In-order Traversal: 20 30 40 50 60 70 80
Pre-order Traversal: 50 30 20 40 70 60 80
Post-order Traversal: 20 40 30 60 80 70 50
In-order Traversal after deletion: 20 30 40 60 70 80