Create a tree from a file .txt in C

Question

my problem is the following:

I have to create a tree from a file .txt, this is an example of what is inside the file:

the first element a is the root, after that is always this way:

the first element (x for example is the left tree) the second element (b for example is the right tree).

if an element is preceded by a point, that element for sure dont have a left or right child below.

so in this case the outgoing tree will be the following:

this is the structure in c language of my tree:

typedef char element;

typedef struct tree_element {
    element value;
    struct tree_element* left, * right;
} node;

typedef node* tree;

Any ideas on how to solve this?

my incorrect solution:

bool IsEmpty(tree t) {
    return (t == NULL);
}

tree EmptyTree(void) {
    return NULL;
}
tree Left(tree t) {
    if (IsEmpty(t)) {
        return NULL;
    }
    else {
        return t->left;
    }
}

tree Right(tree t) {
    if (IsEmpty(t)) {
        return NULL;
    }
    else {
        return t->right;
    }
}

tree ConsTree(const element* e, tree l, tree r) {
    tree t = malloc(sizeof(node));
    t->value = *e;
    t->left = l;
    t->right = r;
    return t;
}


tree InsertValue(tree t, element e, int position) {
    if (IsEmpty(t)) {
        return ConsTree(&e, EmptyTree(), EmptyTree());
    }
    tree root = t;
    while (true) {
        if (position == 1) {
            if (IsEmpty(Left(t))) {
                t->left = ConsTree(&e, EmptyTree(), EmptyTree());
                break;
            }
            else {
                t = Left(t);
            }
        }
        else {
            if (IsEmpty(Right(t))) {
                t->right = ConsTree(&e, EmptyTree(), EmptyTree());
                break;
            }
            else {
                t = Right(t);
            }
        }
    }
    return root;
}


extern tree LoadTree(const char* filename) {
    FILE* f = fopen(filename, "r");
    if (f == NULL) {
        return EmptyTree();
    }
    else {
        fseek(f, 0, SEEK_END);
        if (ftell(f) == 0) {
            fclose(f);
            return EmptyTree();
        }
        else {
        
            fseek(f, 0, SEEK_SET);
            tree t = EmptyTree();
            char c;
            c = fgetc(f);
            int i = 0;
            element e;
            e = c;
            l++;
            t = InsertValue(t,e,0);
            while (c != EOF) {
                c = fgetc(f);
                if (c != ' ' && c != '\t' && c != '\r' && c != '\n' && c != '\v' && c != '\f') {
                    i++;
                }
            }
        
            fclose(f);
            return t;
        }
    }
}

thanks in advance

Answer 1

The input file gives for each sub tree the value then if not prefixed by a dot the left tree then the right tree and that recursively, so the way to construct the tree can follow the same recursion :

node * read_tree(FILE * fp)
{
  node * r = malloc(sizeof(node));
  
  fscanf(fp, " %c", &r->value);
  
  if (r->value != '.') {
    r->left = read_tree(fp);
    r->right = read_tree(fp);
  }
  else {
    fscanf(fp, " %c", &r->value);
    r->left = r->right = NULL;
  }
  
  return r;
}

The space before %c in the format bypass the possible space/newline/tab/... allowing to read a file with the indents or without them like a.xbd.s.u.c as you said in a remark.

The proposal above supposes/hopes the file is valid, else it is possible to do :

node * read_tree(FILE * fp)
{
  node * r = malloc(sizeof(node));
  const char * err;
  
  if (r == NULL)
    err = "not enough memory";
  else if (fscanf(fp, " %c", &r->value) != 1)
    err = "invalid file, unexpected EOF";
  else if (r->value != '.') {
    r->left = read_tree(fp);
    r->right = read_tree(fp);
    return r;
  }
  else if (fscanf(fp, " %c", &r->value) != 1)
    err = "invalid file, unexpected EOF after '.'";
  else if (r->value == '.')
    err = "invalid file, two consecutive '.'";
  else {
    r->left = r->right = NULL;
    return r;
  }
  
  fprintf(stderr, "%s\nposition in the file : %ld\n", err, ftell(fp));
  exit(-1);
}

---

A full program can be :

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

typedef char element;

typedef struct tree_element {
  element value;
  struct tree_element* left, * right;
} node;

node * read_tree(FILE * fp)
{
  node * r = malloc(sizeof(node));
  const char * err;
  
  if (r == NULL)
    err = "not enough memory";
  else if (fscanf(fp, " %c", &r->value) != 1)
    err = "invalid file, unexpected EOF";
  else if (r->value != '.') {
    r->left = read_tree(fp);
    r->right = read_tree(fp);
    return r;
  }
  else if (fscanf(fp, " %c", &r->value) != 1)
    err = "invalid file, unexpected EOF after '.'";
  else if (r->value == '.')
    err = "invalid file, two consecutive '.'";
  else {
    r->left = r->right = NULL;
    return r;
  }
  
  fprintf(stderr, "%s\nposition in the file : %ld\n", err, ftell(fp));
  exit(-1);
}

void print_free_tree(node * tree, int lvl)
{
  if (tree == NULL)
    putchar('.');
  else {
    putchar('(');
    print_free_tree(tree->left, lvl+1);
    printf("-%c %d-", tree->value, lvl);
    print_free_tree(tree->right, lvl+1);
    putchar(')');
    free(tree);
  }
}

int main(int argc, char ** argv)
{
  FILE * fp;
  
  if (argc != 2)
    fprintf(stderr, "Usage: %s <file>\n", *argv);
  else if ((fp = fopen(argv[1], "r")) == NULL)
    perror("cannot read file");
  else {
    node * tree = read_tree(fp);
    
    /* must be at end of file except may be some space/newline */
    char c;
    
    if (fscanf(fp, " %c", &c) == 1)
      fprintf(stderr, "invalid file, extra element(s) from the position %ld\n", ftell(fp));
    
    fclose(fp);
    
    /* show & free tree */
    print_free_tree(tree, 1);
    putchar('\n');
  }
  
  return 0;
}

Compilation and execution :

pi@raspberrypi:/tmp $ gcc -Wall c.c
pi@raspberrypi:/tmp $ cat f
a
  .x
  bd.s.u.c
pi@raspberrypi:/tmp $ ./a.out f
((.-x 2-.)-a 1-(((.-s 4-.)-d 3-(.-u 4-.))-b 2-(.-c 3-.)))
pi@raspberrypi:/tmp $ 

to help to check the validity of the tree each value is written with the level of its node, the empty branches are indicated by a '.'.

Execution under valgrind :

pi@raspberrypi:/tmp $ valgrind ./a.out f
==13298== Memcheck, a memory error detector
==13298== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==13298== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==13298== Command: ./a.out f
==13298== 
((.-x 2-.)-a 1-(((.-s 4-.)-d 3-(.-u 4-.))-b 2-(.-c 3-.)))
==13298== 
==13298== HEAP SUMMARY:
==13298==     in use at exit: 0 bytes in 0 blocks
==13298==   total heap usage: 10 allocs, 10 frees, 5,556 bytes allocated
==13298== 
==13298== All heap blocks were freed -- no leaks are possible
==13298== 
==13298== For lists of detected and suppressed errors, rerun with: -s
==13298== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
pi@raspberrypi:/tmp $