Deserialize binary tree

[MirelPasa]

Hello.
I'm working on a program that deserializes a binary tree from file
Besides what it is doing,my program should also be able to read hexadecimal numbers and big double numbers from file.With big double numbers i am working on it but with hexadecimals i dont know how to do it.
Also the marker that indicates that the node has no child is -1 and i want it to be a character(for example #) but im not having much success with this.
Can someone help me with these two problems(reading hexadecimals from file and replacing -1 with # as a marker?).

    #include <stdio.h>
    #define MARKER -1
    
    struct Node
    {
        int key;
        struct Node* left, *right;
    };
    
    Node* newNode(int key)
    {
        Node* temp = new Node;
        temp->key = key;
        temp->left = temp->right = NULL;
        return (temp);
    }
    
    void deSerialize(Node *&root, FILE *fp)
    {
    
        int val;
        if ( !fscanf(fp, "%d ", &val) || val == MARKER)
           return;
    
        root = newNode(val);
        deSerialize(root->left, fp);
        deSerialize(root->right, fp);
    }
    
    void preorder(Node *root)
    {
        if (root)
        {
            printf("%d ", root->key);
            preorder(root->left);
            preorder(root->right);
        }
    }
    
    int main()
    {
        Node *root1 = NULL;
        FILE *fp = fopen("tree.txt", "r");
        deSerialize(root1, fp);
    
        printf("preorder Traversal of the tree constructed from file:\n");
        preorder(root1);
    
        return 0;
    }

As an example,if the file contains 1 2 4 -1 -1 5 -1 -1 3 -1 -1 it will display 1 2 4 5 3
Thank you!

[Duthomhas]

If you can assume some way to distinguish types (such as: there will always be spaces between node values), then you can easily delimit on spaces and then determine the type from the string data.

So, first, are you using C or C++? Please pick one. The suggestions I have differ significantly depending on which language you wish.

Second, you are not accounting for possible input error and you are not cleaning up your dynamic memory.

[MirelPasa]

Hello Duthomhas.The values are separated by space.I am using C.Please feel free to give me your suggestions.

[Duthomhas]

Sure. Sorry, one more question. How are you storing floating-point numbers vs integers vs whatever in your tree? (I can make a suggestion if you don't know.)

[Duthomhas]

Okay, so this is unusual for me, I'm basically posting code that does what you want (I think).

From your description you appear to want a variant-type binary tree. Soooo, we create a discriminated union with non-discriminated left and right child nodes as our base node type.

Use the Get and Set functions to manipulate a node..

I added int, float, and string types to the variant. Strings are messy, but all of this shows how you can play with managing the data.

#include <iso646.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


/*---------------------------------------------------------------------------*/
/* Variant Binary Tree                                                       */
/*---------------------------------------------------------------------------*/
/*
  Each node may contain the following value types:
    • Integer
    • Floating Point Double
    • Double-quoted string
      (anything following a backslash '\' is treated literally).
*/

typedef enum { int_type, float_type, string_type } node_type;

typedef struct node_type
{
    node_type type;
    union
    {
        int    _int;
        double _float;
        char*  _string;
    }
    value;
    struct node_type* left;
    struct node_type* right;
}
Node;


    /* not for use by user */
    void Node_ClearNode(Node* node)
    {
        if (node)
        {
            switch (node->type)
            {
                case int_type:
                case float_type:
                    break;
                case string_type:
                    free( node->value._string );
                    node->value._string = NULL;
                    break;
            }
        }
    }
    
    /* not for use by user */
    void Node_SetNode(Node* node, node_type type, const void* value)
    {
        if (node)
        {
            Node_ClearNode(node);
            node->type = type;
            switch (type)
            {
                case int_type:    node->value._int    = value ?           *(int*)   value  : 0;    break;
                case float_type:  node->value._float  = value ?           *(double*)value  : 0.0;  break;
                case string_type: node->value._string = value ? strdup((const char*)value) : NULL; break;
            }
        }
    }
    
    /* not for use by user */
    Node* Node_CreateNode(node_type type, const void* value, Node* left, Node* right)
    {
        Node* node  = malloc(sizeof(Node));
        node->type  = int_type;
        Node_SetNode(node, type, value);
        node->left  = left;
        node->right = right;
        return node;
    }


/* USER API :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: */

/* Get and set a node's value */
void SetIntNode   (Node* node, int         n) { Node_SetNode(node, int_type,   &n); }
void SetFloatNode (Node* node, double      x) { Node_SetNode(node, float_type, &x); }
void SetStringNode(Node* node, const char* s) { Node_SetNode(node, string_type, s); }

node_type GetNodeType(Node* node) { return node ? node->type : 0; }

int   GetIntNode   (Node* node) { return GetNodeType(node) == int_type    ? node->value._int    : 0;    }
float GetFloatNode (Node* node) { return GetNodeType(node) == float_type  ? node->value._float  : 0.0;  }
char* GetStringNode(Node* node) { return GetNodeType(node) == string_type ? node->value._string : NULL; }


/* Create a new node or tree */
Node* CreateIntNode   (int         n) { return Node_CreateNode(int_type,     &n, NULL, NULL); }
Node* CreateFloatNode (double      x) { return Node_CreateNode(float_type,   &x, NULL, NULL); }
Node* CreateStringNode(const char* s) { return Node_CreateNode(string_type,   s, NULL, NULL); }

Node* CreateIntNodes   (int         n, Node* left, Node* right) { return Node_CreateNode(int_type,     &n, left, right); }
Node* CreateFloatNodes (double      x, Node* left, Node* right) { return Node_CreateNode(float_type,   &x, left, right); }
Node* CreateStringNodes(const char* s, Node* left, Node* right) { return Node_CreateNode(string_type,   s, left, right); }


/* Destroy a tree */
void DeleteNodes(Node* node)
{
    if (node)
    {
        Node_ClearNode(node);
        DeleteNodes(node->left);
        DeleteNodes(node->right);
        free(node);
    }
}

[Duthomhas]

/*---------------------------------------------------------------------------*/
/* Tree Preorder Input Serialization                                         */
/*---------------------------------------------------------------------------*/

char* ReadQuotedString(FILE* fp)
{
    int    c;
    size_t n = 0;
    size_t N = 100;
    char*  s = (char*)malloc(N);
    
    if (!s) return NULL;

    // Read the opening quote
    fscanf(fp, "%1s", s);
    if (*s != '"')
    {
      ungetc(*s, fp);
      free( s );
      return NULL;
    }

    // Read until non-escaped closing quote
    for (;;)
    {
        // Realloc if more space needed
        if (n == N)
        {
            char* S = (char*)realloc(s, N+100);
            if (!S) break;
            s = S;
            N += 100;
        }

        // Get next character from FILE
        c = fgetc(fp);
        if (c == EOF) break;

        // Escapes
        if (c == '\\')
        {
            c = fgetc(fp);
            if (c == EOF) break;
        }

        // End quoted string
        else if (c == '"')
            break;

        // Any other character
        s[ n++ ] = c;
    }

    // Make sure to null-terminate the string
    s[ n ] = '\0';
    return s;
}


Node* ReadNodes(FILE* fp)
{
    Node*  node = NULL;
    int    i, n;
    double f;
    char*  s;

    char  fmt[ 50 ];
    char  buf[ 50 ];

    if (!fscanf(fp, "%1s", buf))
        return NULL;

    switch (*buf)
    {
        case '.':
            return NULL;

        case '"':
            // Attempt to read a quoted string
            ungetc('"', fp);
            s = ReadQuotedString(fp);
            if (!s) return NULL;
            node = CreateStringNode(s);
            if (!node) free(s);
            break;

        default:
            ungetc(*buf, fp);
          
            // (Get the whitespace-delimited string)
            sprintf(fmt, "%%%ds", (int)sizeof(fmt));
            if (!fscanf(fp, fmt, buf))
                return NULL;

            // Attempt to read decimal, hexadecimal, or octal integer
            if (sscanf(buf, "%i%n", &i, &n) and (n == strlen(buf)))
            {
                node = CreateIntNode(i);
                break;
            }
            
            // Attempt to read a decimal or hexadecimal floating point number
            f = strtod(buf, &s);
            if (s == strchr(buf,'\0'))
            {
                node = CreateFloatNode(f);
                break;
            }
            
            // failure
    }

    // Read any node children
    if (node)
    {
        node->left  = ReadNodes(fp);
        node->right = ReadNodes(fp);
    }
    return node;
}


/*---------------------------------------------------------------------------*/
/* Tree Preorder Output Serialization                                        */
/*---------------------------------------------------------------------------*/

void WriteQuotedString(FILE* fp, const char* s)
{
    fputc('"', fp);
    while (*s)
    {
        if ((*s == '\\') or (*s == '"'))
            fputc('\\', fp);
        fputc(*s++, fp);
    }
    fputc('"', fp);
}


void PrintNodes(FILE* fp, Node *node)
{
    if (node)
    {
        switch (node->type)
        {
            case int_type:    fprintf(fp, "%d",     node->value._int);    break;
            case float_type:  fprintf(fp, "%g",     node->value._float);  break;
            case string_type: WriteQuotedString(fp, node->value._string); break;
        }
        fputc(' ', fp);
        PrintNodes(fp, node->left);
        PrintNodes(fp, node->right);
    }
    else fprintf(fp, ". ");
}


/*---------------------------------------------------------------------------*/
/* Main Program                                                              */
/*---------------------------------------------------------------------------*/

int main()
{
    FILE* fp = fopen("tree.txt", "r");
    Node* root = ReadNodes(fp);

    printf("Preorder traversal of the tree constructed from file:\n");
    PrintNodes(stdout, root);

    DeleteNodes(root);
    return 0;
}

C is obnoxious because it is not very easy to put all this stuff in one spot. (That would require additional high-level coding and preprocessor magic, which we'll skip for now.)

If this is a school project, learn from the example and code up something on your own. It will make your life a little more stressful for a couple of nights, but so much more satisfying in the end.

Own it!

(And enjoy!)

[MirelPasa]

Thank you very much!