How to get all child nodes of a specific node in non-binary tree in C++

Question

I'm being stuck because I don't know how to get all child nodes of a specific node in non-binary tree.

For example, the root node is A.

A = {B, C}

B = {D, E, F}

E = {G}

I want to get all child nodes of B = {D, E, F, G}

How can I do? Thank you very much.

Answer 1

You can obtain child nodes recursively.

First, walk the tree to obtain the initial node B. After that, apply this recursive pseudocode:

void get_children(Node *node, list<Node*>& res) {
    for each child in node->children {
        res.add(child);
        get_children(child, res);
    }
}

Pass B to get_children, along with an empty list of nodes. The function will add all children to the list passed into it. Make sure that you pass your list by reference; otherwise, the function will not modify your list.

Answer 2

Assuming that your tree is directed, a simple graph traversal algorithm (BFS or DFS) will do the job for you.

Breadth-First-Search(Graph, startNode):

    create empty queue Q      
    Q.enqueue(startNode)                      
    while Q is not empty:           
        current = Q.dequeue()
        for each node n that is adjacent to current:
            print n
            Q.enqueue(n)