Tree in C++

A tree is a non-linear data structure in C++ made up of a root node and several other nodes connected via edges. A node in a tree may have 0 (i.e., no child nodes) or more. A node's child nodes are linked to it through edges.

Every tree has a root node that serves as its beginning point, and every node (apart from the root) in the tree has a parent node. The root node of the hierarchy is the only node without parents. Let's go through the meanings of a few fundamental tree-related words.

• Node:

A node is a fundamental building individual in the context of trees that includes data (also known as the key) and reference to its child nodes. Each node represents a single element in the tree structure. A node's number of child nodes might vary depending on the kind of tree. For instance, each node in a binary tree can only have two offspring.

• Root:

The highest node from which all other nodes in a tree branch out is known as the root. For access to the entire tree structure, it acts as the starting point or entrance point. The root node, which symbolizes the entire tree, has no parents.

• Parent:

A node with one or more child nodes attached to it is referred to as a parent node. Every node (apart from the root) in a hierarchical tree structure has specifically one parent. Depending on its connections to other nodes, a node may simultaneously hold the roles of a parent and a child.

• Child:

In a tree, the child represents a node that is connected to the other node, known as the parent node. The relationship between the parent node and child node is that the parent node is located one level above the child node, and the edge connects them.

• Siblings:

Nodes that share a parent node are said to be siblings. In other words, nodes are considered siblings if they share a parent node. Within the tree structure, siblings belong to the same level (depth).

• Leaf:

An unbranched node in the tree is called a leaf node or an external node. A leaf node is, in other words, a node with zero outdegrees. It is found at the tree's base and is the only unrelated node.

• Height:

The distance along the longest path from any leaf node to a tree's root node defines the tree's height. It illustrates the maximum number of edges that must have traveled from the root until the farthest leaf node. A tree's depth, or how "deep" it is, may be identified by its height.

• Depth:

A node's level or separation from the root node is called its "depth" in a tree data structure. Every node has a depth one larger than its parent, except the root node, whose depth is regarded as 0. Put another way. It stands for how many edges are necessary to get from the root node to a certain node in the tree.

Example

1. Root: The first or topmost node is the root node. In the above example, the root node is 1.

2. Node: every element in the tree is the node, i.e., Node 1,2,3,4,5,6.

3. Parent and child nodes:

• Node 1 is the parent of 2 and 3
• Node 2 and 3 are the children of Node 1
• Node 2 is the parent of 5 and 6
• Node 5 and 6 are the children of Node 2

4. Siblings: The nodes with the same parent are siblings, so the siblings are Nodes 2 and 3 and Nodes 5 and 6.

5. Leaf Node: It is a node that contains no children. In the above example, Leaf nodes are Node 3,4 and 6.

6. Height of the tree: It is the length of the longest path from the leaf node to the root node

Explanation:

In the given example, the height of the tree is 2.

1. Depth of the tree: The depth is nothing but the distance from the node to the root

• Node 1 has a depth of 0
• Node 2 and 3 have depth 1
• Nodes 5 and 6 have depth 2.

Types of Trees in C++

The types of trees in C++ are:

1. General Tree
2. Forests
3. Binary Tree
4. Binary Search Tree
5. Expression Tree

1. General Tree:

A general tree is a hierarchical data structure in which any number of children, up to and including zero, may exist for any node. It is an adaptable way of illustrating the connections between items, where each node may have several branches connecting it to other nodes.

The hierarchical relationships between items, such as file systems, organizational charts, family trees, and more, are frequently represented as general trees. They give modeling complicated interactions that don't easily fit into a binary framework a flexible and organic approach.

To build a generic tree in C++, a custom node class with a data field and an object (such as a vector or list) to contain its child nodes can be used. Each node can have infinite offspring, and we may link the nodes together to create a tree structure.

Example:

#include<iostream>

using namespace std;

// Definition for a new tree node

struct TreeNode {

int data;

struct TreeNode* left;

struct TreeNode* right;

};

//function to create a new node with the given data

struct TreeNode* createNode(int data) {

    // Declare and allocate a new node

struct TreeNode* newNode = new struct TreeNode();

// Assign data to this node

newNode->data = data;

// Initialize left and right children as NULL

newNode->left = NULL;

newNode->right = NULL;

return newNode;

}

