генерирование всех возможных двоичных деревьев из перестановки входных целых чисел, считывающих данные из файла

Question

Я пытаюсь сгенерировать все возможные двоичные деревья из заданного ввода, например, если ввод 1,2,3,4, тогда будет 24 перестановки этого ввода, например,

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

Я храню эти перестановки в файле result.txt. Я написал отдельную программу для создания двоичного дерева, объединяющего обе эти программы, и полуфинальный код выглядит следующим образом

#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;
}

Я застрял в основной функцииздесь я не могу понять, что мой файл results.txt содержит выходные данные перестановки в виде

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

, чтобы иметь возможность создавать дерево, которое мне нужно читать из файла result.txt построчно каждая строкасоздаст отдельное дерево, которое я хочу отобразить на стандартный вывод.Теперь файл слишком длинный со всеми входными перестановками, каждая новая перестановка отделена от предыдущей с помощью \n. Как мне продолжить чтение, если я выполняю fgets для файла

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

Я не могу понятькак разделить входные значения в строке user, возможно, при запуске был задан ряд переменных, поэтому sscanf здесь не является решением, потому что при каждом выполнении программы пользователь может выполнить его следующим образом

Enter the size of array
5

и ряд в качестве ввода1 2 3 4 5 при другом выполнении пользователь может выполнить, как

Enter the size of array
4

, а серия в качестве входных данных - 1 2 3 4

. Также проблема, с которой я сталкиваюсь, заключается в нескольких выполнениях.перезаписано в первый раз, я не нахожу режимы открытия файла w или достаточно для этого. Но я могу избавиться от этого, реализовав, если файл существует, затем удалить, но выше проблема чтения аргумента построчно при выборе переменной является моей проблемой из файла,Как это реализовать?

Answer 1

Кажется, здесь больше, чем один вопрос.Я сосредоточусь на этой части:

Я не могу понять, как разделить входные значения ...

Насколько я понимаю, у вас естьстрока (считанная из файла) с переменным числом чисел, и вы хотите проанализировать эту строку, чтобы получить каждое отдельное число.

Ниже приведен пример, показывающий, как это можно сделать.Для простоты у меня есть жесткий код для ввода пользователя / файла.

#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;
}

Вывод:

Found 5 numbers in the line
10
20
30
40
50