In C++, a tree is a non-linear data structure that consists of nodes connected by edges. The nodes are arranged hierarchically in a tree structure, with one node being the root node (at the top) and the remaining nodes forming one or more subtrees.
Each node in a tree has a parent node (except the root node), zero or more child nodes, and an associated value (also known as a key or payload). The relationship between the nodes is defined by the edges, which connect each node to its parent and child nodes.
There are many types of trees that are used to represent different types of data or structures, such as binary trees, AVL trees, red-black trees, and B-trees. Each type of tree has its own specific characteristics and implementation details.
Trees are commonly used in computer science and programming to represent hierarchical data structures, such as file systems, XML documents, and data organization in databases.
#include <iostream> using namespace std; struct Node { int value; Node* left; Node* right; }; Node* newNode(int value) { Node* node = new Node; node->value = value; node->left = NULL; node->right = NULL; return node; } void inorderTraversal(Node* node) { if(node != NULL) { inorderTraversal(node->left); cout << node->value << " "; inorderTraversal(node->right); } } int main() { Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); cout << "Inorder traversal of binary tree: "; inorderTraversal(root); return 0; }
This program constructs a binary tree with 5 nodes and performs an inorder traversal (i.e., prints the values in sorted order) of the tree.
This is a very simple example of a tree, and there are many more complex tree structures and algorithms that can be implemented in C++.
TYPES OF TREES:
There are various types of trees in C++ that are used depending on the specific requirements of a situation. Here are some of the most common types of trees and their implementation in C++.
- Binary Trees: A binary tree is a tree structure where each node has at most two children, referred to as the left child and right child.
Implementation:
We can represent a binary tree as a structure or class in C++. Here is a basic implementation using a structure.
#include<iostream> using namespace std; struct Node { int value; Node* left; Node* right; }; Node* newNode(int value) { Node* node = new Node; node->value = value; node->left = NULL; node->right = NULL; return node; } void inorderTraversal(Node* node) { if(node != NULL) { inorderTraversal(node->left); cout << node->value << " "; inorderTraversal(node->right); } } int main() { Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); cout << "Inorder traversal of binary tree: "; inorderTraversal(root); return 0; }
- Binary Search Trees: A binary search tree is a binary tree where the value of all nodes in the left subtree is less than or equal to the value of the root node and the value of all nodes in the right subtree is greater than the value of the root node.
Implementation:
We can represent a binary search tree as a structure or class in C++. Here is a basic implementation using a structure.
#include<iostream> using namespace std; struct Node { int value; Node* left; Node* right; }; Node* newNode(int value) { Node* node = new Node; node->value = value; node->left = NULL; node->right = NULL; return node; } void inorderTraversal(Node* node) { if(node != NULL) { inorderTraversal(node->left); cout << node->value << " "; inorderTraversal(node->right); } } Node* insertNode(Node* node, int value) { if(node == NULL) { return newNode(value); } if(value < node->value) { node->left = insertNode(node->left, value); } else { node->right = insertNode(node->right, value); } return node; } int main() { Node* root = NULL; root = insertNode(root, 50); insertNode(root, 30); insertNode(root, 20); insertNode(root, 40); insertNode(root, 70); insertNode(root, 60); insertNode(root, 80); cout << "Inorder traversal of binary search tree: "; inorderTraversal(root); return 0; }
- AVL Trees: An AVL tree is a self-balancing binary search tree where the difference in height between the left and right subtrees cannot be more than one.
Implementation:
We can represent an AVL tree as a structure or class in C++. Here is a basic implementation using a structure.
#include<iostream> using namespace std; struct Node { int value; Node* left; Node* right; int height; }; Node* newNode(int value) { Node* node = new Node; node->value = value; node->left = NULL; node->right = NULL; node->height = 1; return node; } int height(Node* node) { if(node == NULL) { return 0; } return node->height; } int getBalance(Node* node) { if(node == NULL) { return 0; } return height(node->left) - height(node->right); } Node* rightRotate(Node* y) { Node* x = y->left; Node* T2 = x->right; x->right = y; y->left = T2; y->height = max(height(y->left), height(y->right)) + 1; x->height = max(height(x->left), height(x->right)) + 1; return x; } Node* leftRotate(Node* x) { Node* y = x->right; Node* T2 = y->left; y->left = x; x->right = T2; x->height = max(height(x->left), height(x->right)) + 1;
TRAVERSAL IN TREES:
Traversal in trees refers to visiting each node in a tree exactly once. There are three ways to traverse trees: Inorder, Preorder, and Postorder. We can traverse the tree by using recursion or iteration. In this explanation, we will go over all three traversing methodologies along with their respective implementations in C++.
- Inorder Traversal: In Inorder Traversal, we first visit the left subtree of the root node, then we visit the root node, and then we visit the right subtree of the root node. In binary search trees, the inorder traversal results in the nodes' values in ascending order.
Algorithm:
Traverse the node's left subtree, then print the node, and then traverse the node's right subtree.
Implementation:
We can implement Inorder Traversal in C++ using recursion. Here is an example:
#include <iostream> using namespace std; struct Node { int value; Node* left; Node* right; }; Node* newNode(int value) { Node* node = new Node; node->value = value; node->left = NULL; node->right = NULL; return node; } void inorderTraversal(Node* node) { if(node != NULL) { inorderTraversal(node->left); cout << node->value << " "; inorderTraversal(node->right); } } int main() { Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); cout << "Inorder traversal of binary tree: "; inorderTraversal(root); return 0; }
- Preorder Traversal: In Preorder Traversal, we first visit the root node, then we visit the left subtree of the root node, and then we visit the right subtree of the root node.
Algorithm:
Print the node, traverse the node's left subtree, and then traverse the node's right subtree.
Implementation:
We can implement Preorder Traversal in C++ using recursion. Here is an example:
#include <iostream> using namespace std; struct Node { int value; Node* left; Node* right; }; Node* newNode(int value) { Node* node = new Node; node->value = value; node->left = NULL; node->right = NULL; return node; } void preorderTraversal(Node* node) { if(node != NULL) { cout << node->value << " "; preorderTraversal(node->left); preorderTraversal(node->right); } } int main() { Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); cout << "Preorder traversal of binary tree: "; preorderTraversal(root); return 0; }
- Postorder Traversal: In Postorder Traversal, we first visit the left subtree of the root node, then we visit the right subtree of the root node, and then we visit the root node.
Algorithm:
Traverse the node's left subtree, then traverse the node's right subtree, and then print the node.
Implementation:
We can implement Postorder Traversal in C++ using recursion. Here is an example:
#include <iostream> using namespace std; struct Node { int value; Node* left; Node* right; }; Node* newNode(int value) { Node* node = new Node; node->value = value; node->left = NULL; node->right = NULL; return node; } void postorderTraversal(Node* node) { if(node != NULL) { postorderTraversal(node->left); postorderTraversal(node->right); cout << node->value << " "; } } int main() { Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); cout << "Postorder traversal of binary tree: "; postorderTraversal(root); return 0; }
In all of these implementations, we have used recursion to traverse the tree. We first check if the current node is not null. If the current node is not null, we recursively call the traversal function on the left and right subtrees and print the current node's value in the desired order.
PRACTICE PROBLEMS :