Non-Linear Data Structure: Definition, its Types with Examples

A non-linear data structure is a type of data structure where data elements are not stored in a sequence. These structures allow for more complex relationships between data elements, and the elements can have multiple links or branches to other elements. This makes them ideal for representing real-world structures that are hierarchical, or network based.

There are two types of Non-linear data structures:

1. Tree

A tree is a hierarchical data structure where each element (called a node) is connected to one or more nodes in a parent-child relationship. Trees are often used to represent hierarchical structures, such as file systems or organizational charts.

2. Graph

A graph is a collection of nodes (vertices) and edges, where edges connect the nodes. Graphs are more general and flexible than trees and can represent complex relationships, such as social networks, transportation systems, or web pages.

A tree is a non-linear data structure that models hierarchical relationships using nodes and edges. A tree consists of a root node, which serves as the entry point, and child nodes that branch off from the root and other nodes. A tree’s structure allows for the efficient representation and traversal of hierarchical data.

Types of Trees in Data Structure

The types of trees in the data structure include:

• Simple Tree: A hierarchical data structure with a single root and nodes, where each node can have any number of children but no cycles.
• Binary Tree: A tree where each node has at most two children, referred to as the left and right children.
• Binary Search Tree (BST): A binary tree in which the left child is smaller, and the right child is larger than the parent, with this property recursively holding for all nodes.
• AVL Tree: A self-balancing binary search tree where the difference between the heights of the left and right subtrees (balance factor) is at most 1 for every node.
• B-Tree: A self-balancing tree data structure that maintains sorted data and allows for efficient insertion, deletion, and search operations. Nodes can have more than two children.‍
• B+ Tree: A variation of the B-tree where all values are stored in the leaf nodes and internal nodes only store keys to guide searching. It is often used in databases.

Terminology Used in Trees

• Node: An individual element in a tree.
• Root: The topmost node in a tree.‍
• Leaf: A node without any children.‍
• Subtree: A tree formed by descendants of a node.‍
• Parent: A node that has child nodes.‍
• Child: A node that descends from another node.‍
• Siblings: The nodes have the same parent node.

A graph is a non-linear data structure consisting of nodes (or vertices) and edges that connect pairs of nodes. Graphs are widely used to represent networks, such as social networks, communication networks, or road systems.

Types of Graphs in Data Structure

The types of graphs in the data structure include:

• Directed Graph (Digraph): In a directed graph, the edges have a direction, meaning each edge has a starting and an ending node.
• Undirected Graph: In an undirected graph, the edges do not have a direction; the connection between the nodes is bidirectional.
• Weighted Graph: In a weighted graph, each edge has a weight or cost associated with it, typically used to represent distances or costs between nodes.‍
• Unweighted Graph: In an unweighted graph, all edges are equal, with no specific weight assigned.

Terminology Used in Graphs

• Vertex (Node): A fundamental unit in a graph representing a point or position.
• Edge: A connection between two vertices.
• Adjacent: Two vertices are adjacent if there is an edge between them.
• Path: A sequence of edges connecting two vertices.
• Cycle: A path that starts and ends at the same vertex.

Here is the comparison between linear and non-linear data structures:

Here is the binary tree implementation of non-linear data structures in C and C++:

C program:

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

// Define a node structure
struct Node {
    int value;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->value = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Function to insert a node in the binary tree
struct Node* insert(struct Node* root, int value) {
    if (root == NULL) {
        return createNode(value);  // Insert a new node if the current root is NULL
    }
    if (value < root->value) {
        root->left = insert(root->left, value);  // Insert in the left subtree
    } else {
        root->right = insert(root->right, value);  // Insert in the right subtree
    }
    return root;
}

// In-order traversal (left, root, right)
void inorderTraversal(struct Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);  // Traverse left subtree
        printf("%d ", root->value);  // Visit the node
        inorderTraversal(root->right);  // Traverse right subtree
    }
}

// Pre-order traversal (root, left, right)
void preorderTraversal(struct Node* root) {
    if (root != NULL) {
        printf("%d ", root->value);  // Visit the node
        preorderTraversal(root->left);  // Traverse left subtree
        preorderTraversal(root->right);  // Traverse right subtree
    }
}

// Post-order traversal (left, right, root)
void postorderTraversal(struct Node* root) {
    if (root != NULL) {
        postorderTraversal(root->left);  // Traverse left subtree
        postorderTraversal(root->right);  // Traverse right subtree
        printf("%d ", root->value);  // Visit the node
    }
}
int main() {
    struct Node* root = NULL;

    // Inserting nodes into the binary tree
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    // Traversal
    printf("In-order Traversal: ");
    inorderTraversal(root);
    printf("\n");

    printf("Pre-order Traversal: ");
    preorderTraversal(root);
    printf("\n");

    printf("Post-order Traversal: ");
    postorderTraversal(root);
    printf("\n");

    return 0;
   }

C++ program

#include <iostream>
using namespace std;

// Define a node structure
class Node {
public:
    int value;
    Node* left;
    Node* right;

    Node(int val) {
        value = val;
        left = right = nullptr;
    }
};

// BinaryTree class contains methods for tree operations
class BinaryTree {
public:
    Node* root;

    BinaryTree(int rootValue) {
        root = new Node(rootValue);  // Initialize the tree with the root node
    }

