CareerCup

The question was with "... tree/graph" at the end. Why r u talking about tree and traversals?

Use Matrices. You can easily store tree and graph as matrix and then serialize and deserialize matrix.

what is serialization of a binary tree?

Writing the tree to some file in binary data is called 'serialization' and reading back the file to construct the same binary tree is 'deserialization'.

void Tree::Serialize(TNode* root, int a[], int& reclevel)
{
if( NULL == root)
{
a[reclevel++] = -1;
}
else
{
a[reclevel++] = root->data;
Serialize(root->left,a,reclevel);
Serialize(root->right,a,reclevel);
}
}

TNode* Tree::DeSerialize(int a[], int& reclevel)
{
if( -1 == a[reclevel])
{
reclevel++;
return NULL;
}
else
{
TNode* node = new TNode();
node->data = a[reclevel++];
node->left = DeSerialize(a,reclevel);
node->right = DeSerialize(a,reclevel);
return node;
}
}

Hi,
Doesn't it required to construct same binary tree in dserialization ?
Or I didn't understand Ramu's solution !!!
it will change entire structure of the tree !!!
someone help plz
katie

Try appending 'L' or 'R' to the nodes as u do pre order travesal...
For example: tree like
6
/ \
3 9
/ / \
2 7 10

will be like: 6R3L2L9R7L10R

Then when u de-serialize, start inserting in the tree based on 'L' and 'R'

Any order of traversal is fine as long as the serialize and deserialize in the same order, AND you account for incomplete trees by representing an empty child something like '*' or 'x' in the serialized file. For example:

1
/ \
2 3
/ \ / \
4 5 6

Would be represented (using a depth first search) as:
123456x

For deserialization you must simply add the numbers in the same order as the depth first serialization. This is also assuming that we are only serializing integer values

hey if it means writing in file then we can go like this..
file will contain
1
23
4567

for empty child let put x.
so the code will be

int a=1,b=1;
s.push(root);
while(a!=0)
{
b=a;
a=0;

while(b>0)
{
p=s.pop();
if(p==X)
{
end loop;
}
if(p.left)
{
s.push(p.left);
a++;
}
if(p.right)
{
s.push(p.right);
a++;
}
Print p;
b--;
}
print Space;
}
\\ this code if for complete tree which doesnt miss any single child.
\\ Here if any child doesnot exist then assume it X.

convert the tree into a heap -> serialize
convert the heap into a binary tree -> deserialize