C言語で二分探索木を辞書順で制作したいです。

Question

前提・実現したいこと

キーボードから入力された会員番号と氏名を二分探索木の木として登録し、
木を構築する際の過程をprintf関数で表示することを目指しています。
何とか会員番号順で二分探索木を作成することは出来たのですが
氏名を辞書順で作成することが出来ません。
どのように改良すれば辞書順で作成することが出来るのでしょうか？

まだまだプログラミング初学者なため出来るだけ簡単に分かりやすく
ご教授いただければ幸いです。よろしくお願いします。

該当のソースコード

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NAME_LEN 20

struct node_t {
  int number;
  char name[MAX_NAME_LEN];
  struct node_t *left;
  struct node_t *right;
};

struct node_t *mallocNode(int number, char *name){
  struct node_t *add;

  add = (struct node_t*)malloc(sizeof(struct node_t));
  if(add == NULL){
    return NULL;
  }

  add->left = NULL;
  add->right = NULL;
  add->number = number;
  strcpy(add->name, name);

  return add;
}

struct node_t *addNode(struct node_t *root, int number, char *name)
{
  struct node_t *node;

  if(root == NULL){

    root = mallocNode(number, name);
    if(root == NULL){
      printf("malloc error\n");
      return NULL;
    }
    return root;
  }

  node = root;
  while(1) {

    if(number < node->number){

      if(node->left == NULL){

        node->left = mallocNode(number, name);

        break;
      }

      node = node->left;
　　
　　 } else if(number > node->number){

      if(node->right == NULL){

        node->right = mallocNode(number, name);

        break;
      }

      node = node->right;
    } else {

      printf("%d already exist\n", number);
      break;
    }
  }

  return root;
}

void printTree(struct node_t *root, int depth){
  int i;

  if(root == NULL){
    return ;
  }

  printTree(root->right, depth+1);

  for(i = 0; i < depth; i++){
    printf("  ");
  }

  printf("+%3d(%s)\n", root->number, root->name);

  printTree(root->left, depth+1);

  depth++;
}

int main(void){

  struct node_t *root, *node;
  int number;
  char name[MAX_NAME_LEN];
  int loop;
  int select;

  root = NULL;

do {
    printf("Name:");
    scanf("%s", name);
    printf("Number:");
    scanf("%d", &number);

    root = addNode(root, number, name);

    loop = 0;

    printTree(root, 0);

    printf("Again?【Yes -> 1, No -> 0】:"); scanf("%d", &select);

  } while (select == 1);

  return 0;
}

補足

二分探索木は木の形を保ったまま左に９０度回転したような形で表現しています。
他に二分探索木の良い表現方法などありましたら是非教えて頂きたいです。
よろしくお願いします。

Comments

[hoshi-takanori]

number と node->number を比較してるところ (2 箇所) を name と node->name の比較に変えれば良いのでは。

[4431]

残念ながら試してみても上手く動作しませんでした。

[hoshi-takanori]

具体的にどのようなコードを書いて、どううまくいかなかったのでしょうか？

[4431]

ご指摘の通りnumber と node->number を比較してるところ (2 箇所) を name と node->name の比較に変更し、コンパイル、実行してみました。しかしどんな氏名だろうが、どんな会員番号だろうが二分探索木の右側の子ノードにしか新しいデータが追加されず、正しく木を構築することが出来ませんでした。

[hoshi-takanori]

つまり name < node->name にしたってことでしょうか？ それだとポインタ (文字列が存在するメモリの番地) の比較になってしまいます。
https://yu-nix.com/blog/2021/11/27/c-string-compare/

[4431]

全くその通りでした。

またstrcmpを使って文字列を比較しようとしているのですが
どのように実装すればいいのかご教授していただけないでしょうか？

Answer 1

C で文字列が同じかどうかを判定する方法を書いた記事はよく見かけますが、大小比較のやり方まで書いてある記事はあまり見かけないですね…。

使う関数は同じ strcmp ですが、この関数は strcmp(str1, str2) とした場合、str1 と str2 が同じなら 0、str1 のほうが小さければマイナスの値、str1 のほうが大きければプラスの値が返ります。

したがって、「name が node->name よりも小さい (辞書順で前)」という if 文は次のように書きます。

    if (strcmp(name, node->name) < 0) {
      // name が node->name よりも小さい時の処理
    }

Comments

[4431]

回答ありがとうございます。
アドバイスを参考にして作成したところ無事に完成しました。

質問への追記・修正の依頼として多くのメッセージを残していただいて
ありがとうございました。