Trees and Graphs in C

Trees and graphs are non-linear data structures used to represent hierarchical and networked data.

In this lesson, you will learn:

• How trees and graphs are structured.
• How to implement a binary tree in C.
• How to represent graphs using adjacency lists and matrices.

What is a Tree?

A tree is a hierarchical data structure consisting of nodes.

Key terms:

• Root - The top node.
• Parent and Child - Nodes connected directly.
• Leaf - A node with no children.

Example: Binary Tree Node

In C, a binary tree node is defined using a struct with left and right child pointers.

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

struct Node {
    int data;
    struct Node *left, *right;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

int main() {
    struct Node *root = createNode(10);
    return 0;
}

Binary Tree Traversal

Traversal methods:

• Inorder (LNR) - Left, Node, Right.
• Preorder (NLR) - Node, Left, Right.
• Postorder (LRN) - Left, Right, Node.

Example: Inorder Traversal

This program performs an inorder traversal of a binary tree.

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

struct Node {
    int data;
    struct Node *left, *right;
};

void inorder(struct Node *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    struct Node *root = malloc(sizeof(struct Node));
    root->data = 10;
    root->left = NULL;
    root->right = NULL;
    inorder(root);
    return 0;
}

What is a Graph?

A graph is a collection of nodes (vertices) connected by edges.

Graphs can be:

• Directed - Edges have direction.
• Undirected - Edges have no direction.

Graph Representation

Graphs can be represented using:

• Adjacency Matrix - A 2D array representing connections.
• Adjacency List - A list where each node points to its neighbors.

Graph Traversal

Common traversal methods:

• Breadth-First Search (BFS) - Visits all neighbors before moving deeper.
• Depth-First Search (DFS) - Explores as deep as possible before backtracking.

Summary

In this lesson, you learned:

• How trees and graphs are structured.
• How to perform tree traversals.
• How graphs are represented and traversed.

This concludes the Data Structures in C section!