C Program To Draw A Tree

A tree represents a nonlinear hierarchical arrangement of nodes and edges. Positioned at the top is a root node, while leaf nodes are situated at the lower levels. Each node may have zero or more child nodes beneath it. By establishing connections from nodes to their parent nodes, a parent-child relationship is formed, and data items are stored within the nodes. Trees serve as effective tools for representing various data structures such as computer directories, database indexes, decision trees, parsers, and ordered lists that can be easily accessed. The height of a tree is determined by the total number of edges on the longest path from the root to a leaf. Trees offer adaptability and flexibility, allowing for swift operations like adding, removing, searching, and sorting data.

Key Terminologies of Trees

There are various terms related to Trees. Some key terminologies of trees include:

Nodes - Nodes serve as the fundamental components of a tree data structure. Every node holds information and references to its child nodes.

The root node represents the primary node located at the tree hierarchy's top. It serves as the foundational node for the entire tree structure.

Nodes within a hierarchy are linked vertically through parent-child relationships, with each node potentially pointing to lower-level child nodes.

A leaf in a tree structure represents a node without any children, serving as the endpoint at the bottom level of the hierarchy.

A subtree refers to a segment of a tree consisting of a node and all of its offspring.

Height - Height is a metric that signifies the maximum depth by measuring the count of edges from the root to the lowest leaf node.

Depth - Depth is the distance of a node from the root measured in edges. Root has depth 0 .

Level - Level represents depth plus 1. The root is at level 1.

Degree - Degree is the number of subtrees/children of a node. Leaves have a degree of 0.

Binary Trees - Binary trees limit nodes to a maximum of 2 children, making this arrangement widely utilized in programming.

Binary Search Trees (BSTs) organize their left and right subtrees in a way that the values on the left side are less than or equal to the node, while the values on the right side are greater, enabling quick and effective search operations.

Balanced Tree - Balanced trees are designed to maintain uniform heights among subtrees, facilitating optimal performance for various operations.

Complete Binary Tree - Complete binary trees necessitate every node to have either 0 or 2 children, but not 1.

Complete Tree - A complete tree is characterized by filling all levels with nodes, except for the last level, and aligning nodes to the left.

A woodland comprises numerous individual trees.

Traversing a tree involves systematically visiting all nodes, commonly done recursively.

Key Properties of Trees

There are several properties of Trees. Some main properties of tree are as follows:

• ✅ Hierarchical - A tree models hierarchical relationships between elements. Each element can have an arbitrary number of subordinate elements below it in a parent-child relationship.
• ✅ Recursive - Trees are defined recursively where each node is itself a tree consisting of its descendants. Algorithms on trees are often defined recursively.
• ✅ Rooted - Trees have a single root node at the top and grow downwards from it. The root node has no parents, and all other nodes ultimately link back to the root.
• ✅ Labeled - Each node has a value associated with it, which is called its label or data element . Trees store data in their nodes.
• ✅ Connected - All nodes are connected by edges from parent to child. Each node (except the root) has one incoming edge from its parent node.
• ✅ Unordered - Nodes at each level are not ordered in any particular manner. The children of a node have no specific order.
• ✅ Acyclic - Trees cannot have cycles. The edges have a specific direction from parent to child nodes, ruling out cycles.
• ✅ Dynamic size - Trees can grow and shrink in size as nodes are added or removed. There is no fixed size for a tree.
• ✅ Varying degree - Nodes can have any number of children or subtree sizes. Some nodes may have no children, while others have many.

Example:

Let's consider an illustration to showcase the process of constructing a tree in the C programming language.

#include <stdio.h>

#include <stdlib.h>



// Define the structure of a binary tree node

struct TreeNode {

 int data;

 struct TreeNode* left;

 struct TreeNode* right;

};



// Function to create a new tree node

struct TreeNode* createNode(int data) {

 struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));

 newNode->data = data;

 newNode->left = newNode->right = NULL;

 return newNode;

}



// Function to perform an in-order traversal of the tree

void inOrderTraversal(struct TreeNode* root) {

 if (root == NULL) {

 return;

 }

 inOrderTraversal(root->left);

 printf("%d ", root->data);

 inOrderTraversal(root->right);

}



int main() {

 // Create a simple binary tree

 struct TreeNode* root = createNode(1);

 root->left = createNode(2);

 root->right = createNode(3);

 root->left->left = createNode(4);

 root->left->right = createNode(5);



 // Print the tree using in-order traversal

 printf("Binary Tree (In-order traversal): ");

 inOrderTraversal(root);

 printf("\n");



 // Clean up memory (free allocated nodes)

 // In practice, this should be done when you're done with the tree

 free(root->left->left);

 free(root->left->right);

 free(root->left);

 free(root->right);

 free(root);



 return 0;

}

