Array Implementation

Array Implementation in Binary Tree

Implementing a binary tree using arrays involves representing the tree structure in a linear array. This representation simplifies access to nodes and is particularly useful for complete binary trees, where all levels of the tree are fully filled except possibly for the last level, which is filled from left to right.

In this representation:

• For any node at index i:
  • Its left child is located at index 2i+1.
  • Its right child is located at index 2i+2.

Here’s a simple example of implementing a binary tree using arrays in C:

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

#define MAX_SIZE 100

// Define a structure for the binary tree
struct BinaryTree {
    int data[MAX_SIZE];
    int size;
};

// Function to initialize the binary tree
void initBinaryTree(struct BinaryTree* tree) {
    tree->size = 0;
}

// Function to insert a new element into the binary tree
void insert(struct BinaryTree* tree, int value) {
    if (tree->size < MAX_SIZE) {
        tree->data[tree->size] = value;
        tree->size++;
    } else {
        printf("Binary tree is full!\n");
    }
}

// Function to print the binary tree
void printTree(struct BinaryTree* tree) {
    printf("Binary Tree: ");
    for (int i = 0; i < tree->size; i++) {
        printf("%d ", tree->data[i]);
    }
    printf("\n");
}

// Main function
int main() {
    struct BinaryTree tree;
    initBinaryTree(&tree);

    insert(&tree, 1);
    insert(&tree, 2);
    insert(&tree, 3);
    insert(&tree, 4);
    insert(&tree, 5);

    printTree(&tree);

    return 0;
}

Output:

Binary Tree: 1 2 3 4 5

Code Explanation

Step 1: Define the Structure for the Binary Tree

#define MAX_SIZE 100  // Maximum size of the tree

// Define a structure for the binary tree
struct BinaryTree {
    int data[MAX_SIZE];  // Array to store tree elements
    int size;            // Number of elements in the tree
};

Explanation:

• The binary tree is represented using an array instead of pointers.
• The data[MAX_SIZE] array holds the tree elements.
• size keeps track of the number of elements in the tree.

Step 2: Initialize the Binary Tree

// Function to initialize the binary tree
void initBinaryTree(struct BinaryTree* tree) {
    tree->size = 0;  // Set size to zero (empty tree)
}

Explanation:

• This function initializes the tree by setting size = 0, indicating an empty tree.

Step 3: Insert Elements into the Tree

// Function to insert a new element into the binary tree
void insert(struct BinaryTree* tree, int value) {
    if (tree->size < MAX_SIZE) {  // Check if tree is full
        tree->data[tree->size] = value;  // Insert element at the next available index
        tree->size++;  // Increase size count
    } else {
        printf("Binary tree is full!\n");
    }
}

Explanation:

• The function adds elements sequentially in level order (BFS manner).
• Each new element is added at the next available index.
• The size is increased after each insertion.
• If the array reaches its maximum capacity (MAX_SIZE), it displays “Binary tree is full!”.

Step 4: Print the Binary Tree

// Function to print the binary tree
void printTree(struct BinaryTree* tree) {
    printf("Binary Tree: ");
    for (int i = 0; i < tree->size; i++) {  // Loop through the tree elements
        printf("%d ", tree->data[i]);
    }
    printf("\n");
}

Explanation:

• This function prints all elements in level order (BFS manner).

Step 5: Main Function

int main() {
    struct BinaryTree tree;   // Declare binary tree
    initBinaryTree(&tree);    // Initialize the tree
 
    insert(&tree, 1);
    insert(&tree, 2);
    insert(&tree, 3);
    insert(&tree, 4);
    insert(&tree, 5);
 
    printTree(&tree);  // Print the tree elements
 
    return 0;
}

Explanation:

• Creates a binary tree.
• Inserts values 1, 2, 3, 4, 5.
• Calls printTree() to display the binary tree.