int main() {

/* Create the root node */

struct TreeNode* rootNode = createNode(10);

// Print the structure of the tree on the console

Cout << "General tree created is as follows:" << endl;

cout<<"\t\t\t"<<rootNode->data<<endl;

cout<<"\t\t\t"<<"/"<<"\\"<<endl;

// Create two child nodes for the root node. One is left, and the other is right.

rootNode->left = createNode(20);

    rootNode->right = createNode(30);

// Printing the values of the left and right child nodes 

cout << "\t\t\t" << rootNode->left->data << " " << rootNode->right->data << endl;

cout<<endl;

// Creating a child node (40) for the left child node (20) and linking both of them

rootNode->left->left = createNode(40);

// Printing the value of the left child 

cout <<"\t\t\t/"<< endl;

cout << "\t\t " << rootNode->left->left->data;

return 0;

}

Output:

Explanation:

The tree node defined as TreeNode contains three fields

• Data: This is used to store the data
• Left: This node is used to store the reference of the current left child of the node
• Right: This node stores the reference of the current right child of the node.

We created a function called createNode that accepts input as an integer and returns a pointer to a newly created or allocated TreeNode.This function creates a new node for the given date and initializes the left and right pointers of the new node as NULL.

In the main function, the createNode function creates a root node of the tree with a value of 10 and stores the returned pointer in the variable of the rootNode.Then, we print the structure of the tree as the output.

2. Forests

In C++, a "forest" is a grouping of unique, separate "trees." Imagine a forest as a collection of distinct trees growing separately from one another. The forest's trees each stand for a certain hierarchy or group of components.

A tree is a data structure in C++ containing child nodes that create a branching structure for every component, or "node," within the structure. In contrast, a forest is a collection of similar trees with unique nodes and branches. A group of tree data structures can be utilized in C++ to depict a forest. Each tree has a unique root node, and you may work on each tree separately. The woodland serves as a holding area for various trees.

Consider a forest as a collection of several family trees as an illustration. Each family tree represents a distinct family lineage with its ancestors and descendants. The forest is made up of many different family trees, yet they are all separate and unrelated. With the help of the associated code example, you may initialize several trees, each with its own root node and child nodes, to construct a forest. The data contained in each tree may then be traversed, searched for, or modified using various methods.

3. Binary Tree

A binary tree in C++ is a data structure concept containing nodes arranged hierarchically. The binary tree is a special type of tree in which each node should contain child nodes that are not more than two. The insertion, deletion, and searching are easy in the binary tree because they follow a special type of arrangement of nodes.

 A binary tree is similar to a forest tree, which does not contain any more than two children. A binary tree has a root node, which is the parent or entry point for the tree. Database indexing, hierarchical data organization, and computer science algorithms use binary trees. Utilizing binary trees frequently entails traversing the tree to reach every node, adding new items while keeping the binary search tree property, and quickly looking for a certain element.

Implementing a binary tree in C++ involves developing a structure for the tree nodes and using pointers to connect them. The pointers provide for easier tree navigation and the ability to add additional nodes as required.

Example for Binary Tree:

#include<iostream>

using namespace std;

// Definition for a node in the binary tree

struct TreeNode {

int value; // Data stored in the node

TreeNode* left; //pointer to the left child node

TreeNode*right; //pointer to the right child node

TreeNode(int val):value(val),left(NULL),right(NULL) {}

};

//function to create a new node with the given data

TreeNode*createNode(int data) {

return new TreeNode(data);

}

int main() {

// Creating the root node with value 10

TreeNode*rootNode=createNode(10);

// Creating left and right child nodes with values 20 and 30

rootNode->left = createNode(20);

rootNode->right = createNode(30);

// Creating left child nodes for the left child node with values 40 and 50

rootNode->left->left=createNode(40);

rootNode->left->right=createNode(50);

// Displaying the binary tree structure

cout<<"Binary tree structure:"<<endl;

cout<<"     

"<<rootNode->value<<endl;

cout<<" / \\"<<endl;

cout<<" " <<rootNode->left->value<<" "<<rootNode->right->value << endl;

cout<<" / \\"<<endl;

cout<<" " << rootNode->left->left->value<<"  

"<<rootNode->left->right->value<<endl;

return 0;

}

Output:

Explanation:

The header files are included in the above code, a standard header format of input and output stream.