    // Insert a new node with the given value
    void insert(Node* currentNode, int value) {
        if (value < currentNode->value) {
            if (currentNode->left == nullptr) {
                currentNode->left = new Node(value);
            } else {
                insert(currentNode->left, value);
            }
        } else if (value > currentNode->value) {
            if (currentNode->right == nullptr) {
                currentNode->right = new Node(value);
            } else {
                insert(currentNode->right, value);
            }
        }
    }

    // In-order traversal (left, root, right)
    void inorderTraversal(Node* node) {
        if (node != nullptr) {
            inorderTraversal(node->left);
            cout << node->value << " ";
            inorderTraversal(node->right);
        }
    }

    // Pre-order traversal (root, left, right)
    void preorderTraversal(Node* node) {
        if (node != nullptr) {
            cout << node->value << " ";
            preorderTraversal(node->left);
            preorderTraversal(node->right);
        }
    }

    // Post-order traversal (left, right, root)
    void postorderTraversal(Node* node) {
        if (node != nullptr) {
            postorderTraversal(node->left);
            postorderTraversal(node->right);
            cout << node->value << " ";
        }
    }
};

int main() {
    BinaryTree tree(50);  // Create a tree with root node 50

    // Inserting nodes into the binary tree
    tree.insert(tree.root, 30);
    tree.insert(tree.root, 20);
    tree.insert(tree.root, 40);
    tree.insert(tree.root, 70);
    tree.insert(tree.root, 60);
    tree.insert(tree.root, 80);

    // Traversals
    cout << "In-order Traversal: ";
    tree.inorderTraversal(tree.root);
    cout << endl;

    cout << "Pre-order Traversal: ";
    tree.preorderTraversal(tree.root);
    cout << endl;

    cout << "Post-order Traversal: ";
    tree.postorderTraversal(tree.root);
    cout << endl;

    return 0;
}

Here is the adjacency graph implementation of non-linear data structures in C and C++:

C program

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

#define MAX_VERTICES 10  // Maximum number of vertices

// Structure to represent a graph
struct Graph {
    int matrix[MAX_VERTICES][MAX_VERTICES];
    int vertices;  // Number of vertices
};

// Initialize the graph
void initGraph(struct Graph *g, int vertices) {
    g->vertices = vertices;
    
    // Initialize the adjacency matrix to 0
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            g->matrix[i][j] = 0;
        }
    }
}
// Add an edge to the graph
void addEdge(struct Graph *g, int start, int end) {
    if (start < g->vertices && end < g->vertices) {
        g->matrix[start][end] = 1;
        g->matrix[end][start] = 1;  // For undirected graph
    }
}
// Print the adjacency matrix
void printGraph(struct Graph *g) {
    for (int i = 0; i < g->vertices; i++) {
        for (int j = 0; j < g->vertices; j++) {
            printf("%d ", g->matrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    struct Graph g;
    initGraph(&g, 5);  // Initialize graph with 5 vertices

    // Add edges to the graph
    addEdge(&g, 0, 1);
    addEdge(&g, 0, 4);
    addEdge(&g, 1, 2);
    addEdge(&g, 1, 3);
    addEdge(&g, 3, 4);

    // Print the graph's adjacency matrix
    printf("Adjacency Matrix of the Graph:\n");
    printGraph(&g);
    
    return 0;
}

C++ program

#include <iostream>
#include <vector>
using namespace std;

class Graph {
public:
    vector<vector<int>> adjMatrix;
    int vertices;

    Graph(int v) {
    vertices = v;
        adjMatrix.resize(vertices, vector<int>(vertices, 0));  // Initialize matrix with 0s
    }

    // Add an edge
    void addEdge(int start, int end) {
        adjMatrix[start][end] = 1;
        adjMatrix[end][start] = 1;  // For undirected graph
    }

    // Print the adjacency matrix
    void printGraph() {
        for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++) {
                cout << adjMatrix[i][j] << " ";
            }
            cout << endl;
        }
    }
};
int main() {
    Graph g(5);  // Create a graph with 5 vertices

    // Add edges
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(3, 4);

    // Print the adjacency matrix
    cout << "Adjacency Matrix of the Graph:" << endl;
    g.printGraph();

    return 0;
}

Here are the advantages of using non-linear data structures:

• Non-linear data structures, such as trees, offer faster search times compared to linear data structures, especially in large datasets.
• Trees are ideal for representing hierarchical data, such as organizational charts or file systems.
• Graphs can represent more complex relationships, such as social networks or transportation systems.

Here are the disadvantages of using non-linear data structures:

• Non-linear data structures are more complex to implement and manage than linear data structures.
• Graphs and trees can consume more memory due to the need for storing multiple relationships between elements.
• Traversing non-linear data structures, particularly graphs, can be challenging and often requires specialized algorithms.

In conclusion, non-linear data structures are essential for solving complex problems that involve relationships between elements that are not linear. Whether it’s trees for hierarchical data or graphs for interconnected data, these structures provide efficient ways to model, manipulate, and search data. Despite their complexity, they are invaluable in many advanced algorithms and applications, ranging from databases and file systems to networks and artificial intelligence.

1. What is the main difference between linear and non-linear data structures?

Linear data structures store elements sequentially, while non-linear data structures store elements in a hierarchical or interconnected manner.

2. Why are trees considered non-linear data structures?

Trees have a hierarchical structure where nodes can have multiple child nodes, making the relationship between elements more complex than a linear sequence.

3. Can non-linear data structures be used for graph traversal?

Yes, graph traversal algorithms like Depth First Search (DFS) and Breadth First Search (BFS) are used to traverse non-linear data structures like graphs.