-2

メンバー文字列を持つノードを BST に挿入し、その BST に関する情報 (高さ、順序通りのトラバーサル、葉の数など) を出力するプログラムを作成しようとしています...

現時点では、順不同のトラバーサルを行うと、ツリーの最下部にあるはずであっても、最後に入力された文字列がルートとして出力されます。

コードは次のとおりです。

挿入機能:

void insert_node(Node* root, char *nextString) {
    int newLessThanRoot = strcmp( root->Word, nextString ) > 0 ? 1 : 0; // test if nextString is left or right from root

    if (newLessThanRoot && root->Left != NULL) {
      return insert_node(root->Left, nextString);
    }
    if (!newLessThanRoot && root->Right != NULL) {
      return insert_node(root->Right, nextString);
    }

    Node* freshNode = newNode();
    freshNode->Word = malloc(strlen(nextString) +1);
    strcpy(freshNode->Word, nextString);
    freshNode->Left = NULL;
    freshNode->Right = NULL;

    if (newLessThanRoot) {
      root->Left = freshNode;
    }
    else {
      root->Right = freshNode;
    }
}

順序トラバーサル関数:

void inorder(Node *temp) {
  if (temp != NULL) {
    inorder(temp->Left);
    printf("%s ",temp->Word);
    inorder(temp->Right);
  }
}

それらがどのように使用されているか:

 char inputString[15];
  char *inputStringPtr = &inputString[0];
  Node* root;
  root = newNode();
  fscanf(infile,"%s",inputStringPtr);
  root->Word = inputString;
  //printf("Root's word: %s\n",root->Word);

  while (fscanf(infile,"%s",inputStringPtr) == 1) {
      insert_node(root,inputStringPtr);
      printf("%s\n",inputString);
  }

  int numberOfStrings = num_of_strings(root);
  int heightOfBST = height_of_tree(root);
  int numberOfLeaves = num_of_leaves(root);

  inorder(root);

入力は次のようになります。

b a c e d l m n o p z

したがって、出力（順序どおりのトラバーサルを行う場合）は次のようになります。

a b c d e l m n o p z

しかし、代わりに次のとおりです。

z a c d e l m n o p z
4

2 に答える 2

3

ここで、ルート ノードの値を読み取ります。

root = newNode();
fscanf(infile,"%s",inputStringPtr);
root->Word = inputString;

ここで、2 番目のノードの値で再度上書きします。

while (fscanf(infile,"%s",inputStringPtr) == 1) {

strdup() を使用して、ルート値のコピーを作成できます。

root->Word = strdup(inputString);

これで問題が解決するはずです。

insert_node()新しいノードごとに値を正しくコピーします。strdup()malloc(strlen())/strcpy() の代わりに、そこでも使用することを検討してください。

于 2016-02-02T19:22:47.300 に答える
2

inOrder 関数と insert_node 関数に問題はありません。使用にはいくつかの問題があります。ラインで

 root->Word = inputString;

ローカルストアのアドレスをルートに割り当てています。ローカル ストアが変化し続けると、ルート Word も変化します。

于 2016-02-02T19:25:11.637 に答える