Output:

Binary Tree (In-order traversal): 4 2 5 1 3

Explanation of importanLogic Practices:

• ✅ In this example, include h and stdlib.h header files for standard input/output and memory allocation functions.
• ✅ Define a TreeNode structure to represent each node in the binary tree. It contains an integer data value and pointers to left and right child nodes.
• ✅ Create a createNode function to allocate memory for and initialize a new TreeNode . It sets the data value and child pointers to null.
• ✅ Define an inOrderTraversal function to print the tree nodes in an in-order sequence (left subtree, root, right subtree). It traverses recursively if the root is not null.
• ✅ In main function, first create the root node with data 1.
• ✅ Add left and right child nodes to the root with data 2 and 3.
• ✅ Add further left and right child nodes to node 2 with data 4 and 5.
• ✅ Print the tree by calling inOrderTraversal , passing the root node. It will print the node values in sorted order.
• ✅ Free the memory allocated for each TreeNode by traversing from the leaves up to the root.
• ✅ Return 0 to indicate successful program execution.

Types of Trees:

There are several types of the Tree. Some important types of the tree are as follows:

• ✅ Binary Tree - Each node has up to two child nodes referred to as left and right child. Binary trees are commonly used in binary search trees and heaps.
• ✅ Binary Search Tree (BST) - A binary tree where the nodes are organized in order - the left subtree nodes are less than the parent, and the right subtree nodes are greater than the parent. Provides fast lookup, insertion and deletion.
• ✅ AVL Tree - Self balancing binary search tree where the difference between the height of left and right subtrees of any node is not more than 1. Avoids skew and provides O(log n) lookup time.
• ✅ Red-Black Tree - A self balancing BST where nodes have an extra color bit to ensure tree remains approximately balanced during insertions and deletions.
• ✅ B-Tree - Tree where each node can have more than 2 children, up to some pre-defined order. Used in databases and file systems to enable efficient search and sequential access.
• ✅ Heap - A specialized tree structure where parent nodes are ordered with respect to child nodes. Two common types are max-heap and min-heap, with the largest and smallest values at the root. Used to implement priority queues.
• ✅ Trie - Tree where nodes store associative arrays indexed by characters. Enables efficient lookup and insertion of strings. Used in dictionaries, databases and spell checkers.
• ✅ Suffix Tree - Specialized trie where suffixes of a given string are stored at the edges of the tree. Allows fast substring queries.

Tree Traversal:

1. Inorder Traversal

During this traversal process, the initial focus is on exploring the left subtree before moving on to the root node, and subsequently examining the right subtree. This method proves effective for obtaining nodes in an organized sequence within binary search trees.

Pseudocode:

traverse(root): if root == null: return

traverse(root.left) visit(root) traverse(root.right)

2. Preorder Traversal

Here, the initial node is explored initially, followed by the left sub-tree, and eventually the right sub-tree. Making a duplicate of the tree can be beneficial.

Pseudocode:

traverse(root): if root == null: return

visit(root) traverse(root.left) traverse(root.right)

3. Postorder Traversal

During this traversal, the process starts by visiting the left subtree, followed by the right subtree, and concluding with the root node. This method is commonly employed for tasks such as tree deletion or executing various clean-up procedures.

Pseudocode:

traverse(root): if root == null: return

traverse(root.left) traverse(root.right) visit(root)

These three tree traversals enable a systematic exploration of all nodes within a tree, each following a distinct order. They serve as the foundation for numerous standard tree manipulations.

Tree Applications:

There are various uses of Tree data structure. Several key applications of trees include:

Binary Search Trees (BSTs): They are valuable for performing quick searches, additions, and removals of information, which makes them perfect for constructing dictionaries and symbol tables.

Expression Trees: They are utilized to represent mathematical expressions, enabling effective evaluation and streamlining.

A unique form of binary tree commonly employed in priority queue implementations, like binary heaps and Fibonacci heaps.

File Systems: Trees are employed to illustrate directory arrangements in file systems. Every directory has the potential to encompass files or subdirectories, constructing a hierarchical layout.

Hierarchical Data Representation: Trees are employed to depict structured data, like organizational charts, genealogical trees, and XML/JSON data formats.

Artificial Intelligence: Trees play a crucial role in decision tree algorithms when it comes to performing classification and regression tasks.