Horje
Printing Hierarchical Structure with Numbering and Indentation

Consider the below diagram , which shows a sort of hierarchical organization for a company . Electronics R’Us has four departments namely R&D , Sales, Purchasing , Manufacturing . Sales is subsequently divide into Domestic and International categories and so on .

imgdrawio-(1)

We need to generate an output which describes this hierarchical structure along with numbering and indentation . Refer below image for the kind of output to be generated.

image1drawio

Approach:

Our code will have following four main components

1. TreeNode Class : Each information is stored in a tree node represented by a TreeNode class, which has an array of children and a string containing the node’s name.

2. TreeDisplay Class: It contains methods to initialize the tree and display it in the required format.

3. Initialize Tree Function : By arranging nodes and their connections, the InitializeTree function builds the tree in accordance with the supplied diagram. It creates the root node and sets its children.

4. DisplayTree Method : It recursively traverses the tree and displays each node along with its depth. It will take into account the depth (n) of the current node to determine the level of indentation. It will then print the node’s name along with its depth and particular indentation. After that we will use recursion so that it calls itself for each child node, passing the child node along with its depth and updated indentation.

Below is the implementation of the above approach:

C++ 
#include <iostream>
#include <string>
#include <vector>

class TreeNode {
public:
    std::vector<TreeNode*> children;
    std::string str;
    int childCount;

    TreeNode(std::string str, int n)
        : str(str)
        , childCount(n)
    {
        children.resize(n, nullptr);
    }
};

class TreeDisplay {
public:
    TreeNode* InitializeTree(TreeNode* root)
    {
        root = new TreeNode("Electronics R'US", 4);
        root->children[0] = new TreeNode("R&D", 0);
        root->children[1] = new TreeNode("Sales", 2);
        root->children[2] = new TreeNode("Purchasing", 0);
        root->children[3]
            = new TreeNode("Manufacturing", 3);

        root->children[1]->children[0]
            = new TreeNode("Domestic", 0);
        root->children[1]->children[1]
            = new TreeNode("International", 3);

        root->children[3]->children[0]
            = new TreeNode("TV", 0);
        root->children[3]->children[1]
            = new TreeNode("CD", 0);
        root->children[3]->children[2]
            = new TreeNode("Tuner", 0);

        root->children[1]->children[1]->children[0]
            = new TreeNode("Canada", 0);
        root->children[1]->children[1]->children[1]
            = new TreeNode("America", 0);
        root->children[1]->children[1]->children[2]
            = new TreeNode("Overseas", 4);

        root->children[1]
            ->children[1]
            ->children[2]
            ->children[0]
            = new TreeNode("Africa", 0);
        root->children[1]
            ->children[1]
            ->children[2]
            ->children[1]
            = new TreeNode("Europe", 0);
        root->children[1]
            ->children[1]
            ->children[2]
            ->children[2]
            = new TreeNode("Asia", 0);
        root->children[1]
            ->children[1]
            ->children[2]
            ->children[3]
            = new TreeNode("Australia", 0);

        return root;
    }

    void DisplayTree(TreeNode* node, int n,
                     std::string prefix)
    {
        if (n != 0) {
            std::cout << prefix << n << "\t" << node->str
                      << std::endl;
        }
        else {
            std::cout << node->str << std::endl;
        }

        if (!node->children.empty()) {
            for (size_t i = 0; i < node->children.size();
                 i++) {
                if (n == 0) {
                    DisplayTree(node->children[i], i + 1,
                                "\t");
                }
                else {
                    DisplayTree(node->children[i], i + 1,
                                "\t" + prefix
                                    + std::to_string(n)
                                    + ".");
                }
            }
        }
    }
};

int main()
{
    TreeNode* root = nullptr;
    TreeDisplay t;
    root = t.InitializeTree(root);
    t.DisplayTree(root, 0, "");
    return 0;
}
Java 
class TreeNode // Creating Class TreeNode with attributes as
               // a string an array named children to store
               // child nodes
{
    TreeNode[] children;
    String str;
    int childCount;
    TreeNode(String str,
             int n) // TreeNode Constructor takes in two
                    // parameters a string and n (no of
                    // child nodes)
    {
        this.str = str;
        childCount = n;
        children = new TreeNode[n];
    }
}

public class TreeDisplay {

    TreeNode InitializeTree(TreeNode root)
    { // Implementing the tree given in the diagram

        root = new TreeNode("Electronics R'US", 4);
        root.children[0] = new TreeNode("R&D", 0);
        root.children[1] = new TreeNode("Sales", 2);
        root.children[2] = new TreeNode("Purchasing", 0);
        root.children[3] = new TreeNode("Manufacturing", 3);

        root.children[1].children[0]
            = new TreeNode("Domestic", 0);
        root.children[1].children[1]
            = new TreeNode("International", 3);

        root.children[3].children[0]
            = new TreeNode("TV", 0);
        root.children[3].children[1]
            = new TreeNode("CD", 0);
        root.children[3].children[2]
            = new TreeNode("Tuner", 0);

        root.children[1].children[1].children[0]
            = new TreeNode("Canada", 0);
        root.children[1].children[1].children[1]
            = new TreeNode("America", 0);
        root.children[1].children[1].children[2]
            = new TreeNode("Overseas", 4);

        root.children[1].children[1].children[2].children[0]
            = new TreeNode("Africa", 0);
        root.children[1].children[1].children[2].children[1]
            = new TreeNode("Europe", 0);
        root.children[1].children[1].children[2].children[2]
            = new TreeNode("Asia", 0);
        root.children[1].children[1].children[2].children[3]
            = new TreeNode("Australia", 0);
        return root; // root of the resulting tree is
                     // returned by the function to be used
                     // in other functions
    }

