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 *root, vector<pair<int, int>> &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<int, int>> &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;
} |