Static Representation of Binary Tree

A binary tree can be represented using an array when the number of nodes is fixed (static). Instead of using pointers like in a dynamic tree, we store tree elements in sequential indices of an array.

Indexing Rules : 

For a 0-based index array representation:

  1. Root node is stored at index 0.
  2. Left child of a node at index i is stored at 2*i + 1.
  3. Right child of a node at index i is stored at 2*i + 2.

If a node is missing, we store a placeholder value (e.g., -1 or _).

Static Representation of Binary Tree Using Array

#include <stdio.h>

#define MAX_SIZE 15  // Maximum size of the binary tree array

int tree[MAX_SIZE];  // Array to store the binary tree

// Function to initialize the tree with -1 (indicating empty nodes)

void initializeTree() {

    for (int i = 0; i < MAX_SIZE; i++) {

        tree[i] = -1;  // -1 represents an empty node

    }

}

// Function to insert a value at a given index

void insertNode(int value, int index) {

    if (index >= MAX_SIZE) {

        printf(“Index out of bounds!\n”);

        return;

    }

    if (tree[index] != -1) {

        printf(“Node already occupied at index %d\n”, index);

        return;

    }

    tree[index] = value;

}

// Function to display the binary tree as an array

void displayTree() {

    printf(“Binary Tree (Array Representation):\n”);

    for (int i = 0; i < MAX_SIZE; i++) {

        if (tree[i] == -1)

            printf(“_ “);  // Empty node

        else

            printf(“%d “, tree[i]);

    }

    printf(“\n”);

}

int main() {

    initializeTree();

    // Insert nodes

    insertNode(1, 0);  // Root node

    insertNode(2, 1);  // Left child of root

    insertNode(3, 2);  // Right child of root

    insertNode(4, 3);  // Left child of node at index 1

    insertNode(5, 4);  // Right child of node at index 1

    insertNode(6, 5);  // Left child of node at index 2

    insertNode(7, 6);  // Right child of node at index 2

    // Display tree

    displayTree();

    return 0;

}

Instructions to edit and run the Progam ( On Ubuntu)

Step 1: Open Terminal

Press Ctrl + Alt + T to open the terminal.

Step 2: Create a C File Using gedit

In the terminal, type:

gedit binary_tree.c &

  • This will open gedit, a GUI text editor.

The & at the end allows you to continue using the terminal while gedit is open.

Step 3: Type your Program

Step 4: Save & Close gedit

  • Click Save or press Ctrl + S.
  • Close gedit.

Step 5: Compile the C Program

Go back to the terminal and run:

gcc binary_tree.c -o binary_tree

This compiles the program and creates an executable file named binary_tree.

Step 6: Run the Executable

Execute the program by running:

./binary_tree

Note :

  • If GCC is not installed, install it using:

sudo apt update

sudo apt install gcc

  • If you want to edit the file later, use:

gedit binary_tree.c &