從文件中讀取二叉樹

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未提供，因此我無法測試所做的更改。