Serialize a binary tree

#include <stdio.h>
#include <vector>
#include <string>
#include <boost/foreach.hpp>

#define foreach BOOST_FOREACH


using namespace std;

struct Node
{
int data;
Node *left;
Node *right;

Node(int d):data(d), left(NULL), right(NULL){}
};

typedef Node *Tree;

struct SerializedNode
{
int data; //this can be any type which is serializable
int parent; //index of the parent in the sequence
Node *node; //This is placeholder for dereferencing
bool isLeft;//tells whether this is left or right node

SerializedNode(int d, int p, bool l):data(d), parent(p), node(NULL), isLeft(l){}

};

void serialize(vector<SerializedNode> &v, Node *root, int parent, bool isLeft)
{
if(!root) return;
int size = v.size(); //index of the current node

v.push_back(SerializedNode(root->data, parent, isLeft));

serialize(v, root->left, size, true );
serialize(v, root->right, size, false);

}

Tree deserialize(vector<SerializedNode> &v)
{
foreach(SerializedNode &n, v)
{
n.node = new Node(n.data);

if(n.parent != -1)
{
Node *parent = v.at(n.parent).node;

n.isLeft?parent->left = n.node : parent->right = n.node;
}
}

return v[0].node;
}

string serializeTree(Tree t)
{
vector<SerializedNode> v;

serialize(v, t, -1, false);
return string((char*)(&v[0], v.size() * sizeof(SerializedNode)));
}

Tree deserializeTree(string s)
{
const char *data = s.c_str();
size_t len = s.length();

vector<SerializedNode> v;
v.reserve(len/sizeof(SerializedNode));

memcpy(&v[0], data, len);

return deserialize(v);
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s