Algorithm
A complete binary tree is a special type of binary tree in which all levels are completely filled, except possibly for the last level, which is filled from left to right. In other words, every level, except possibly the last, is completely filled, and all nodes are as left as possible.
Here are some key properties of a complete binary tree:
-
Fill from left to right: The nodes are added from left to right on each level, ensuring that the left child is filled before the right child.
-
Last level: The last level of the tree may not be completely filled, but the nodes in that level should be filled from left to right.
-
Height: The height of the tree is minimized, given the number of nodes. If the last level is partially filled, it is filled from left to right.
-
Array representation: A complete binary tree can be efficiently represented using an array. If a node is at index i in the array, its left child is at index 2i+1 and its right child is at index 2i+2.
For example, consider the following complete binary tree:
markdown
1
/ \
2 3
/ \ /
4 5 6
In the corresponding array representation, the elements would be: [1, 2, 3, 4, 5, 6].
The concept of a complete binary tree is often used in data structures and algorithms, particularly in heap implementations, where the heap is a complete binary tree with specific ordering properties.
Code Examples
#1 Complete Binary Tree implement in Python
Code -
Python Programming
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class CompleteBinaryTree:
def __init__(self):
self.root = None
def insert(self, key):
if not self.root:
self.root = Node(key)
else:
self._insert(self.root, key)
def _insert(self, current, key):
queue = [current]
while queue:
node = queue.pop(0)
if not node.left:
node.left = Node(key)
break
elif not node.right:
node.right = Node(key)
break
else:
queue.append(node.left)
queue.append(node.right)
def level_order_traversal(self):
if not self.root:
return []
result = []
queue = [self.root]
while queue:
node = queue.pop(0)
result.append(node.key)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
# Example usage:
if __name__ == "__main__":
cbt = CompleteBinaryTree()
keys = [1, 2, 3, 4, 5, 6, 7, 8, 9]
for key in keys:
cbt.insert(key)
print("Level Order Traversal:", cbt.level_order_traversal())
#2 Complete Binary Tree implement in Java
Code -
Java Programming
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
class CompleteBinaryTree {
Node root;
// Constructor to create a new complete binary tree
public CompleteBinaryTree() {
root = null;
}
// Function to insert a new node in the tree
public void insert(int key) {
root = insert(root, key);
}
// Recursive function to insert a new node with the given key
private Node insert(Node root, int key) {
if (root == null) {
root = new Node(key);
return root;
}
// Insert the new node in the level order traversal
if (root.left == null) {
root.left = new Node(key);
} else if (root.right == null) {
root.right = new Node(key);
} else {
// If left and right are already filled, insert in the next level
root.left = insert(root.left, key);
}
return root;
}
// Function to perform a level order traversal of the tree
public void levelOrderTraversal() {
if (root == null) {
return;
}
int height = getHeight(root);
for (int i = 1; i < = height; i++) {
printGivenLevel(root, i);
}
}
// Function to get the height of the tree
private int getHeight(Node root) {
if (root == null) {
return 0;
} else {
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
}
// Function to print nodes at a given level
private void printGivenLevel(Node root, int level) {
if (root == null) {
return;
}
if (level == 1) {
System.out.print(root.data + " ");
} else if (level > 1) {
printGivenLevel(root.left, level - 1);
printGivenLevel(root.right, level - 1);
}
}
public static void main(String[] args) {
CompleteBinaryTree tree = new CompleteBinaryTree();
for (int i = 1; i < = 10; i++) {
tree.insert(i);
}
System.out.println("Level Order Traversal of the Complete Binary Tree:");
tree.levelOrderTraversal();
}
}
#3 Complete Binary Tree implement in C
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
// Define a structure for a tree node
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// Function to create a new node
TreeNode* createNode(int value) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}
// Function to insert a node into the tree
TreeNode* insert(TreeNode* root, int value, int index, int n) {
// Base case: If the index is greater than or equal to n, return
if (index >= n) {
return root;
}
// Create a new node with the given value
root = createNode(value);
// Recursively insert the left child
root->left = insert(root->left, 2 * index + 1, n);
// Recursively insert the right child
root->right = insert(root->right, 2 * index + 2, n);
return root;
}
// Function to print the tree in in-order traversal
void inOrderTraversal(TreeNode* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}
int main() {
// Number of nodes in the tree
int n;
printf("Enter the number of nodes in the tree: ");
scanf("%d", &n);
// Initialize the root of the tree
TreeNode* root = NULL;
// Insert nodes into the tree
root = insert(root, 1, 0, n);
// Print the tree in in-order traversal
printf("In-order traversal of the complete binary tree: ");
inOrderTraversal(root);
// Free the memory allocated for the tree nodes
// (In a real-world scenario, you might want to implement a proper tree deletion function)
return 0;
}
#4 Complete Binary Tree implement in C++
Code -
C++ Programming
#include <iostream>
#include <queue>
// Define the structure of a binary tree node
template < typename T>
struct Node {
T data;
Node* left;
Node* right;
// Constructor
Node(T value) : data(value), left(nullptr), right(nullptr) {}
};
// Define the CompleteBinaryTree class
template < typename T>
class CompleteBinaryTree {
private:
Node* root;
public:
// Constructor
CompleteBinaryTree() : root(nullptr) {}
// Insert a node into the tree
void insert(T value) {
if (root == nullptr) {
root = new Node(value);
return;
}
std::queue < Node*> q;
q.push(root);
while (!q.empty()) {
Node < T>* temp = q.front();
q.pop();
if (!temp->left) {
temp->left = new Node < T>(value);
break;
} else {
q.push(temp->left);
}
if (!temp->right) {
temp->right = new Node < T>(value);
break;
} else {
q.push(temp->right);
}
}
}
// Inorder traversal
void inorder(Node < T>* node) {
if (node) {
inorder(node->left);
std::cout << node->data << " ";
inorder(node->right);
}
}
// Public method to start inorder traversal from the root
void inorderTraversal() {
inorder(root);
std::cout << std::endl;
}
};
// Example usage
int main() {
CompleteBinaryTree < int> tree;
// Insert elements into the tree
tree.insert(1);
tree.insert(2);
tree.insert(3);
tree.insert(4);
tree.insert(5);
// Perform inorder traversal
std::cout << "Inorder Traversal: ";
tree.inorderTraversal();
return 0;
}
Demonstration
Complete Binary Tree-DevsEnv