Построение полного бинарного дерева дано только по порядку?

Question

Я пытаюсь построить полное бинарное дерево (полное значение, что каждый неконечный узел имеет два листовых узла, соединяющихся с ним, т.е. node->right и node->left равны != NULL), учитывая только обход дерева по порядку,Кроме того, мне сообщают, является ли узел в обходе после заказа листовым узлом или нет.Данный обход по порядку выглядит следующим образом: например,

2(1.000000e+00)
3(1.000000e+00)
(1.000000e+00 1.000000e+00)
1(1.000000e+00)
(1.000000e+00 2.000000e+00)

, где строка в формате "%d(%le)" является листовым узлом, а "(%le %le)" - неконечным узлом.Обычно вы не можете построить дерево, используя только порядок записей, потому что было бы несколько возможностей для соединений, но я уверен, что возможность отличить листовые и неконечные узлы так или иначе важна.Моя текущая функция выглядит следующим образом:

Node *constructTreeHelper(FILE *infile, int *index) { 
    // Base case 
    if (*index <= 0) {
        return NULL; 
    }
    Node *root = NULL;

    // Check for the "(" character
    int check;
    check = getc(infile);
    fseek(infile, -1, SEEK_CUR);

    // If the node is not a leaf node
    if (check == 40) {
        double lwire, rwire;
        fscanf(infile, "(%le %le)\n", &lwire, &rwire);
        root = createNode(0, 0, lwire, rwire);
        *index = *index - 1;
        if (*index >= 0) { 
            root->right = constructTreeHelper(infile, index); 
            root->left = constructTreeHelper(infile, index); 
        } 
    } else {
        // If the node is a leaf node
        int sink;
        double cap;
        fscanf(infile, "%d(%le)\n", &sink, &cap);
        root = createNode(sink, cap, 0, 0);
        *index = *index - 1;
        if (*index >= 0) { 
            root->right = constructTreeHelper(infile, index); 
            root->left = constructTreeHelper(infile, index); 
        } 
    }
    return root;
} 

, где index равно числу узлов в дереве - 1. Очевидно, что эта реализация строит узлы только справа.Как я могу обновить это, чтобы правильно построить дерево?

Редактировать: Позвольте мне добавить еще немного информации о том, что я знаю.Итак, первый узел всегда должен быть листовым, а последний узел всегда должен быть корневым.Поскольку это не двоичное дерево поиска, а скорее просто двоичное дерево, вы не можете рекурсивно вызывать функцию с обновленными параметрами диапазона каждый раз.Моя реализация должна решить ее за O (n) раз, но я просто не могу понять, как использовать знания о том, является ли узел листовым узлом при построении дерева.

Answer 1

В вашем коде есть некоторые проблемы:

• Вы должны использовать ungetc() вместо fseek() для возврата на один символ во избежание сбоя в потоках, которые не поддерживают поиск.

• Вы должны написать (check == '(') вместо жесткого кодирования значения символа ASCII.Он более переносим и удобочитаем.

• Чтобы избежать неопределенного поведения, следует проверить EOF и fscanf() успешность разбора.На самом деле, это позволило бы избежать необходимости проверки на check.

• . При анализе конечного узла не следует повторять и анализировать дополнительные узлы ниже текущего..

• index представляется избыточным, поскольку последовательности узлов должно быть достаточно для полного определения, где остановиться.

Вот измененная версия:

Node *constructTreeHelper(FILE *infile, int *index) { 
    double lwire, rwire;
    int sink;
    double cap;
    Node *node;

    // Base case 
    if (*index <= 0) {
        // This test seems redundant with the file contents */
        return NULL; 
    }

    // this fscanf will fail on the byte byte if it is not a '('
    if (fscanf(infile, " (%le %le)", &lwire, &rwire) == 2) {
       // If the node is not a leaf node
        node = createNode(0, 0, lwire, rwire);
        *index -= 1;
        node->right = constructTreeHelper(infile, index); 
        node->left = constructTreeHelper(infile, index); 
    } else if (fscanf(infile, "%d(%le)\n", &sink, &cap) == 2) {
        // If the node is a leaf node
        node = createNode(sink, cap, 0, 0);
        *index -= 1;
    } else {
        // invalid format or end of file */
        node = NULL;
    }
    return node;
}