|
Write code to serialize and deserialize a tree.The nodes contain string......
Software QA/Tests Interview Questions from Microsoft
(Continued from previous question...)
Write code to serialize and deserialize a tree.The nodes contain string......
Question:
Write code to serialize and deserialize a tree.The nodes contain string instead of data part. the lenght of string can be anything(not fixed).
maybe an answer:
here is a code to serialize and de-serialize a binary search tree. The key idea here is to serialize the BST in pre-order.
#include "BinaryTree.h"
#include <fstream>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
static void serializeImp(btree *p, ofstream& sFile, char *buf)
{
if(p == NULL)
return;
sprintf(buf, "%d", p->data);
for(int i = 0; buf[i] != '\0'; i++)
sFile.put(buf[i]);
sFile.put(' ');
serializeImp(p->left, sFile, buf);
serializeImp(p->right, sFile, buf);
}
void serializeBST(btree *p, char *filename)
{
char buffer[34];
ofstream sFile(filename);
serializeImp(p, sFile, buffer);
sFile.close();
}
static bool getNextData(ifstream& inFile, char *buf)
{
int i;
char c;
while(!inFile.eof() && (c = inFile.get()) == ' ');
if(inFile.eof())
return false;
buf[0] = c;
for(i = 1; !inFile.eof() && (c = inFile.get()) != ' '; i++)
buf[i] = c;
buf[i] = '\0';
return true;
}
void deSerializeImp(btree **p, ifstream& inFile, int *val, char *buf, int min, int max)
{
if(*val < min || *val > max)
return;
*p = createNode(*val);
if(!getNextData(inFile, buf))
return;
*val = atoi(buf);
deSerializeImp(&(*p)->left, inFile, val, buf, min, (*p)->data);
deSerializeImp(&(*p)->right, inFile, val, buf, (*p)->data, max);
}
btree* deSerializeBST(char *filename)
{
int val;
btree *p = NULL;
ifstream inFile(filename);
char buffer[34];
if(!getNextData(inFile, buffer))
return NULL;
val = atoi(buffer);
deSerializeImp(&p, inFile, &val, buffer, INT_MIN, INT_MAX);
inFile.close();
return p;
}
int main(int argc, char *argv[])
{
btree *head = NULL, *newTree = NULL;
int arr[] = {30,20,10,40,35,50};
if(argc != 2)
cout << "invalid number of arguments" << endl;
for(int i = 0; i < 6; i++)
head = BinaryTree_insert(head, arr[i]);
serializeBST(head, argv[1]);
//newTree = deSerializeBST(argv[1]);
return 0;
}
(Continued on next question...)
Other Interview Questions
| 