Represent and traverse a n-ary tree as a vector

Question

I've implemented a n-ary tree ( to be more specific, a trie ) and I was wondering if there's a method to represent and traverse it as a vector. With a binary tree that would be trivial ( see this question ) but I don't seem to find a way to perform this with a n-ary tree. My final goal would be storing the vector represented tree to a file, mmap it and perform fast lookups without having it effectively loaded into memory.
An efficient approach to store a trie on disk ad using it with a mmap-ped pointer instead of allocating its inner structures would be great too.

Thanks.

Answer 1

If you have a tree where every node n has exactly k children, then you can proceed by placing the children of node n at positions k*n+m in the array, where m is between 0 and k-1. This will also work if every node has k or less children, but it will use a lot more memory than required if a lot of nodes have fewer than k children. The only other way I know of to store a tree as an array where nodes have different number of children is to store an auxillary array,, where for each node you store the offset into the original array to find that node's children and then you can either also store the number of children for each node or simply look up the offset for the next node's children to figure out how many children there are for the node.

Answer 2

Any graph structure can be represented as a flat array of nodes (in fact, that's how computer memory works). You just need to use indices instead of pointers, because pointers are invalidated when the vector grows or when the structure is mmap'd.

Here's a three-way tree as a flat vector:

struct Node {
    Node(int data) : payload(data)
    {
        for (int i = 0; i < 3; i++) {
            child[i] = (size_t)(-1);  // invalid
        }
    }

    int payload;
    size_t child[3];
};

typedef std::vector<Node> Tree;

void add_node(Tree &t, size_t parent, int child_index, int payload)
{
    t.push_back(Node(payload));
    t[parent].child[child_index] = t.size() - 1;
}

You'll need separate logic to insert the root node since it doesn't have a parent. Also if you want a version where the mmap'd files can be used cross-platform, you'd better use fixed-size index types rather than the platform-specific int and size_t.

Traversal code is the same as with a pointer structure, except that

next = node->child[1]

becomes

t[t[node_idx].child[1]]

etc. i.e. each lookup of a node passes through the Tree object.

Answer 3

Assuming you know the No of node of the tree

you could change the size of adj vector to your suitable value

code->

 #include<iostream>
 #include<vector>
using namespace std;
vector<int> adj[100000000];
void dfs(int);
int main()
{

    int i,n,root,par;
    cin>>n;
     //Input line contains n space separated integers.
    // The ith integer represents the immediate ancestor of the ith node
   // Node having 0 as parent node is the Root Node
    i=1;
    while(i<=n)
    {
        cin>>par;

        if(par==0)
        {
            root=i;
        }
        else
        {
            adj[par].push_back(i);
        }
        i++;
    }
    //traversal of the Tree(Inorder traversal)
   dfs(root);

    }

    void dfs(int at)
   {
vector<int>::iterator it;
it=adj[at].begin();
cout<<*it<<" ";
while(it!=adj[at].end())
{
    dfs((*it));
    it++;
}
return;
}

Hoping this might helps