Question

How to serialize and deserialize a binary tree in C

Answer 1

#include <stdio.h>     
#include <stdlib.h>    

struct Node
{
    int n;
    struct Node* left, *right;
};

struct Node* create_node(int n)
{
	struct Node* temp = (struct Node *)malloc(sizeof(struct Node));
    if (temp != NULL)
	{
		temp->n = n;
		temp->left = temp->right = NULL;
	}
    return (temp);
}

// stores a tree in a file 
void serialize(struct Node *root, FILE *fp)
{
    if (root == NULL)
    {
        fprintf(fp, "%d ", -1);
        return;
    }
 
    fprintf(fp, "%d ", root->n);
    serialize(root->left, fp);
    serialize(root->right, fp);
}

// constructs a tree from a file
void de_serialize(struct Node **root, FILE *fp)
{
    int n;
	
	// no more items or last item -1
    if ( !fscanf(fp, "%d ", &n) || n == -1)
       return;
 
    *root = create_node(n);
    de_serialize(&(*root)->left, fp);
    de_serialize(&(*root)->right, fp);
}

void print_tree(struct Node *root)
{
    if (root)
    {
        print_tree(root->left);
        printf("%d ", root->n);
        print_tree(root->right);
    }
}
void free_tree(struct Node *root)
{
    if (root == NULL) 
        return;
     
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

int main(int argc, char **argv)
{   
	struct Node *root        = create_node(100);
    root->left               = create_node(10);
    root->right              = create_node(70);
    root->left->left         = create_node(80);
    root->left->right        = create_node(40);
    root->left->left->left   = create_node(50);
    root->left->left->right  = create_node(30);
 
    // serialize the tree into a file
    FILE *fp = fopen("d:\\tree.txt", "w");
    if (fp == NULL)
    {
        puts("Error open file");
        return 0;
    }
    serialize(root, fp);
    fclose(fp);
 
    // deserialize the tree from a file
    struct Node *root_read = NULL;
    fp = fopen("d:\\tree.txt", "r");
    de_serialize(&root_read, fp);
 
    printf("root\n");
	print_tree(root);
	
	printf("\nroot_read\n");
	print_tree(root_read);
	
	free_tree(root);
	free_tree(root_read);
	
	fclose(fp);
	
    return 0;
}

 
/*
run:
   
root
50 80 30 10 40 100 70
root_read
50 80 30 10 40 100 70

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <stdio.h>
#include <string.h>
#include <time.h>
#include <stdlib.h> 
 
struct node 
{ 
    int val;
    struct node *left; 
    struct node *right; 
}; 
 
#define VAL_COUNT 5
 
struct node *add_to_tree(struct node *n, int num);
void serialize(struct node *root, FILE *fp);
void de_serialize(struct node **root, FILE *fp);
void print_tree(struct node *n);
void free_tree(struct node *n);
 
int main(void)
{
    struct node *root = NULL;
    int i = 0;
	
	srand((unsigned)time(NULL));
     
    while (i < VAL_COUNT)
    {
           root = add_to_tree(root, rand() % 100 + 1);
           i++;
    }
	
	// serialize the tree into a file
    FILE *fp = fopen("d:\\tree.txt", "w");
    if (fp == NULL)
    {
        puts("Error open file");
        return 0;
    }
    serialize(root, fp);
    fclose(fp);
	
    // deserialize the tree from a file
    struct node *root_read = NULL;
    fp = fopen("d:\\tree.txt", "r");
    de_serialize(&root_read, fp);
  
    // print
    printf("root\n");
    print_tree(root);
     
    printf("\nroot_read\n");
    print_tree(root_read);
     
	// free
    free_tree(root);
    free_tree(root_read);
     
    fclose(fp);
    
    return 0;
}
struct node *add_to_tree(struct node *n, int num)
{
    if (n == NULL) 
    { 
        if ( (n = (struct node *) malloc(sizeof(struct node)) ) == NULL)
        {
            printf("malloc error");
            EXIT_FAILURE;
        }
        n->val = num;
		n->left = n->right = NULL;
    } 
	else if (num < n->val) 
			  n->left = add_to_tree(n->left, num);
		 else
			  n->right = add_to_tree(n->right, num);
    
	return n;
}
void serialize(struct node *root, FILE *fp)
{
    if (root == NULL)
    {
        fprintf(fp, "%d ", -1);
        return;
    }
  
    fprintf(fp, "%d ", root->val);
    serialize(root->left, fp);
    serialize(root->right, fp);
}
void de_serialize(struct node **root, FILE *fp)
{
    int n;
     
    // no more items or last item -1
    if ( !fscanf(fp, "%d ", &n) || n == -1)
       return;
  
    *root = add_to_tree(*root, n);
    de_serialize(&(*root)->left, fp);
    de_serialize(&(*root)->right, fp);
}
void print_tree(struct node *n)
{
    if (n != NULL) 
    {
        print_tree(n->left);
        printf("%3d\n", n->val);
        print_tree(n->right);
    }
}
void free_tree(struct node *n)
{
    if (n == NULL) 
        return;
     
    free_tree(n->left);
    free_tree(n->right);
    free(n);
}

// tree.txt
// 91 88 16 -1 34 -1 -1 -1 94 -1 -1 

/*
run:

root
 16
 34
 88
 91
 94

root_read
 16
 34
 88
 91
 94

*/

 

70+ SQL courses for beginners and professionals