    void DisplayTree(TreeNode node, int n, String prefix)
    {
        if (n != 0) {
            System.out.println(prefix + n + "\t"
                               + node.str);
        }
        else {
            System.out.println(node.str);
        }

        if (node.childCount > 0) {
            for (int i = 0; i < node.childCount; i++) {
                if (n == 0) {
                    DisplayTree(node.children[i], i + 1,
                                "\t");
                }
                else {
                    DisplayTree(node.children[i], i + 1,
                                "\t" + prefix + n + ".");
                }
            }
        }
    }
    public static void main(String[] args)
    {
        TreeNode root = null;
        TreeDisplay t = new TreeDisplay();
        root = t.InitializeTree(root);
        t.DisplayTree(root, 0, "");
    }
}
Python 
class TreeNode:
    def __init__(self, str, n):
        self.str = str
        self.childCount = n
        self.children = [None] * n

class TreeDisplay:
    def initialize_tree(self, root):
        root = TreeNode("Electronics R'US", 4)
        root.children[0] = TreeNode("R&D", 0)
        root.children[1] = TreeNode("Sales", 2)
        root.children[2] = TreeNode("Purchasing", 0)
        root.children[3] = TreeNode("Manufacturing", 3)

        root.children[1].children[0] = TreeNode("Domestic", 0)
        root.children[1].children[1] = TreeNode("International", 3)

        root.children[3].children[0] = TreeNode("TV", 0)
        root.children[3].children[1] = TreeNode("CD", 0)
        root.children[3].children[2] = TreeNode("Tuner", 0)

        root.children[1].children[1].children[0] = TreeNode("Canada", 0)
        root.children[1].children[1].children[1] = TreeNode("America", 0)
        root.children[1].children[1].children[2] = TreeNode("Overseas", 4)

        root.children[1].children[1].children[2].children[0] = TreeNode("Africa", 0)
        root.children[1].children[1].children[2].children[1] = TreeNode("Europe", 0)
        root.children[1].children[1].children[2].children[2] = TreeNode("Asia", 0)
        root.children[1].children[1].children[2].children[3] = TreeNode("Australia", 0)
        
        return root

    def display_tree(self, node, n, prefix):
        if n != 0:
            print(prefix + str(n) + "\t" + node.str)
        else:
            print(node.str)

        if node.childCount > 0:
            for i in range(node.childCount):
                if n == 0:
                    self.display_tree(node.children[i], i + 1, "\t")
                else:
                    self.display_tree(node.children[i], i + 1, "\t" + prefix + str(n) + ".")

if __name__ == "__main__":
    root = None
    t = TreeDisplay()
    root = t.initialize_tree(root)
    t.display_tree(root, 0, "")
JavaScript 
class TreeNode {
    constructor(str, n) {
        this.str = str;
        this.childCount = n;
        this.children = new Array(n).fill(null);
    }
}

class TreeDisplay {
    initializeTree() {
        let root = new TreeNode("Electronics R'US", 4);
        root.children[0] = new TreeNode("R&D", 0);
        root.children[1] = new TreeNode("Sales", 2);
        root.children[2] = new TreeNode("Purchasing", 0);
        root.children[3] = new TreeNode("Manufacturing", 3);

        root.children[1].children[0] = new TreeNode("Domestic", 0);
        root.children[1].children[1] = new TreeNode("International", 3);

        root.children[3].children[0] = new TreeNode("TV", 0);
        root.children[3].children[1] = new TreeNode("CD", 0);
        root.children[3].children[2] = new TreeNode("Tuner", 0);

        root.children[1].children[1].children[0] = new TreeNode("Canada", 0);
        root.children[1].children[1].children[1] = new TreeNode("America", 0);
        root.children[1].children[1].children[2] = new TreeNode("Overseas", 4);

        root.children[1].children[1].children[2].children[0] = new TreeNode("Africa", 0);
        root.children[1].children[1].children[2].children[1] = new TreeNode("Europe", 0);
        root.children[1].children[1].children[2].children[2] = new TreeNode("Asia", 0);
        root.children[1].children[1].children[2].children[3] = new TreeNode("Australia", 0);

        return root;
    }

    displayTree(node, n, prefix) {
        if (n !== 0) {
            console.log(prefix + n + "\t" + node.str);
        } else {
            console.log(node.str);
        }

        if (node.childCount > 0) {
            for (let i = 0; i < node.childCount; i++) {
                if (n === 0) {
                    this.displayTree(node.children[i], i + 1, "\t");
                } else {
                    this.displayTree(node.children[i], i + 1, "\t" + prefix + n + ".");
                }
            }
        }
    }
}

function main() {
    const treeDisplay = new TreeDisplay();
    const root = treeDisplay.initializeTree();
    treeDisplay.displayTree(root, 0, "");
}

main();

Output:

Capture


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
Angular Sweep in Python Angular Sweep in Python
Hopcroft–Karp Algorithm in Python Hopcroft–Karp Algorithm in Python
Convex Hull in Python Convex Hull in Python
Difference Between Recursive and Explicit Difference Between Recursive and Explicit
CSES Solutions - Permutation Inversions CSES Solutions - Permutation Inversions

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 15



 

Horje