0

我一直在处理来自文件的输入，并认为我的逻辑是正确的，但我的节点没有正确链接。我能够正确设置根并且程序能够遍历字符串并正确加载节点，只是不链接它们。谁能帮我整理一下我的逻辑并找出问题所在？

输入字符串是 (A (B (DG) 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;
    }
    }
4

1 回答 1

0

我认为问题在于您没有设置左右指针的值。您正在传递指针的值。您需要将指针传递给指针（左和右），以设置结构中的值。另一种选择是使用引用而不是指针。

以下是我为您提供的代码提出的修改：

  • 将节点参数的 build_tree 调用更改为指向指针的指针。
  • 相应地更改了值的分配。
  • 更改了对 build_tree 的调用以传递左右的地址（以获取指向指针的指针）。
  • 删除分配/条件以设置 root_node。因此，当您调用 build_tree 时，您需要传入 root 的地址。这会将节点设置为与后面的所有节点一样，因此不需要是特殊情况。
  • 在没有分支的情况下为 left 和 right 添加了 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,&root);

由于未提供 get_data 和 get_data_num，我无法测试所做的更改。

于 2013-02-09T20:03:37.263 回答