Binary Tree implementation in C
Tree is a non-linear data structure which deals with root element and child nodes.Root is the main node which connects the entire data structure. It has childs which is divided into 2 types. The two categories are Left and right.
Let us create a binary tree which has exactly two child is
given below…
C implementation of binary Tree using Linked list:
- Here, the binary tree is created using linked list. A node is created as root. It has two nodes and data.
- ‘createNode()’ creates a node with memory and data.
- There are three traversal to print the node data.
- Pre-order traversal: It follows ‘Root-left child-right child’ format.
- Post – order traversal:it uses ‘left child – right child- root’ format.
- In-order traversal:It has ‘left child- root- right child’ format.
Code:
#include <stdio.h>
#include <stdlib.h>
// create the tree as linked list
struct T_Node {
int data;
struct T_Node*
left;
struct T_Node*
right;
};
// create a new node
struct T_Node* createNode(int value) {
struct T_Node*
nNode = (struct T_Node*)malloc(sizeof(struct T_Node));
nNode->data =
value;
nNode->left =
NULL;
nNode->right =
NULL;
return nNode;
}
// Add a node into the binary tree
struct T_Node* insert(struct T_Node* root, int value) {
if (root == NULL)
{
return
createNode(value);
}
if (value <
root->data) {
root->left
= insert(root->left, value);
} else {
root->right
= insert(root->right, value);
}
return root;
}
// let us create the Inorder traversal
void inorder(struct T_Node* root) {
if (root != NULL)
{
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
// this is the Preorder traversal
void preorder(struct T_Node* root) {
if (root != NULL)
{
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
// Here, is the Postorder traversal
void postorder(struct T_Node* root) {
if (root != NULL)
{
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
}
int main() {
struct T_Node*
root = NULL;
// Insert the
values to the binary tree
root =
insert(root, 140);
insert(root, 25);
insert(root, 65);
insert(root, 45);
insert(root, 167);
insert(root, 180);
insert(root, 80);
insert(root,89);
insert(root,245);
// Traversals
printf("Inorder traversal of the binary tree is:\n ");
inorder(root);
printf("\n");
printf("Preorder traversal of the binary tree is:\n ");
preorder(root);
printf("\n");
printf("Postorder traversal of the binary tree is:\n ");
postorder(root);
printf("\n");
return 0;
}
Output:
Inorder traversal of the binary tree is:
25 45 65 80 89 140
167 180 245
Preorder traversal of the binary tree is:
140 25 65 45 80 89
167 180 245
Postorder traversal of the binary tree is:
45 89 80 65 25 245
180 167 140
Hence, the code is completed. It implemented the binary Tree in C using linked list. Hope, this code is useful to you. Keep Coding!!!
Comments
Post a Comment