AVAILABLE: 5
The structure of a tree is non-linear, unlike linear structures such as linked lists, stacks, and queues. Each node in a tree has levels, typically referred to as parent and child nodes. A binary tree is a specific type of tree structure where each parent node can have a maximum of two children, referred to as the left child and the right child.
A tree is a non-linear data structure that represents hierarchical relationships (one-to-many relationships) between elements. It can be defined as a collection of nodes with one special element called the root. The other nodes are considered subtrees or branches. In simple terms, a tree can be described as a set of elements where one element is designated as the root, and the others are divided into disjoint sets.
Types of Binary Trees
Full Binary Tree
A binary tree where every node (except the leaves) has two children, and every subtree has the same path length.
Complete Binary Tree
Similar to a full binary tree, but the subtrees can have different path lengths. Nodes (except leaves) have either 0 or 2 children.
Skewed Binary Tree
A binary tree where all nodes (except leaves) have only one child.
Declaring a Tree
A tree consists of nodes. The components of a node are typically represented in C++ as follows:
struct Node {
int data;
Node *left;
Node *right;
};
Initializing a Tree
Initially, a binary tree is empty, meaning it has no nodes. This can be set in the main function as:
Node *tree;
tree = NULL;
Adding a Node to the Tree
In a binary tree, adding a new node follows these rules:
- If the tree is empty, the new node becomes the root.
- If the tree is not empty, start at the root and perform the following checks:
- If the new node's value is less than the current node's value, move to the left child. If the left child is empty, the new node is added as the left child.
- If the new node's value is greater than the current node's value, move to the right child. If the right child is empty, the new node is added as the right child.
- This recursive process continues until the new node is placed.
Example recursive function for adding nodes:
void addNode(Node **root, int newData) {
if (*root == NULL) {
Node *newNode = new Node;
newNode->data = newData;
newNode->left = NULL;
newNode->right = NULL;
*root = newNode;
std::cout << "Node added!\n";
} else if (newData < (*root)->data) {
addNode(&(*root)->left, newData);
} else if (newData > (*root)->data) {
addNode(&(*root)->right, newData);
} else {
std::cout << "Node already exists!\n";
}
}
Tree Traversals
Preorder Traversal
Visit the node, then its left child, followed by its right child.void preOrder(Node *root) { if (root != NULL) { std::cout << root->data << " "; preOrder(root->left); preOrder(root->right); } }Inorder Traversal
Visit the left child, then the node, followed by the right child.void inOrder(Node *root) { if (root != NULL) { inOrder(root->left); std::cout << root->data << " "; inOrder(root->right); } }Postorder Traversal
Visit the left child, then the right child, followed by the node.void postOrder(Node *root) { if (root != NULL) { postOrder(root->left); postOrder(root->right); std::cout << root->data << " "; } }
Complete Program
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
struct Node {
int data;
Node *left;
Node *right;
};
void addNode(Node **root, int newData) {
if ((*root) == NULL) {
Node *newNode;
newNode = new Node;
newNode->data = newData;
newNode->left = NULL;
newNode->right = NULL;
(*root) = newNode;
(*root)->left = NULL;
(*root)->right = NULL;
std::cout << "Data added!";
getch();
} else if (newData < (*root)->data) {
addNode(&(*root)->left, newData);
} else if (newData > (*root)->data) {
addNode(&(*root)->right, newData);
} else if (newData == (*root)->data) {
std::cout << "Data already exists!";
getch();
}
}
void preOrder(Node *root) {
if (root != NULL) {
std::cout << root->data << " ";
preOrder(root->left);
preOrder(root->right);
}
}
void inOrder(Node *root) {
if (root != NULL) {
inOrder(root->left);
std::cout << root->data << " ";
inOrder(root->right);
}
}
void postOrder(Node *root) {
if (root != NULL) {
postOrder(root->left);
postOrder(root->right);
std::cout << root->data << " ";
}
}
void main() {
int data;
Node *tree;
tree = NULL;
char choice;
do {
clrscr();
std::cout << "1. Add Node\n";
std::cout << "2. View Pre-order\n";
std::cout << "3. View In-order\n";
std::cout << "4. View Post-order\n";
std::cout << "5. Exit\n";
std::cout << "Enter your choice (1-5): ";
std::cin >> choice;
if (choice != '1' && choice != '2' && choice != '3' && choice != '4' && choice != '5') {
std::cout << "\n\nInvalid choice...\n";
} else {
if (choice == '1') {
std::cout << "\nNew data: ";
std::cin >> data;
addNode(&tree, data);
} else if (choice == '2') {
std::cout << "\n";
if (tree != NULL) {
preOrder(tree);
} else {
std::cout << "Tree is empty!";
}
getch();
} else if (choice == '3') {
std::cout << "\n";
if (tree != NULL) {
inOrder(tree);
} else {
std::cout << "Tree is empty!";
}
getch();
} else if (choice == '4') {
std::cout << "\n";
if (tree != NULL) {
postOrder(tree);
} else {
std::cout << "Tree is empty!";
}
getch();
}
}
} while (choice != '5');
}
void BinaryTree::remove(int d) {
// Locate the element
bool found = false;
if (isEmpty()) {
std::cout << "This tree is empty!\n";
return;
}
tree_node *current;
tree_node *parent;
current = root;
while (current != NULL) {
if (current->data == d) {
found = true;
break;
} else {
parent = current;
if (d > current->data) current = current->right;
else current = current->left;
}
}
if (!found) {
std::cout << "Data not found!\n";
return;
}
// Options:
// 1. Remove a leaf node
// 2. Remove a node with one child
// 3. Remove a node with two children
// Node with one child
if ((current->left == NULL && current->right != NULL) || (current->left != NULL && current->right == NULL)) {
if (current->left == NULL && current->right != NULL) {
if (parent->left == current) {
parent->left = current->right;
delete current;
} else {
parent->right = current->right;
delete current;
}
} else {
if (parent->left == current) {
parent->left = current->left;
delete current;
} else {
parent->right = current->left;
delete current;
}
}
return;
}
// Leaf node
if (current->left == NULL && current->right == NULL) {
if (parent->left == current) parent->left = NULL;
else parent->right = NULL;
delete current;
return;
}
// Node with two children
if (current->left != NULL && current->right != NULL) {
tree_node *checker = current->right;
if (checker->left == NULL && checker->right == NULL) {
current = checker;
delete checker;
current->right = NULL;
} else {
// Find the smallest value in the right subtree
if (current->right->left != NULL) {
tree_node *leftCurr;
tree_node *leftCurrParent;
leftCurrParent = current->right;
leftCurr = current->right->left;
while (leftCurr->left != NULL) {
leftCurrParent = leftCurr;
leftCurr = leftCurr->left;
}
current->data = leftCurr->data;
delete leftCurr;
leftCurrParent->left = NULL;
} else {
tree_node *temp = current->right;
current->data = temp->data;
current->right = temp->right;
delete temp;
}
}
return;
}
}
This code demonstrates a binary tree implementation in C++ with node addition, traversal (pre-order, in-order, and post-order), and node removal.
Source
Prepared by Eko Riswanto.