从文件中读取二叉树

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未提供，因此我无法测试所做的更改。