Tree Data Structure in C
Introduction
A fundamental idea in computer science, the tree data structure is essential to many algorithms and applications. We will dig into the realm of trees and examine how they are used in the C programming language in this tutorial. We will cover everything, from comprehending the fundamental terms used to describe trees to implementing typical operations like insertion, deletion, and traversal. This thorough manual will provide you with the information and abilities you need to efficiently deal with trees in C, whether you're a novice or an expert programmer wishing to brush up on your skills.
What is Tree?
A tree is a hierarchical data structure consisting of nodes connected by edges, with a single node designated as the root node. It develops numerous layers of branching, like a tree, with each node having the ability to have child nodes.
Basic Terminology
Let's become more familiar with certain key terms so that we might understand trees better:
- Root Node: The topmost node of a tree.
- Parent Node: A node that has one or more child nodes.
- Child Node: A node associated with a parent node
- Leaf Node: Nodes that have no children.
- Subtree: a node and all of its children make up a tree inside of a tree.
The Tree Implementation in C
A structure and pointers can be used in C to implement a tree. Here is an example of the basic tree data structure:
typedef struct TreeNode { int data; struct TreeNode* left; struct TreeNode* right; } TreeNode;
The "left" and "right" child nodes are denoted by left and right pointers, respectively, and each node in this structure is furnished with data. We may utilize this structure to build a tree by joining the nodes with the necessary pointers.
Source Code
#include<stdio.h> #include<stdlib.h> typedef struct TreeNode { int data; struct TreeNode* left; struct TreeNode* right; } TreeNode; // Function to create a new node TreeNode* createNode(int data){ TreeNode*newNode=(TreeNode*)malloc(sizeof(TreeNode)); newNode->data = data; newNode->left = NULL; newNode->right = NULL; return newNode; } // Function to insert a node into the tree TreeNode* insertNode(TreeNode* root, int data){ if (root==NULL) { root = createNode(data); } else if (data <= root->data) { root->left = insertNode(root->left, data); } else { root->right = insertNode(root->right, data); } return root; } // Function to find the minimum value in a tree TreeNode* findMin(TreeNode* root){ while (root->left != NULL) { root = root->left; } return root; } // Function to delete a node from the tree TreeNode* deleteNode(TreeNode* 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 or only one child if (root->left == NULL) { TreeNode* temp = root->right; free(root); return temp; } else if (root->right == NULL) { TreeNode* temp = root->left; free(root); return temp; } // Case 2: Two children TreeNode* temp = findMin(root->right); root->data = temp->data; root->right = deleteNode(root->right, temp->data); } return root; } // Function for inorder traversal (left-root-right) void inorderTraversal(TreeNode* root) { if (root == NULL) { return; } inorderTraversal(root->left); printf("%d ", root->data); inorderTraversal(root->right); } int main() { TreeNode* root = NULL; // Insert nodes into the tree root = insertNode(root, 50); root = insertNode(root, 30); root = insertNode(root, 20); root = insertNode(root, 40); root = insertNode(root, 70); root = insertNode(root, 60); root = insertNode(root, 80); printf("Inorder traversal of the tree: "); inorderTraversal(root); printf(" "); // Delete a node from the tree root = deleteNode(root, 20); printf("Inorder traversal after deleting 20: "); inorderTraversal(root); printf(" "); return 0; }
Output
Operations on Tree Data Structure
1.Insertion:
We must determine the suitable place depending on the node's value and keep the tree's attributes in order to add a new node to a tree. This entails moving around the tree and contrasting values until we locate a blank space for insertion. Then, to link it properly, we construct a new node and change the relevant pointers.
2.Deletion:
Removing a node from a tree data structure could be more challenging. We must consider many possibilities, including nodes with no children, nodes with 1 child, and nodes with 2 children. To delete the node while maintaining the tree's structure, we modify the pointers per the case.
3.Traversal:
The practice of visiting each node in the tree in a specified order is known as "tree traversal." The most often used traversal strategies are:
- Inorder traversal: Firstly, it visits the left subtree, followed by the node you are on now, and then it visits the right subtree.
- Preorder traversal: A visit to the current node is followed by trips to the left and right subtrees.
- postOrder traversal: Firstly, it visits the left subtree; after that, it returns the right subtree, then lastly present node.
Conclusion
Trees are a flexible and strong data structures that are used in many methods, including syntax trees, binary heaps, and search trees. Understanding tree ideas and how they are implemented in C is essential for any programmer. The fundamentals of trees, important terminology, C implementation, and typical operations have all been addressed in this tutorial. You will better handle issues effectively and use trees in your programs if you understand these ideas and practice using tree algorithms.