Recorrido de orden de nivel al convertir N-ary Tree en una representación de lista de adyacencia con K como Node raíz

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
  
// A binary tree node
struct Node {
    int data;
    vector<Node*> child;
};
  
// Function to create a new tree node
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->data = key;
    return temp;
}
  
// Adjacency list to store the Tree
vector<vector<int> > adj;
  
// Function to perform the DFS traversal
// of the N-ary tree using the given
// pointer to the root node of the tree
void DFS(struct Node* node)
{
    // Traverse all child of node
    for (auto x : node->child) {
        if (x != NULL) {
  
            // Insert the pair of vertices
            // into the adjacency list
            adj[node->data].push_back(x->data);
            adj[x->data].push_back(node->data);
  
            // Recursive call for DFS on x
            DFS(x);
        }
    }
}
  
// Function to print the level order
// traversal of the given tree with
// s as root node
void levelOrderTrav(int s, int N)
{
    // Create a queue for Level
    // Order Traversal
    queue<int> q;
  
    // Stores if the current
    // node is visited
    vector<bool> visited(N);
  
    q.push(s);
  
    // -1 marks the end of level
    q.push(-1);
    visited[s] = true;
    while (!q.empty()) {
  
        // Dequeue a vertex from queue
        int v = q.front();
        q.pop();
  
        // If v marks the end of level
        if (v == -1) {
            if (!q.empty())
                q.push(-1);
  
            // Print a newline character
            cout << endl;
            continue;
        }
  
        // Print current vertex
        cout << v << " ";
  
        // Add the child vertices of
        // the current node in queue
        for (int u : adj[v]) {
            if (!visited[u]) {
                visited[u] = true;
                q.push(u);
            }
        }
    }
}
  
// Driver Code
int main()
{
    Node* root = newNode(1);
    (root->child).push_back(newNode(2));
    (root->child).push_back(newNode(3));
    (root->child).push_back(newNode(4));
    (root->child).push_back(newNode(5));
    (root->child[0]->child).push_back(newNode(6));
    (root->child[0]->child).push_back(newNode(7));
    (root->child[2]->child).push_back(newNode(8));
    (root->child[3]->child).push_back(newNode(9));
    (root->child[3]->child).push_back(newNode(10));
    (root->child[3]->child).push_back(newNode(11));
    int N = 11;
    int K = 5;
    adj.resize(N + 1, vector<int>());
  
    DFS(root);
    levelOrderTrav(5, 11);
  
    return 0;
}