Trees and Graphs‎ > ‎

Serialize N-ary Tree

Given an n-ary tree (each node can have arbitrary number of children), write a function to efficiently save the tree to a file and another to load the tree back in memory from the file.

// We will record each node's value and number of children it has using Breadth-First traversal.
// Assuming a vector is our file, and 
//  pair.first == node's value
//  pair.second == number of node's children
void SaveTree(Node *rootvector<pair<intint>> &file)
{
    if (nullptr == root)
        return;
 
    queue<Node*> q;
    q.push(root);
 
    while (!q.empty())
    {
        Node *current = q.front();
        q.pop();
 
        file.push_back(make_pair(current->value, current->children.size()));
 
        for (Node *e : current->children)
            q.push(e);
    }
}
 
Node *LoadTree(vector<pair<intint>> &file)
{
    if (file.empty())
        return nullptr;
 
    int index = 0;
    queue<pair<Node*, int>> q;
    Node *root = new Node(file[index].first);
    q.push(make_pair(root, file[index].second));
    index++;
 
    while (!q.empty())
    {
        Node *n = q.front().first;
        int ccount = q.front().second;
        q.pop();
 
        for (int i = 0; i < ccount; i++)
        {
            Node *m = new Node(file[index].first);
            q.push(make_pair(m, file[index].second));
            n->children.push_back(m);
            index++;
        }
    }
 
    return root;
}