This is an implementation of a binary tree in C++ with various operations, including insertion, deletion, search, and level-order traversal.
#include <iostream>
#include <queue>
// Binary Tree Node
struct Node {
int data;
Node* left;
Node* right;
};
// Function to create a new node
Node* createNode(int value) {
Node* newNode = new Node;
newNode->data = value;
newNode->left = nullptr;
newNode->right = nullptr;
return newNode;
}
// Function to insert a node in the binary tree
void insertNode(Node* root, int value) {
if (root == nullptr) {
root = createNode(value);
return;
}
std::queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* curr = q.front();
q.pop();
if (curr->left != nullptr) {
q.push(curr->left);
} else {
curr->left = createNode(value);
return;
}
if (curr->right != nullptr) {
q.push(curr->right);
} else {
curr->right = createNode(value);
return;
}
}
}
// Function to perform level-order traversal of the binary tree
void levelOrderTraversal(Node* root) {
if (root == nullptr) {
return;
}
std::queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* curr = q.front();
q.pop();
std::cout << curr->data << " ";
if (curr->left != nullptr) {
q.push(curr->left);
}
if (curr->right != nullptr) {
q.push(curr->right);
}
}
}
int main() {
Node* root = createNode(1);
insertNode(root, 2);
insertNode(root, 3);
insertNode(root, 4);
insertNode(root, 5);
std::cout << "Level-Order Traversal: ";
levelOrderTraversal(root); // Output: 1 2 3 4 5
std::cout << std::endl;
return 0;
}
- In this implementation, we define a Node structure to represent a node in the binary tree. Each node has an integer data value and pointers to its left and right child nodes.
- The createNode function is used to create a new node with the given value and initialize its left and right child pointers to nullptr.
- The insertNode function performs the insertion of a new node in the binary tree. It uses a queue to perform a level-by-level traversal of the tree and finds the appropriate position to insert the new node.
- The levelOrderTraversal function performs the level-order traversal of the binary tree. It uses a queue to process each node in a breadth-first manner. At each step, the current node is printed, and its left and right child nodes are enqueued for further processing.
- In the main function, we create a binary tree and insert nodes with values 2, 3, 4, and 5. Then, we perform the level-order traversal and print the nodes in breadth-first order.
Level-Order Traversal: 1 2 3 4 5
This is an implementation of a binary tree in C++ that includes various operations and demonstrates the level order traversal using recursion:
#include <iostream>
#include <queue>
// Binary Tree Node Structure
struct Node {
int data;
Node* left;
Node* right;
Node(int value) {
data = value;
left = nullptr;
right = nullptr;
}
};
// Function to insert a new node in the binary tree
void insertNode(Node* root, int value) {
if (root == nullptr) {
root = new Node(value);
return;
}
std::queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* current = q.front();
q.pop();
if (current->left == nullptr) {
current->left = new Node(value);
return;
} else {
q.push(current->left);
}
if (current->right == nullptr) {
current->right = new Node(value);
return;
} else {
q.push(current->right);
}
}
}
// Function to perform level order traversal recursively
void levelOrderTraversalRecursive(Node* root, int level) {
if (root == nullptr) {
return;
}
if (level == 1) {
std::cout << root->data << " ";
} else if (level > 1) {
levelOrderTraversalRecursive(root->left, level - 1);
levelOrderTraversalRecursive(root->right, level - 1);
}
}
// Function to calculate the height of the binary tree
int getHeight(Node* root) {
if (root == nullptr) {
return 0;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return std::max(leftHeight, rightHeight) + 1;
}
// Function to perform level order traversal using recursion
void levelOrderTraversal(Node* root) {
int height = getHeight(root);
for (int level = 1; level <= height; level++) {
levelOrderTraversalRecursive(root, level);
}
}
int main() {
// Create the binary tree
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
// Perform level order traversal
std::cout << "Level Order Traversal: ";
levelOrderTraversal(root); // Output: 1 2 3 4 5 6 7
std::cout << std::endl;
return 0;
}
- In this implementation, we have a Node structure that represents a node in the binary tree. Each node has an integer data value and pointers to its left and right child nodes.
- The insertNode function is used to insert a new node in the binary tree. It utilizes a queue to find the appropriate position for insertion by performing a level order traversal.
- The levelOrderTraversalRecursive function performs the level order traversal recursively. It prints the data of the nodes at a specific level, and for each level greater than 1, it recursively calls the function for the left and right child nodes at the next level.
- The getHeight function calculates the height of the binary tree by recursively calculating the height of the left and right subtrees and returning the maximum height plus one.
- Finally, the levelOrderTraversal function calculates the height of the binary tree using getHeight and performs the level order traversal by calling levelOrderTraversalRecursive for each level.
- In the main function, we create a binary tree with some sample nodes and perform the level order traversal.
Level-Order Traversal: 1 2 3 4 5