generating all possible binary trees from a permutation of input ints reading data from file

Question

I am trying to generate all possible binary trees, from a given input for example if the input is 1,2,3,4 then there will be 24 permutations of this input like for example

2       4       3       1
2       4       1       3
3       2       1       4
3       2       4       1
3       1       2       4
3       1       4       2
3       4       1       2
3       4       2       1
4       2       3       1
4       2       1       3

I am storing these permutations in a file result.txt I have written separately program to create a binary tree combined both these programs and the semi final code looks like this

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

struct btnode
{
    int value;
    struct btnode *l;
    struct btnode *r;
}*root = NULL, *temp = NULL, *t2, *t1;

void delete1();
void insert();
void delete();
void inorder(struct btnode *t);
void create();
void search(struct btnode *t);
void preorder(struct btnode *t);
void postorder(struct btnode *t);
void search1(struct btnode *t,int data);
int smallest(struct btnode *t);
int largest(struct btnode *t);

void printarray(int arr[],int size);

int flag = 1;
/* To insert a node in the tree */
void insert()
{
    create();
    if (root == NULL)
        root = temp;
    else
        search(root);
}

/* To create a node */
void create()
{
    int data;

    printf("Enter data of node to be inserted : ");
    scanf("%d", &data);
    temp = (struct btnode *)malloc(1*sizeof(struct btnode));
    temp->value = data;
   temp->value = data;
    temp->l = temp->r = NULL;
}

/* Function to search the appropriate position to insert the new node */
void search(struct btnode *t)
{
    if ((temp->value > t->value) && (t->r != NULL))      /* value more than root node value insert at right */
        search(t->r);
    else if ((temp->value > t->value) && (t->r == NULL))
        t->r = temp;
    else if ((temp->value < t->value) && (t->l != NULL))    /* value less than root node value insert at left */
        search(t->l);
    else if ((temp->value < t->value) && (t->l == NULL))
        t->l = temp;
}

/* recursive function to perform inorder traversal of tree */
void inorder(struct btnode *t)
{
   if (root == NULL)
    {
        printf("No elements in a tree to display");
        return;
    }
    if (t->l != NULL)
        inorder(t->l);
    printf("%d -> ", t->value);
    if (t->r != NULL)
        inorder(t->r);
}

/* To check for the deleted node */
void delete()
{
    int data;

    if (root == NULL)
    {
        printf("No elements in a tree to delete");
        return;
  }
    printf("Enter the data to be deleted : ");
    scanf("%d", &data);
    t1 = root;
    t2 = root;
    search1(root, data);
}

/* To find the preorder traversal */
void preorder(struct btnode *t)
{
    if (root == NULL)
    {
        printf("No elements in a tree to display");
        return;
    }
    printf("%d -> ", t->value);
    if (t->l != NULL)
        preorder(t->l);
    if (t->r != NULL)
        preorder(t->r);
}

/* To find the postorder traversal */
void postorder(struct btnode *t)
{
    if (root == NULL)
    {
        printf("No elements in a tree to display ");
        return;
    }
    if (t->l != NULL)
        postorder(t->l);
    if (t->r != NULL)
        postorder(t->r);
    printf("%d -> ", t->value);
}

/* Search for the appropriate position to insert the new node */
void search1(struct btnode *t, int data)
{
    if ((data>t->value))
    {   t1 = t;
        search1(t->r, data);
    }
    else if ((data < t->value))
    {
        t1 = t;
        search1(t->l, data);
    }
    else if ((data==t->value))
    {
        delete1(t);
    }
}

/* To delete a node */
void delete1(struct btnode *t)
{
    int k;

    /* To delete leaf node */
  /* To delete leaf node */
    if ((t->l == NULL) && (t->r == NULL))
    {
        if (t1->l == t)
        {
            t1->l = NULL;
        }
        else
        {
            t1->r = NULL;
        }
        t = NULL;
        free(t);
        return;
    }

    /* To delete node having one left hand child */
    else if ((t->r == NULL))
    {
        if (t1 == t)
        {
            root = t->l;
      t1 = root;
        }
        else if (t1->l == t)
        {
            t1->l = t->l;

        }
        else
        {
            t1->r = t->l;
        }
        t = NULL;
        free(t);
        return;
    }

    /* To delete node having right hand child */
    else if (t->l == NULL)
    {
        if (t1 == t)
        {
     root = t->r;
            t1 = root;
        }
        else if (t1->r == t)
            t1->r = t->r;
        else
            t1->l = t->r;
        t == NULL;
        free(t);
        return;
    }

    /* To delete node having two child */
    else if ((t->l != NULL) && (t->r != NULL))
    {
        t2 = root;
        if (t->r != NULL)
        {
            k = smallest(t->r);
            flag = 1;
        }
   else
        {
            k =largest(t->l);
            flag = 2;
        }
        search1(root, k);
        t->value = k;
    }

}