This C++ code constructs an easily understood binary tree with four nodes by defining a binary tree. The TreeNode struct defines a node in the binary tree and has two pointers, left and right, that indicate the left and right child nodes, respectively, along with an integer value (the node's contents). The TreeNode(int val) constructor sets the child pointers to NULL and initializes a node with the value that has been provided.

A new node is created using the specified data by the createNode function. A pointer to the newly constructed node gets returned after allocating memory for the node, changing its value to the information provided, and initializing the child pointers to NULL.

The function createNode method is created in the main function. It creates the root node, which contains the value 10. Then, it creates two child nodes for the root node and links as left and right nodes of the parent node. The two child nodes contain values 20 and 30, respectively. Furthermore, it inserts two more nodes with the values 40 and 50, identifying them as the left and right children of the left child node (20), respectively.

4. Binary Search Tree

A binary search Tree, also known as BST, is a special type of tree that belongs to the data structure, making the tree operations easy. This binary search tree will make insertion, deletion, and searching easy. This tree contains nodes where each node holds a key value. The left subtree of a specific node contains only the keys lower than the node key value. The right subtree of a specified node contains only the nodes with keys higher than the key value of the parent node. In this way, the binary search Tree will be created.

The BST feature makes it possible to search for a particular key efficiently. The BST uses a binary search technique while searching for a key, checking the key with the current node's key and traversing either the left or right subtree, cutting the search space in half each time. In a balanced BST, this provides that the average time complexity of search, insertion, and deletion operations is O(log n), where n is the number of nodes in the tree.

Example:

#include<iostream>

using namespace std;

struct TreeNode {

    int value; // Data stored in the node

    TreeNode* leftChild; //pointer to the left child node

    TreeNode* rightChild; //pointer to the right child node

    TreeNode(int val) : value(val), leftChild(NULL), rightChild(NULL) {}

};

class BinarySearchTree {

    TreeNode* root; // Pointer to the root node of the BST

public:

    BinarySearchTree() {

        root=NULL; // Initialize the BST with an empty tree (no root)

    }

    bool isEmpty() {

        return (root== (TreeNode* currentNode);

};

//function to insert a new node with the given data into the BST

void BinarySearchTree::insert(int item) {

    TreeNode* newNode NULL); // Check if the BST is empty (no root node)

    }

    void insert(int item);

    void displayInOrder();

    void printInOrder=new TreeNode(item); // Create a new node with the given value

    TreeNode* parent=NULL; //pointer to keep track of the parent node

    TreeNode* currentNode=root; // Start traversing the tree from the root

    while (currentNode !=NULL) {

        parent=currentNode; // Keep track of the parent node for insertion

        if (item > currentNode->value)

currentNode=currentNode->rightChild; // Go to the right subtree

        else

currentNode=currentNode->leftChild; 

// Go to the left subtree

    }

    // Insert the new node as the child of the parent node based on the value

    if (parent==NULL)

        root=newNode; // If the tree is empty, set the new node as the root

    else if (item < parent->value)

        parent->leftChild=newNode; // Insert as the left child if the value is smaller

    else

        parent->rightChild=newNode; // Insert as the right child if the value is larger

}

//function to display the BST in in-order traversal (ascending order)

void BinarySearchTree::displayInOrder() {

    printInOrder(root); // Start in-order traversal from the root node

    cout << endl;

}

// Helper function to perform in-order traversal recursively

void BinarySearchTree::printInOrder(TreeNode* currentNode) {

    if (currentNode != NULL) {

printInOrder(currentNode->leftChild); // Visit the left subtree

cout<<currentNode->value<<" "; // Print the value of the current node

printInOrder(currentNode->rightChild); // Visit the right subtree

    }

}

int main() {

    BinarySearchTree bst;

    bst.insert(20);

    bst.insert(10);

    bst.insert(5);

    bst.insert(15);

    bst.insert(40);

    bst.insert(45);

    bst.insert(30);

    cout<<"Binary search tree created in ascending order:"<<endl;

    bst.displayInOrder();

    return 0;

}

Output:

Explanation:

This Binary Search Tree (BST) concept and basic operation are shown in C++ code. The program begins by defining a TreeNode struct, which is a node in the BST. Two pointers, leftChild and rightChild, referring to the left and right child nodes, respectively, are contained in each TreeNode, along with an integer value representing the data stored in the node. The struct additionally has a constructor that creates a TreeNode with the specified value and NULL sibling pointers as starting values.

To handle the BST, a BinarySearchTree class is defined next. It has a private member root that points to the BST's root node and public methods for carrying out different operations. The root pointer is initialized to NULL in the BinarySearchTree constructor to create a blank BST.

Insert: Using this function, the user can retain the BST property while inserting a new node with a specified value into the BST. The tree is traversed using a recursive process, and each node's location is calculated by comparing the new value to its value. A new node is created by the function and linked as either a left or right child of the proper parent node.

The displayInOrder function is used to perform in-order traversal. So that it displays in ascending order. The printInorder function is used to print or display the tree in order.

5. Expression Tree:

A binary tree called an expression tree is used to represent mathematical expressions in an organized and hierarchical way. Each tree node represents an operator or an operand in the expression. Leaf nodes represent operands, whereas interior nodes represent operators. It is simpler to evaluate and modify complicated expressions since the tree's structure exactly correlates to the order of operations in the expression.

A binary tree data structure can implement an expression tree in C++. A value (operator or operand) and pointers to its left and right children are present at each tree node. The operands will be in the tree's leaves, and the operators will be in its internal nodes.

Expression trees help analyze expressions and change their forms (from infix to postfix or prefix).

Tree Traversal Techniques

A tree data structure’s node can be visited and analyzed using tree traversal. There are several ways to traverse a tree; each one provides a distinct viewpoint on the tree's components and allows for various actions. There are three typical methods for traversing trees:

1. In Order Traversal: In in-order traversal, the nodes of a binary tree are traversed systematically. Starting at the root, the right subtree is examined before the current node and the left subtree. This traversal produces items for a binary search tree in ascending order.

In other words, a sorted view of the items of the tree is provided through in-order traversal. This method is often used when a sorted result is necessary, such as searching for certain items or creating the elements in ascending order.

2. Pre-Order Traversal: This method traverses the nodes in a different sequence. The exploration begins at the root, continues to the left subtree, and then expands to the right subtree. Pre-order traversal is particularly beneficial when it is important to accurately reconstruct the tree's structure since it outputs the tree's components in a form that makes this possible. This method is frequently used for parsing mathematical statements, generating expression trees, and prefix notation.

3. Post-Order Traversal: Post-order traversal includes traversing through the left subtree, right subtree, and current node in that order. A post-order traversal output is essential when processing child nodes before parent nodes in a program. This method is frequently employed in memory management systems, such as those that deallocate memory in a tree, where child node deletion should occur before their parent node is deleted to prevent memory leaks.

Each tree traversal method has unique benefits and is appropriate for various use situations. In computer science and related subjects, efficiently analyzing and manipulating tree structures to complete various tasks requires understanding and using certain traversal methods.

Advantages of Tree in C++

• Effective Searching and Retrieval: A C++ tree type called binary search tree provides quick searching and retrieval because of how the tree is organized. An element may be found in logarithmic time, making it a useful data structure for programs needing data.
• Hierarchical Data Representation: The ability of C++ trees to effectively express hierarchical data structures is one of its main features. Data may be managed and accessed quickly in an organized manner by using trees to organize data in a parent-child relationship.
• Flexibility: There are many different types of C++ trees, including binary trees, AVL trees, red-black trees, and general trees. Every variety of tree has unique features that make them suited for various use cases. Depending on the needs of their applications, programmers may select the best tree structure thanks to its adaptability.
• Sorting and Ordering: Binary search trees, particularly C++ trees, keesorteds in sorted order. With the help of this characteristic, data may be quickly in either ascending or descending order without the use of extra sorting methods.

Conclusion

In conclusion, trees are an important data structure in technology and are essential in many applications. Using classes and structures to represent the nodes and their connections, trees may be constructed in C++. Due to their simplicity and effectiveness, in particular, they are frequent. Binary and generic trees are only two examples of the tree data structure's many varieties.

Unlike general trees, which may have unlimited children, binary trees can only have a maximum of two children per node. A binary tree has a left and right child for each node. A node structure containing references to its left and right children is defined in the C++ code for building a tree. With the use of several tree traversal strategies like in-order, pre-order, and post-order, the elements of the tree may be added, shown, and navigated through.

Applications for trees include memory management, processing expressions, search algorithm implementation, and organizing hierarchical data. They offer effective methods for carrying out tasks, including searching, sorting, and data retrieval.