Nonlinear Data Structures

Tree Structures

Trees represent hierarchical data relationships. Binary trees contain nodes with up to two children, while multi-way trees can have more. The topmost node is called the root.

A binary tree node typically contains:

struct BinaryNode {
    int data;
    BinaryNode* leftChild;
    BinaryNode* rightChild;
    BinaryNode(int value) : data(value), leftChild(nullptr), rightChild(nullptr) {}
};

Constructing a binary tree involves creating nodes and establishing connections:

BinaryNode* root = new BinaryNode(10);
BinaryNode* nodeA = new BinaryNode(20);
BinaryNode* nodeB = new BinaryNode(30);
BinaryNode* nodeC = new BinaryNode(40);
BinaryNode* nodeD = new BinaryNode(50);

root->leftChild = nodeA;
root->rightChild = nodeB;
nodeA->leftChild = nodeC;
nodeA->rightChild = nodeD;

Graph Representations

Graphs consist of vertices connected by edges. Undirected graphs have bidirectional connections, while directed graphs have one-way connections.

An undirected graph with vertices {1, 2, 3, 4, 5} and edges {(1,2), (1,3), (1,4), (1,5), (2,4), (3,5), (4,5)} can be represented using an adjacency matrix:

int graphMatrix[5][5] = {
    {0, 1, 1, 1, 1},
    {1, 0, 0, 1, 0},
    {1, 0, 0, 0, 1},
    {1, 1, 0, 0, 1},
    {1, 0, 1, 1, 0}
};

Atlernatively, using adjacency lists:

vector<vector<int>> adjList(5);
adjList[0] = {1, 2, 3, 4};  // Vertex 1 connections
adjList[1] = {0, 3};        // Vertex 2 connections
adjList[2] = {0, 4};        // Vertex 3 connections
adjList[3] = {0, 1, 4};     // Vertex 4 connections
adjList[4] = {0, 2, 3};     // Vertex 5 connections

Hash Table Implementation

Hash tables provide efficient key-value storage using hash functions. Consider mapping student names to IDs:

unordered_map<string, int> studentMap;
studentMap["Alice"] = 101;
studentMap["Bob"] = 102;
studentMap["Charlie"] = 103;

int aliceId = studentMap["Alice"];  // Returns 101

Custom hash function example for ID to name mappping:

string studentNames[] = {"Alice", "Bob", "Charlie"};

int customHash(int studentId) {
    return (studentId - 101) % 1000;
}

string getName(int id) {
    return studentNames[customHash(id)];
}

Heap Data Structure

Heaps are complete binary trees implemented as arrays. Min-heaps ensure parent nodes are smaller than children, while max-heaps ensure they're larger.

Complete binary tree definition: All levels except possibly the last are completely filled, and nodes are left-aligned.

Priority queue implementation for min-heap operations:

priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(5);
minHeap.push(2);
minHeap.push(8);
minHeap.push(1);
minHeap.push(4);

// Elements will be retrieved in ascending order
while (!minHeap.empty()) {
    int minVal = minHeap.top();
    minHeap.pop();
}