Чтение двоичного дерева из файла

Question

Я работаю над вводом из файла и думаю, что у меня есть логика, но мои узлы не связаны правильно. Я могу правильно установить корневой каталог, и программа сможет пройти через строку и правильно загрузить узлы, просто не связывая их. Может ли кто-нибудь помочь мне разобраться в моей логике и выяснить проблему?

Входная строка: (A (B (D G) E) (C() F)).

struct node 
    { 
    string data; 
    node* left; 
    node* right; 
    }; 

    void tree::build_tree(string &input, int i, node *n) 
    { 
    if(i > input.length()) 
      return *n = NULL; 

    if(input[i] == '(') 
    { 
     string data; string temp; 
     int prev_i = i; 

    //get_data retrieves the identifier 
    data = get_data(input, temp, i+1); 

    //get_data_num retrieves the new position in the string 
    i = get_data_num(input, temp, i+1); 

    if(input[prev_i] == '('&& input[i] == ')') 
    { 
     i += 1; 
     *n = NULL; 
    } 
    else 
    { 
     // Allocate a new node and assign the data and 
     // set the pointer to the branches to null 
     *n = new node; 
    (*n)->data = data; 
    (*n)->left = NULL; 
    (*n)->right = NULL; 

    if(input[i] == ' ') 
    {i += 1; } 

    //Pass the address of the nodes 
    build_tree(input, i, &(*n)->left); 
    build_tree(input, i, &(*n)->right); 
    } 

    } 

    else if(isalnum(input[i]) || input[i] == '_' || input[i] == '-') 
    { 
    string data; string temp; 
    int prev_i = i; 

    data = get_data(input, temp, i); 
    i = get_data_num(input, temp, i); 

    if(input[prev_i] == '('&& input[i] == ')') 
    { 
     i += 1; 
     *n = NULL; 
    } 
    else 
    { 
     *n = new node; 
     (*n)->data = data; 
     (*n)->left = NULL; 
     (*n)->right = NULL; 

     if(input[i] == ' ') 
     { i += 1; } 

    build_tree(input, i, &((*n)->left)); 
    build_tree(input, i, &((*n)->right)); 
    } 
    } 

    else if(input[i] == ' ') 
    { 
    i += 1; 
    } 

    else if(input[i] == ')') 
    { 
    i += 1; 
    *n = NULL; 
    } 

    else 
    { 
    cout << "The input tree is not in the correct format!" << endl; 
    } 
    } 

Answer 1

Я считаю, что проблема заключается в том, что вы не устанавливаете значение левого и правого указателей. Вы передаете значения указателей. Вам нужно передать указатель на указатели (влево и вправо), чтобы установить значение в структуре. Другой альтернативой является использование ссылок вместо указателей.

Вот модификации я придумал для кода, поставляемого:

• Изменен вызов build_tree для аргумента узла будет указатель на указатель.
• Соответственно присвоены значения значений.
• Измененный вызов build_tree для передачи адреса слева и справа (до получить указатель на указатель).
• Удалить назначение/условия для установки root_node. Поэтому, когда вы вызываете , введите build_tree, который вам нужно передать в адрес root. Этот будет устанавливать узел точно так же, как и все последующие узлы, поэтому для него не требуется .
• Добавлено назначение NULL для левого и правого в случае отсутствия ветви (возможно, это не понадобится, но я считаю, что это хорошая практика убедиться, что все элементы имеют некоторые начальные значения).

void tree::build_tree(string &input, int i, node **n) 
{ 

    if(input[i] == '(') 
    { 
    string data; string temp; 

    //get_data retrieves the identifier 
    data = get_data(input, temp, i+1); 

    //get_data_num retrieves the new position in the string 
    i = get_data_num(input, temp, i+1); 

    // Allocate a new node and assign the data and 
    // set the pointer to the branches to null 
    *n = new node; 
    (*n)->data = data; 
    (*n)->left = NULL; 
    (*n)->right = NULL; 

    if(input[i] == ' ') 
    { i += 1; } 

    // Pass the address of the nodes 
    build_tree(input, i, &(*n)->left); 
    build_tree(input, i, &(*n)->right); 
    } 

    else if(isalnum(input[i]) || input[i] == '_' || input[i] == '-') 
    { 
    string data; string temp; 
    data = get_data(input, temp, i); 
    i = get_data_num(input, temp, i); 

    *n = new node; 
    (*n)->data = data; 
    (*n)->left = NULL; 
    (*n)->right = NULL; 

    if(input[i+1] == ' ') 
    { i += 1; } 

    build_tree(input, i, &((*n)->left)); 
    build_tree(input, i, &((*n)->right)); 
    } 

    else if(input[i] == ' ') 
    { 
    i += 1; 
    } 

    else if(input[i] == ')') 
    { 
    *n = NULL; 
    } 

    else 
    { 
    cout << "The input tree is not in the correct format!" << endl; 
    } 
} 

Тогда для начального вызова,

build_tree (TestString, 0, & корень);

Поскольку get_data и get_data_num не были предоставлены, я не смог проверить сделанные изменения.