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
#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 &