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

問題は、左右のポインターの値を設定していないことだと思います。ポインターの値を渡しています。構造体に値を設定するには、ポインター (左と右) にポインターを渡す必要があります。もう 1 つの方法は、ポインターの代わりに参照を使用することです。

あなたが提供したコードに対して私が思いついた変更は次のとおりです。

  • ノード引数の build_tree への呼び出しをポインターへのポインターに変更しました。
  • それに応じて値の割り当てを変更しました。
  • 左と右のアドレスを渡す (ポインターへのポインターを取得する) ように build_tree への呼び出しを変更しました。
  • root_node を設定する割り当て/条件を削除します。したがって、build_tree を呼び出すときは、ルートのアドレスを渡す必要があります。これにより、後続のすべてのノードと同様にノードが設定されるため、特別なケースである必要はありません。
  • ブランチがない場合に備えて、左と右に 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 が提供されていないため、行われた変更をテストできませんでした。

于 2013-02-09T20:03:37.263 に答える