/* To find the smallest element in the right sub tree */
int smallest(struct btnode *t)
{
    t2 = t;
    if (t->l != NULL)
    {
        t2 = t;
        return(smallest(t->l));
    }
    else
      return (t->value);
}

/* To find the largest element in the left sub tree */
int largest(struct btnode *t)
{
    if (t->r != NULL)
    {
        t2 = t;
        return(largest(t->r));
    }
    else
        return(t->value);
}




//function to print the array
void printarray(int arr[], int size)
{
    FILE *fp;
    int i,j;
    fp=fopen("result.txt","a");
    for(i=0; i<size; i++)
    {
          //  printf("%d\t",arr[i]);
      fprintf(fp,"%d\t",arr[i]);
    }
    fprintf(fp,"\n");
    fclose(fp);
}

//function to swap the variables
void swap(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

//permutation function
void permutation(int *arr, int start, int end)
{
    if(start==end)
    {
        printarray(arr, end+1);
        return;
    }
    int i;
    for(i=start;i<=end;i++)
    {
        //swapping numbers
        swap((arr+i), (arr+start));
        //fixing one first digit
        //and calling permutation on
        //the rest of the digits
        permutation(arr, start+1, end);
        swap((arr+i), (arr+start));
    }
}

int main()
{
    //taking input to the array
    int size;
    printf("Enter the size of array\n");
    scanf("%d",&size);
    int i;
    int arr[size];
    for(i=0;i<size;i++)
        scanf("%d",&arr[i]);
    //calling permutation function

    permutation(arr, 0, size-1);
    return 0;
}

I am stuck in the main function here what I am not able to understand is my results.txt file contains output of permutation as

3       4       2       1
4       2       3       1
4       2       1       3

to be able to create the tree I need to read from the file result.txt line by line each line will generate a separate tree that I want to display on stdout. Now the file is too long with all input permutations each new permutation separated from previous via \n so how do I go on reading if I do a fgets on the file

while (fgets(line,sizeof(line),fp)){
        create_tree(line);<-- this function is not in above code I will implement just to give an idea of my logic of implementation

I am not able to understand how do I separate input values in line user may have given a variable series in starting so sscanf is not a solution here because in each execution of program user may execute it like this

Enter the size of array
5

and the series as input is 1 2 3 4 5 in another execution user may execute like

Enter the size of array
4

and the series as input is 1 2 3 4

also a problem I am facing is in multiple executions result.txt should be over written first time I don't find the file opening modes w or a sufficient for this.But I can get rid of this by implementing if file exist then delete but above problem reading line by line argument in variable choices is my problem from file. How to implement this?

`while` + `fgets` + `strtok` or `strchr` + `atoi` or `strtol`. Aren't this separate questions? Genering binary tree from an input / reading stream of numbers separated by spaces / generating all permutations from list of elements - these look like separate topics to me. 1. Read input line by line and parse it. 2. Write a function for generating all permutations from list of elements with a callback function. 3. in that callback function create binary trees 4. Using a binary tree "constructor" that takes as input an array of ints. — KamilCuk, Sep 26 '18 at 15:02
@kelalaka Quote from question: " I need to read from the file result.txt line by line each line will generate a separate tree that I want to display on stdout." — Support Ukraine, Sep 26 '18 at 15:52
Regarding the file problem see https://stackoverflow.com/questions/873454/how-to-truncate-a-file-in-c — Support Ukraine, Sep 26 '18 at 16:15

Support Ukraine · Accepted Answer · 2018-09-27T04:58:28.603

There seem to be more than one question here. I'll focus on this part:

I am not able to understand how do I separate input values...

So as far as I understand you have a line (read from the file) with a variable number of numbers and you want to parse that line to get each individual number.

Below is an example showing how it can be done. For simplicity I have hardcode the user/file input.

#include <stdio.h>

#define MAX 10

int parseLine(char *line, int *arr )
{
    int j = 0;
    int x = 0;
    int t;
    while(j < MAX && sscanf(line + x, "%d%n", &arr[j], &t) == 1)
    {
        x += t;
        ++j;
    }
    return j;
}

int main(void) {
    int size = 5;                    // User input
    char line[] = "10 20 30 40 50";  // Line from file

    int numbers[MAX];
    if (size > MAX)
    {
        printf("Too many numbers!\n");
        return 0;
    }
    int count = parseLine(line, numbers);
    if (count != size)
    {
        printf("Wrong number found!\n");
        return 0;
    }
    printf("Found %d numbers in the line\n", count);
    for(int t=0; t<count; ++t) printf("%d\n", numbers[t]);

    // Build tree from the "count" number in the array

    return 0;
}

Output:

Found 5 numbers in the line
10
20
30
40
50

yes correct this is the only part troubling me some one suggested fget,strtok ,strchr,atoi that is also correct — ss321c, Sep 27 '18 at 03:50

generating all possible binary trees from a permutation of input ints reading data from file

1 Answers1