This C program demonstrates how to serialize a binary tree into a file and deserialize it back into a tree structure using pre-order traversal.

Program Explanation

The program is structured into several functions:

• Node Structure: Defines the structure of a binary tree node.
• Serialize Function: Writes the tree to a file in a pre-order traversal. Null pointers are recorded as markers.
• Deserialize Function: Reads the tree structure from a file and reconstructs the binary tree.
• Utility Functions: Includes functions for creating new nodes and inserting nodes into the tree.
• Main Function: Demonstrates serialization and deserialization processes.

Program Code

// Include necessary headers
#include <stdio.h>
#include <stdlib.h>

// Define the structure for tree nodes
typedef struct node {
    int data;
    struct node* left;
    struct node* right;
} Node;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Function to serialize the binary tree
void serialize(Node* root, FILE* file) {
    if (root == NULL) {
        fprintf(file, "# ");
        return;
    }
    fprintf(file, "%d ", root->data);
    serialize(root->left, file);
    serialize(root->right, file);
}

// Function to deserialize the binary tree
Node* deserialize(FILE* file) {
    int val;
    char ch;

    if (!fscanf(file, "%d", &val)) {
        fscanf(file, "%c", &ch);
        return NULL;
    }

    Node* node = createNode(val);
    node->left = deserialize(file);
    node->right = deserialize(file);
    return node;
}

// Main function to demonstrate serialization and deserialization
int main() {
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    // Open file for writing
    FILE* file = fopen("tree.txt", "w");
    if (file == NULL) {
        printf("Failed to open file\\n");
        return 1;
    }
    serialize(root, file);
    fclose(file);

    // Open file for reading
    file = fopen("tree.txt", "r");
    if (file == NULL) {
        printf("Failed to open file\\n");
        return 1;
    }
    Node* deserializedRoot = deserialize(file);
    fclose(file);

    // Printing to verify, actual implementation of display function needed
    printf("Deserialized tree root is %d\\n", deserializedRoot->data);
    return 0;
}
    

Key Components of the Program:

• Node Structure: Defines the structure of the nodes making up the binary tree.
• createNode Function: Allocates and initializes a new tree node with data.
• serialize Function: Recursively traverses the tree in a pre-order manner and writes each node’s value to a file. If a node is NULL, it writes a special marker (#).
• deserialize Function: Reads values from the file, reconstructing the tree by creating nodes where data is available and skipping where markers indicate NULL.
• Main Function: Sets up a sample tree, serializes it to a file, then reads the file to deserialize it back into a tree structure, and verifies the result by printing the root of the deserialized tree.

This program demonstrates a simple method to persist and recover a binary tree structure, using file operations combined with tree traversal algorithms.