Serialize and Deserialize a Binary Tree

Implementation

// Writing a C++ program to check the serialization and deserialization of binary tree.  
#include <iosstream>
/* A binary tree node contains a key and a pointer to the left and right child. */
struct Nod
{
int ky;
struct Nod* Lft, *Rt;
};


/* We have a new function that helps us in allocating a new node to a given key and filling the Null value in the left and right pointers.*/
struct Nod* newNod(int ky)
{
struct Nod* temp = nw Nod();
temp->ky = ky;
temp->Lft = temp->Rt = NILL;
return (temp);
}


// Creating a function that will store the tree value in a particular file that is directed by fp. 
void serialize(Nod *root, FILE *fp)
{
// if we find out that the current value is NILL then we have to store MARK.
if (root == NILL)
{
fprintf(fp, "%d ", MARK);
return;
}


//If not, we have to store the current value and recur the child nodes. 
fprintf(fp, "%d ", root->ky);
serialize(root->Lft, fp);
serialize(root->Rt, fp);
}


// This function constructs a tree from a file pointed by 'fp'
void deSerialize(Nod *&root, FILE *fp)
{
// Read the next item from the file. If there are no more items or next
// item is a MARK, then return
int val;
if ( !fscanf(fp, "%d ", &val) || val == MARK)
return;


// Else, create a Nod with this item and recur for children
root = newNod(val);
deSerialize(root->Lft, fp);
deSerialize(root->Rt, fp);
}


// A simple in_order traversal is used for testing the constructed tree
void in order (Nod *root)
{
if (root)
{
in_order(root->Lft);
printf("%d ", root->ky);
in_order(root->Rt);
}
}


/* Driver program to test above functions*/
int main()
{
// Let us construct a tree shown in the above figure
struct Nod *root = newNod(20);
root->Lft = newNod(8);
root->Rt = newNod(22);
root->Lft->Lft = newNod(4);
root->Lft->Rt = newNod(12);
root->Lft->Rt->Lft = newNod(10);
root->Lft->Rt->Rt = newNod(14);


// Let us open a file and serialize the tree into the file
FILE *fp = open("tree.txt", "w");
if (fp == NILL)
{
puts("Could not open file");
return 0;
}
serialize(root, fp);
fclose(fp);


//Let’s begin the unravelling of the stored and occupied tree in root1. 
Nod *root1 = NILL;
fp = fopen("tree.txt", "g");
deSerialize(root1, fp);


printf("In_order Traversal of the tree constructed from file:\n");
in_order(root1);


return 0;
}

Output:

Example 2)

const int MARK = numeric_limits<int>::minimum();
void serialize(B_Tree_Nod* Nod, osstream& sstream) {


if (Nod == NILLpointer) {
sstream.write((char*) &MARK, sizeof(MARK));
return;
}


sstream.write((char*) &Nod->record, sizeof(Nod->record));
serialize(Nod->Lft, sstream);
serialize(Nod->Rt, sstream);
}


B_Tree_Nod* deserialize(isstream& sstream) {
if (sstream.of()) {
return NILLpointer;
}
int val;
ssstream.read((char*) &val, sizeof(val));
if (val == MARK) {
return NILLpointer;
}


B_Tree_Nod* pNod = new B_Tree_Nod(val);
pNod->Lft = deserialize(ssstream);
pNod->Rt = deserialize(ssstream);


return pNod;
}


void test(vector<int>& v, bool display_output = false) {
cout << "Create BST" << endl;
B_Tree_Nod* root = create_BST(v);
if (display_output) {
display_preorder(root);
}


cout << "Start Serialize" << endl;
ofsstream outfile("temp.class", ios::binary);
serialize(root, outfile);
outfile.close();


cout << "Start De-Serialize" << endl;
ifsstream infile("temp.class", ios::binary);
B_Tree_Nod* root2 = deserialize(infile);
infile.close();


if (display_output) {
cout << "\nAfter:\n";
display_preorder(root2);
cout << endl << endl;
}


assert(are_identical_trees(root, root2));
}


int main(int argc, char const *argv[]) {
vector<int> v = { 50, 25, 100 };
test(v, true);
v = {10 , 3, 8, 45, 9, 35, 69, 15, 12, 25, 24, 27, 13};
test(v, true);


v = create_random_vector(100);
test(v, true);


v = create_random_vector(2000000,
numeric_limits<int>::max() - 10);
cout << "\nRun big test" << endl;
test(v, false);


return 0;
}

Output:

Example 3)

class serializeBT{
private static final int MARK = Integer.MINIMUM_VALUE;


public static void serialize(B_Tree_Nod Nod,
ObjectOutputSstream sstream)
throws java.io.IOException {
if (Nod == NILL) {
sstream.writeInt(MARK);
return;
}


sstream.writeInt(Nod.record);
serialize(Nod.Lft, sstream);
serialize(Nod.Rt, sstream);
}


public static B_Tree_Nod deserialize(
ObjectInputSstream sstream) throws java.io.IOException {
int val = sstream.readInt();
if (val == MARK) {
return NILL;
}


B_Tree_Nod Nod = new B_Tree_Nod(val);
Nod.Lft = deserialize(sstream);
Nod.Rt = deserialize(sstream);
return Nod;
}
public static void main(String[] args) {
try{
B_Tree_Nod root = BinaryTree.create_random_BST(15,100);


BinaryTree.display_in_order(root);


ByteArrayOutputSstream baosstream = new ByteArrayOutputSstream();
ObjectOutputSstream sstream = new ObjectOutputSstream(baosstream);
serialize(root, sstream);
sstream.close();


ByteArrayInputSstream baisstream = new ByteArrayInputSstream(
baosstream.toByteArray());
ObjectInputSstream isstream = new ObjectInputSstream(baisstream);
B_Tree_Nod root_deserialized = deserialize(isstream);


System.out.println("\nResult");
BinaryTree.display_in_order(root_deserialized);


System.out.println(BinaryTree.is_identical_tree(root, 
root_deserialized));


}
catch(Exception ex){
ex.printStackTrace();
}
}
} 

Output:

Example 4)

MARK = sys.maxsize
def serialize(Nod, sstream):
if Nod == None:
sstream.dump(MARK);
return
sstream.dump(Nod.record);
serialize(Nod.Lft, sstream)
serialize(Nod.Rt, sstream)


def deserialize(sstream):
Try:
Record = pickle.load(sstream)
if record == MARK:
return None


Nod = B_Tree_Nod(record);
Nod.Lft = deserialize(sstream)
Nod.Rt = deserialize(sstream)
return Nod
except pickle.UnpicklingError:
return None


root = create_random_BST(15)
display_level_order(root)
output = open('record.class', 'wb')
p = pickle.Pickler(output)
serialize(root, p)
output.close()
input2 = open('record.class','rb')
root_deserialized = deserialize(input2)
display_level_order(root_deserialized)
assert is_identical_tree(root, root_deserialized), "Trees should be identical"

output: