Concept of Trees Using C

A tree is a fundamental data structure that is widely used in computer science and programming. It is a non-linear and hierarchical structure where elements, called nodes, are arranged at different levels. Trees are highly versatile and are often used for organizing data, enabling efficient searching and retrieval, and representing hierarchical information.

What is a Tree Data Structure?

In a tree data structure:

• Root Node: The topmost node in the tree, which serves as the starting point.
• Node: Each element of the tree, containing data and references to its children.
• Parent and Child Nodes: A parent node is directly connected to its child nodes.
• Leaf Nodes: Nodes without children, located at the bottom of the tree.
• Subtree: A section of a tree that includes a node and all its descendants.
• Depth: The distance from the root node to a particular node.
• Height: The distance from a node to the deepest leaf.

Characteristics of Trees

• Trees follow a hierarchical structure, making them suitable for representing relationships.
• They allow efficient traversal and manipulation of data.
• Nodes in a tree can have zero or more child nodes.

Implementation of Trees in C

Below is an example of how to implement a tree data structure in C:

#include<stdio.h>
#include<stdlib.h>

struct tree {
    int no, level;
    struct tree *left, *right;
};

struct tree *root = NULL;
int dpt;

// Search function
struct tree* search(int val, int *found) {
    struct tree *p = root, *par = NULL;
    while (p != NULL) {
        if (val == p->no) {
            *found = 1;
            return par;
        } else if (val > p->no) {
            par = p;
            p = p->right;
        } else {
            par = p;
            p = p->left;
        }
    }
    return par;
}

// Insert function
void insert(int val) {
    struct tree *parent, *n;
    int f = 0;
    n = (struct tree *)malloc(sizeof(struct tree));
    n->no = val;
    n->left = n->right = NULL;
    if (root == NULL) {
        root = n;
        root->level = 0;
        return;
    }
    parent = search(val, &f);
    if (f == 1) {
        printf("\nDuplicate Number");
        free(n);
        return;
    }
    n->level = parent->level + 1;
    if (val > parent->no)
        parent->right = n;
    else
        parent->left = n;
}

// Preorder traversal
void preorder(struct tree *p) {
    if (p != NULL) {
        printf("%d ", p->no);
        preorder(p->left);
        preorder(p->right);
    }
}

// Inorder traversal
void inorder(struct tree *p) {
    if (p != NULL) {
        inorder(p->left);
        printf("%d ", p->no);
        inorder(p->right);
    }
}

// Postorder traversal
void postorder(struct tree *p) {
    if (p != NULL) {
        postorder(p->left);
        postorder(p->right);
        printf("%d ", p->no);
    }
}

// Display all leaf nodes
void disleafnode(struct tree *p) {
    if (p != NULL) {
        if (p->left == NULL && p->right == NULL)
            printf("%d ", p->no);
        disleafnode(p->left);
        disleafnode(p->right);
    }
}

// Find depth of tree
void depth(struct tree *p) {
    if (p != NULL) {
        if (p->level > dpt)
            dpt = p->level;
        depth(p->left);
        depth(p->right);
    }
}

// Main function
void main() {
    int ch, n;
    do {
        printf("\n1. Insert Node");
        printf("\n2. Preorder");
        printf("\n3. Inorder");
        printf("\n4. Postorder");
        printf("\n5. Display All Leaf Nodes");
        printf("\n6. Depth of Tree");
        printf("\n0. Exit");
        printf("\n\nEnter Your Choice: ");
        scanf("%d", &ch);
        switch (ch) {
            case 1:
                printf("\nEnter Number: ");
                scanf("%d", &n);
                insert(n);
                break;
            case 2:
                preorder(root);
                break;
            case 3:
                inorder(root);
                break;
            case 4:
                postorder(root);
                break;
            case 5:
                disleafnode(root);
                break;
            case 6:
                dpt = 0;
                depth(root);
                printf("\nDepth of Tree: %d", dpt);
                break;
            case 0:
                break;
            default:
                printf("\nWrong Choice. Try Again.");
        }
    } while (ch != 0);
}

Key Terms in Tree Data Structure

1. Node: Fundamental building block of a tree containing data and references.
2. Root: The starting node of the tree with no parent.
3. Leaf Node: Nodes without children.
4. Subtree: A portion of the tree containing a node and its descendants.
5. Depth: Distance from the root to a node.
6. Height: Longest path from a node to a leaf.

Applications of Trees

• Representing hierarchical data (e.g., organizational charts, file systems).
• Efficient searching and sorting (binary search trees, AVL trees).
• Data compression algorithms (Huffman coding).
• Network routing algorithms.
• Implementation of data structures like heaps and tries.

Conclusion

Trees are a powerful and versatile data structure essential in many computer science applications. The hierarchical nature of trees makes them ideal for solving problems that require hierarchical organization, efficient searching, and dynamic data manipulation. Understanding the fundamental concepts and implementation of trees in C can help developers build robust and efficient solutions for a variety of applications.