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:

Root node is stored at index 0.
Left child of a node at index i is stored at 2*i + 1.
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

#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) {
    // Check if the index is out of bounds
    if (index >= MAX_SIZE) {
        printf("Index out of bounds!\n");
        return;
    }

    // Check if the node at the given index is already occupied
    if (tree[index] != -1) {
        printf("Node already occupied at index %d\n", index);
        return;
    }

    // Insert the value at the specified index
    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("_ "); // Print underscore for empty nodes
        } else {
            printf("%d ", tree[i]); // Print the value of the node
        }
    }
    printf("\n");
}

int main() {
    // Initialize the tree with empty nodes
    initializeTree();

    // Insert nodes into the binary tree
    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 the binary tree
    displayTree();

    return 0; // End of program
}

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 &