A Complete Binary Tree is a binary tree where all levels are fully filled except possibly the last level, and all nodes in the last level are as left as possible.
Characteristics of a Complete Binary Tree
- All levels filled: Except for the last level, every level has the maximum number of nodes.
- Nodes packed to the left: In the last level, nodes are inserted from left to right without gaps.
For example:
markdown
Copy code
1
/ \
2 3
/ \ /
4 5 6
This is a complete binary tree because the last level is filled from left to right.
Representation of Complete Binary Tree in C
The most common way to represent a Complete Binary Tree is:
- Array Representation: Using an array where:
- The root is at index 0.
- The left child of a node at index i is at index 2*i + 1.
- The right child of a node at index i is at index 2*i + 2.
- Pointer-Based Representation: Using a linked structure similar to other binary trees.
Operations on Complete Binary Tree
1. Array Representation
Structure
c
Copy code
#define MAX_SIZE 100
struct CompleteBinaryTree {
int nodes[MAX_SIZE];
int size; // Number of nodes in the tree
};
Insertion in Complete Binary Tree
c
Copy code
void insert(struct CompleteBinaryTree* tree, int value) {
if (tree->size >= MAX_SIZE) {
printf(“Tree is full.\n”);
return;
}
tree->nodes[tree->size] = value; // Insert at the next available position
tree->size++;
}
Level Order Traversal
c
Copy code
void levelOrderTraversal(struct CompleteBinaryTree* tree) {
for (int i = 0; i < tree->size; i++) {
printf(“%d “, tree->nodes[i]);
}
printf(“\n”);
}
Example Program for Array-Based Representation
c
Copy code
#include <stdio.h>
#define MAX_SIZE 100
struct CompleteBinaryTree {
int nodes[MAX_SIZE];
int size;
};
void insert(struct CompleteBinaryTree* tree, int value) {
if (tree->size >= MAX_SIZE) {
printf(“Tree is full.\n”);
return;
}
tree->nodes[tree->size] = value;
tree->size++;
}
void levelOrderTraversal(struct CompleteBinaryTree* tree) {
for (int i = 0; i < tree->size; i++) {
printf(“%d “, tree->nodes[i]);
}
printf(“\n”);
}
int main() {
struct CompleteBinaryTree tree = {{0}, 0};
insert(&tree, 1);
insert(&tree, 2);
insert(&tree, 3);
insert(&tree, 4);
insert(&tree, 5);
insert(&tree, 6);
printf(“Level Order Traversal:\n”);
levelOrderTraversal(&tree);
return 0;
}
Output
mathematica
Copy code
Level Order Traversal:
1 2 3 4 5 6
2. Pointer-Based Representation
Structure
c
Copy code
struct Node {
int data;
struct Node* left;
struct Node* right;
};
In a pointer-based implementation, a complete binary tree can be constructed dynamically using a queue for level order insertion.
Dynamic Insertion Using Queue
c
Copy code
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Queue structure for level-order insertion
struct Queue {
struct Node* arr[100];
int front, rear;
};
// Function prototypes
struct Node* createNode(int value);
void insert(struct Node** root, struct Queue* q, int value);
void levelOrderTraversal(struct Node* root);
void enqueue(struct Queue* q, struct Node* node);
struct Node* dequeue(struct Queue* q);
int main() {
struct Node* root = NULL;
struct Queue q = {{NULL}, 0, 0};
insert(&root, &q, 1);
insert(&root, &q, 2);
insert(&root, &q, 3);
insert(&root, &q, 4);
insert(&root, &q, 5);
insert(&root, &q, 6);
printf(“Level Order Traversal:\n”);
levelOrderTraversal(root);
return 0;
}
// Create a new node
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}
// Insert into complete binary tree
void insert(struct Node** root, struct Queue* q, int value) {
struct Node* newNode = createNode(value);
if (*root == NULL) {
*root = newNode;
} else {
struct Node* front = q->arr[q->front];
if (front->left == NULL) {
front->left = newNode;
} else if (front->right == NULL) {
front->right = newNode;
dequeue(q); // Remove the front node if it has two children
}
}
enqueue(q, newNode); // Add the new node to the queue
}
// Enqueue operation
void enqueue(struct Queue* q, struct Node* node) {
q->arr[q->rear++] = node;
}
// Dequeue operation
struct Node* dequeue(struct Queue* q) {
return q->arr[q->front++];
}
// Level Order Traversal
void levelOrderTraversal(struct Node* root) {
if (root == NULL) return;
struct Queue q = {{NULL}, 0, 0};
enqueue(&q, root);
while (q.front < q.rear) {
struct Node* temp = dequeue(&q);
printf(“%d “, temp->data);
if (temp->left) enqueue(&q, temp->left);
if (temp->right) enqueue(&q, temp->right);
}
printf(“\n”);
}
Output
mathematica
Copy code
Level Order Traversal:
1 2 3 4 5 6
Applications of Complete Binary Tree
- Heap Implementation: Complete binary trees are used in heaps (e.g., max-heap, min-heap).
- Binary Search Operations: Useful in searching algorithms and maintaining priority queues.
- Memory Allocation: Data structures like heaps aid in memory management.
Advantages of Complete Binary Tree
- Efficient Use of Space: Compact representation in an array.
- Balanced Structure: Ensures minimal height for a given number of nodes.
Disadvantages
- Rebalancing: If implemented dynamically, maintaining the “complete” property can require rebalancing.
- Inefficiency in Pointer Representation: Additional overhead compared to arrays when using pointers for a large number of nodes.