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
