Serialization/Deserialization of a Binary Tree

Serialize:
to Array - (for node 'i', store left child at '2i+1' & right child at '2i+2')

Assume we have a binary tree below:

    _30_
   /        \
 10      20
 /          /  \
50     45  35

Using pre-order traversal, the algorithm should write the following to a file:

30 10 50 # # # 20 45 # # 35 # #

void writeBinaryTree(BinaryTree *p, ostream &out)
{
    if (!p)
    {
        out << "# ";
    }
    else
    {
        out << p->data << " ";
        writeBinaryTree(p->left, out);
        writeBinaryTree(p->right, out);
    }
}


Deserialize:


Reading the binary tree from the file is similar. We read tokens one at a time using pre-order traversal. If the token is a sentinel, we ignore it. If the token is a number, we insert it to the current node, and traverse to its left child, then its right child.

void readBinaryTree(BinaryTree *&p, ifstream &fin)
{
    int token;
    bool isNumber;
    if (!readNextToken(token, fin, isNumber))
        return;
    if (isNumber)
    {
        p = new BinaryTree(token);
        readBinaryTree(p->left, fin);
        readBinaryTree(p->right, fin);
    }
}