Binary Tree Program in C
This article will discuss the binary tree data structure and its implementation in the C programming language.
Introduction
A tree is a type of non-linear (hierarchical) data structure in C that consists of nodes connected through edges. The binary tree in C is distinct because the parent node may have up to two offspring nodes, 0, 1, or 2. At a binary tree node in C, three data variables are used to record the node's value, the pointer (or link) to the left child, and the pointer to the right child.
In a binary tree, the root is at the top, and the leaves are the bottom nodes. A hierarchical structure in which the root is at the top and the leaves are at the bottom can be used to represent a binary tree data structure.
In computer science, binary trees are used for many things, such as data storage and retrieval, network routing, game AI, and expression evaluation. They may also be used to execute other algorithms, including graph, sort, and search algorithms.
![Binary Tree Program in C](https://static.tutorialandexample.com/c/binary-tree-program-in-c1.png)
Implementing the Binary Tree
In this section, we will implement a full-fledged binary tree data structure with complete operations implemented.
Implementing the Node
First, we will learn to implement nodes in C because they are fundamentally used to build the whole binary tree.
In a binary tree, each node contains three crucial components:
- Data of the node
- Pointer to the left child
- Pointer to the right child
In C, we can use structures to implement nodes of the binary tree.
Code:
// Structure of each node of the tree with all three components
struct node {
int data; // First component of the node
struct node* left; // Second component of the node
struct node* right; // Finally, the last component of the node
};
Operations on a Binary Tree
Certain basic operations are needed to perform on a binary tree data structure,
- Inserting the element
- Removing the element
- Searching for the element
- Deletion of the element
- Traversal of the elements
Binary Tree Program
Below is the program to implement the binary tree data structure in the C programming language.
Code:
#include <stdio.h>
#include <stdlib.h>
// Define a structure for a node in the binary tree
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Function to create a new node with the given data
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function to insert a node into the binary tree
struct Node* insertNode(struct Node* root, int data) {
// If the tree is empty, create a new node and make it the root
if (root == NULL) {
root = createNode(data);
return root;
}
// Else, traverse the tree to find the appropriate position to insert the new node
else {
// If the data is less than the root's data, go to the left subtree
if (data < root->data) {
root->left = insertNode(root->left, data);
}
// If the data is greater than or equal to the root's data, go to the right subtree
else {
root->right = insertNode(root->right, data);
}
return root;
}
}
// Function to traverse the binary tree in an inorder fashion (left, root, right)
void inorderTraversal(struct Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
int main() {
// Create an empty binary tree
struct Node* root = NULL;
// Insert nodes into the binary tree
root = insertNode(root, 50);
insertNode(root, 30);
insertNode(root, 20);
insertNode(root, 40);
insertNode(root, 70);
insertNode(root, 60);
insertNode(root, 80);
// Print the nodes of the binary tree in inorder of traversal
printf("Inorder Traversal: ");
inorderTraversal(root);
return 0;
}
We have implemented a full-fledged binary tree data structure in the above program.
Firstly, we have declared a structure named Node to represent a node in our binary tree. It contains all the three components discussed earlier, namely data, a pointer to the left child, and a pointer to the right child with the variables data, left and right, respectively.
We have also defined three functions:
- createNode(): This function creates a new node with the given data and returns a pointer.
- insertNode(): It inserts a new node with the given data into the binary tree in the appropriate position based on the values of the existing nodes.
- inorderTraversal(): This function performs an inorder traversal of the binary tree, printing the nodes in the correct order, i.e., left, root, right.
Output:
![Binary Tree Program in C](https://static.tutorialandexample.com/c/binary-tree-program-in-c2.png)