25. DSA with C++ - Implementation of Trees

Implementation of Trees

Introduction: Here's an example implementation of a tree in C++. In this implementation, each node can have an arbitrary number of child nodes. We'll define a basic structure for the tree and demonstrate how to create and traverse the tree:

 
#include <iostream>
#include <vector>

// Node structure for the tree
struct Node {
 int data;
 std::vector<Node*> children;
};

// Function to create a new node
Node* createNode(int value) {
 Node* newNode = new Node;
 newNode->data = value;
 return newNode;
}

// Function to insert a child node to a parent node
void insertChild(Node* parent, Node* child) {
 parent->children.push_back(child);
}

// Function to traverse the tree in pre-order (root, children)
void preOrderTraversal(Node* node) {
 if (node == nullptr) {
 return;
 }
 std::cout << node->data << " ";
 for (Node* child : node->children) {
 preOrderTraversal(child);
 }
}

int main() {
 // Create nodes
 Node* root = createNode(1);
 Node* child1 = createNode(2);
 Node* child2 = createNode(3);
 Node* child3 = createNode(4);
 Node* grandchild1 = createNode(5);
 Node* grandchild2 = createNode(6);
 // Build the tree structure
 insertChild(root, child1);
 insertChild(root, child2);
 insertChild(root, child3);
 insertChild(child1, grandchild1);
 insertChild(child1, grandchild2);
 // Perform tree traversal
 std::cout << "Pre-order traversal: ";
 preOrderTraversal(root); // Output: 1 2 5 6 3 4
 std::cout << std::endl;
 // Clean up memory (optional)
 delete grandchild1;
 delete grandchild2;
 delete child1;
 delete child2;
 delete child3;
 delete root;
 return 0;
}
    

Explanation:

• In this implementaon, we have a Node structure that represents a node in the tree. Each node has an integer data value and a vector of child nodes.
• The createNode funcon is used to create a new node with the given value, and the insertChild funcon is used to insert a child node to a parent node.
• The preOrderTraversal funcon performs a pre-order traversal of the tree, vising the root node and then recursively traversing its children. In this example, the pre-order traversal is used to print the data of each node.
• In the main funcon, we create nodes and build the tree structure by inserng child nodes to parent nodes. We then perform a pre-order traversal to print the data of the nodes.
• Remember to free the memory allocated for the nodes by using delete for each node in the tree at the end of the program.

Visual represention of above code:

 
    1 
  / | \ 
 2  3  4 
/ \ 
5  6