二分探索木について

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら　　※コードを貼り付ける場合は [code] と [/code] で囲って下さい。詳しくはこちら
閉鎖
TES

二分探索木について

#1

投稿記事 by TES » 15年前

二分探索木に対して、新しいデータを挿入する関数、削除する関数、および、データを検索する関数を作成したいのですが新しいデータの挿入とデータの削除がわかりません。

新しいデータの挿入は一応挿入できているのですが、正しく二分探索木に
挿入されていないほか、上書きされてしまう場合もあります。

削除する関数は色々調べながら書いてたら、ごちゃごちゃになってしまって
どうしていいかわからなくなってしまいました。

どなたかアドバイスまたは解法を教えていただけないでしょうか。
どうかよろしくお願いします。

コード: 

 
/**    ヘッダファイル    **/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**    構造体の定義     **/
struct tnode {
  struct tnode *left;
  char name[25];
  char tel[15];
  struct tnode *right;
};

/**   関数のプロトタイプ宣言  **/
int mktree(int, char * []);  //二分探索木を作る関数
void sort(struct tnode *);    //辞書順にソートする関数(再帰的)
int search(char [], char[]);
int insert(char [], char[]);
int delete(char []);
struct node* delete_min(struct node** p);

/**        変数の宣言        **/
char na[25], te[15]; //読み込んだ名前と電話番号を入れる配列
char scname[25],sctel[15];  //キーボードから名前を読み取る
FILE *fp;
struct tnode *root, *node, *old, *new;

/**        メイン関数         **/
int main(int argc, char *argv[])
{
  int no=0;
  mktree(argc,argv);

  while(1){
    printf("【二分探索木】\n"
           "検索する ===> 1\n"
           "追加する ===> 2\n"
           "削除する ===> 3\n"
           "表\示する ===> 4\n"
           "終了する ===> 5\n");

    scanf("%d",&no);
    switch (no){
    case 1:
      printf("\n【検索】\n");
      printf("●検索する名前を入力してください\n");
      scanf("%s",scname);
      printf("\n●検索する電話番号を入力してください\n");
      scanf("%s",sctel);
      search(scname,sctel);
      printf("\n");
      break;

    case 2:
      printf("\n【追加】\n");
      printf("●追加する名前を入力してください\n");
      scanf("%s",scname);
      printf("\n●追加する電話番号を入力してください\n");
      scanf("%s",sctel);
      insert(scname,sctel);
      printf("\n");
      break;

    case 3:
      printf("削除する名前を入力してください\n");
      printf("●削除する名前を入力してください\n");
      scanf("%s",scname);
      delete(scname);
      printf("\n");
      break;

    case 4:
      printf("二分探索木を表\示します\n");
      sort(root);
      printf("\n");
      break;

    case 5:
      printf("終了します\n");
      free(root);
      free(node);
      exit(0);
      break;

    default:
      printf("操作が間違っています\n");
      break;
    }
  }

    free(root);
    free(node);
    return 0;
}

/**      二分探索木を作成する関数        **/
int mktree(int argc, char *argv[])
{
  /*ファイルの指定*/
  if(argc!=2){
    printf("！注意！引数にファイル名を指定してください\a\n");
    exit(0);
  }

  /*ファイルを開くのに失敗したときの処理*/
  fp=fopen(argv[1],"r");
  if(fp==NULL){
    printf("！注意！ファイルを開けません\n");
    exit(0);
  }

  /*ルートノード*/
  root=(struct tnode *)malloc(sizeof(struct tnode));
  if(root==NULL){
    printf("！注意！メモリを確保できませんでした\a\n");
    exit(1);
  }

  /*木の作成*/
  while(fscanf(fp,"%s\t%s",na,te)!=-1){
    node=root;
    while(node!=NULL){
      old=node;
      if(strcmp(na,node->name)<=0)
        node=node->left;
      else
        node=node->right;
    }

    /*新しいノードの接続*/
    node=(struct tnode *)malloc(sizeof(struct tnode));
    if(node==NULL){
      printf("！注意！メモリを確保できませんでした\a\n");
      exit(1);
    }
    strcpy(node->name,na);
    strcpy(node->tel,te);
    node->left=node->right=NULL;
    if (strcmp(na,old->name)<=0)
      old->left=node;
    else
      old->right=node;
  }

  /*ファイルを閉じる*/
  close(fp);
  return 0;
}

/**    辞書順にソートし、出力する関数       **/
void sort(struct tnode *node){
  if(node!=NULL){
    sort(node->left);
    printf("%-25s%15s\n",node->name,node->tel);
    sort(node->right);
  }
}

/**   二分探索木からデータを検索する関数     **/
int search(char scname[], char sctel[])
{
    node=root;
    while(1){
      if(strcmp(scname,node->name)==0) break;
      if(strcmp(scname,node->name)<0){
        if(node->left==NULL) break;
        node=node->left;
      } else {
        if(node->right==NULL) break;
        node=node->right;
      }
    }

    if(strcmp(scname,node->name)==0){
       if(strcmp(sctel,node->tel)==0){
        printf("\n［結果］見つかりました\n\n");
      } else {
        printf("\n［結果］番号が違う可能\性があります\n\n");
      }
    }

    if(strcmp(scname,node->name)!=0){
      printf("\n［結果］見つかりませんでした\n\n");
    }
  return 0;
}


/**     二分探索木にデータを追加する関数      **/
int insert(char scname[], char sctel[])
{
  node=root;
  while(node!=NULL){
    old=node;
    if(strcmp(scname,node->name)==0){      //同じ名前があったときの処理
      printf("既に同じ名前があります\n");
      break;
    }

    if(strcmp(scname,node->name)<0){
      node=node->left;
    } else {
      node=node->right;
    }
  }

  node=(struct tnode *)malloc(sizeof(struct tnode));
  strcpy(node->name,scname);
  strcpy(node->tel,sctel);
  node->left=node->right=NULL;

  if(strcmp(scname,node->name)<0){
    old->left=node;
  } else {
    old->right=node;
  }
    return 0;
}

/**     二分探索木にデータを削除する関数      **/
int delete(char scname[])
{
  struct *x;

  node=root;  /* 根から開始 */
  while(node!=NULL){  /* 削除するデータが見つかるまで */

  if(strcmp(scname,node->name)!=0){
      printf("名前がありません\n");
      break;
    }

	if(scname==(node)->scname){
		x=node;
	if(x->left==NULL&&x->right==NULL){
		node=NULL;
	}else if(x->left==NULL){
		node=x->right;
	}else if( x->right == NULL ){
		node=x->left;
	}else{
		node=delete_min( &x->right );
		(node)->right = x->right;
		(node)->left = x->left;
	}
	free(x);
	return 0;
	}

	if(scname<(node)->scname){
		node=&(node)->left;
	}else{
		node=&(node)->right;
	}
	}
	
	return 1
}

struct node* delete_min(struct node** p)
{
	struct node* x;
	
	/* 最小のデータは、二分探索木の性質上、左の子を辿り続ければ発見できる */
	while( (*p)->left != NULL ) /* 左の子を持たない節まで来たら終了 */
	{
		p = &(*p)->left;  /* 左へ進む */
	}
	
	x = *p;            /* 削除するデータの位置をコピー */
	*p=(*p)->right;  /* 削除対象の右の子を、削除した節の位置に移動させる */
	return x;          /* コピーしておいたアドレスを返す */
}
ページトップ
non
記事: 1097
登録日時: 15年前

Re: 二分探索木について

#2

投稿記事 by non » 15年前

コンパイルが通らないのですが・・・・エラーのないプログラムを載せてもらえますか。
non
ページトップ
TES

Re: 二分探索木について

#3

投稿記事 by TES » 15年前

すみません。

とりあえず、これでコンパイルは通ると思います。
削除する関数を取り除いた状態ですが、
よろしくお願いします。

コード: 

 
/**    ヘッダファイル    **/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**    構造体の定義     **/
struct tnode {
  struct tnode *left;
  char name[25];
  char tel[15];
  struct tnode *right;
};

/**   関数のプロトタイプ宣言  **/
int mktree(int, char * []);  //二分探索木を作る関数
void sort(struct tnode *);    //辞書順にソートする関数(再帰的)
int search(char [], char[]);
int insert(char [], char[]);

/**        変数の宣言        **/
char na[25], te[15]; //読み込んだ名前と電話番号を入れる配列
char scname[25],sctel[15];  //キーボードから名前を読み取る
FILE *fp;
struct tnode *root, *node, *old, *new;

/**        メイン関数         **/
int main(int argc, char *argv[])
{
  int no=0;
  mktree(argc,argv);

  while(1){
    printf("【二分探索木】\n"
           "検索する ===> 1\n"
           "追加する ===> 2\n"
           "削除する ===> 3\n"
           "表\示する ===> 4\n"
           "終了する ===> 5\n");

    scanf("%d",&no);
    switch (no){
    case 1:
      printf("\n【検索】\n");
      printf("●検索する名前を入力してください\n");
      scanf("%s",scname);
      printf("\n●検索する電話番号を入力してください\n");
      scanf("%s",sctel);
      search(scname,sctel);
      printf("\n");
      break;

    case 2:
      printf("\n【追加】\n");
      printf("●追加する名前を入力してください\n");
      scanf("%s",scname);
      printf("\n●追加する電話番号を入力してください\n");
      scanf("%s",sctel);
      insert(scname,sctel);
      printf("\n");
      break;

    case 3:
      printf("削除する名前を入力してください\n");
      printf("●削除する名前を入力してください\n");
      scanf("%s",scname);
      printf("\n");
      break;

    case 4:
      printf("二分探索木を表\示します\n");
      sort(root);
      printf("\n");
      break;

    case 5:
      printf("終了します\n");
      free(root);
      free(node);
      exit(0);
      break;

    default:
      printf("操作が間違っています\n");
      break;
    }
  }

    free(root);
    free(node);
    return 0;
}

/**      二分探索木を作成する関数        **/
int mktree(int argc, char *argv[])
{
  /*ファイルの指定*/
  if(argc!=2){
    printf("！注意！引数にファイル名を指定してください\a\n");
    exit(0);
  }

  /*ファイルを開くのに失敗したときの処理*/
  fp=fopen(argv[1],"r");
  if(fp==NULL){
    printf("！注意！ファイルを開けません\n");
    exit(0);
  }

  /*ルートノード*/
  root=(struct tnode *)malloc(sizeof(struct tnode));
  if(root==NULL){
    printf("！注意！メモリを確保できませんでした\a\n");
    exit(1);
  }

  /*木の作成*/
  while(fscanf(fp,"%s\t%s",na,te)!=-1){
    node=root;
    while(node!=NULL){
      old=node;
      if(strcmp(na,node->name)<=0)
        node=node->left;
      else
        node=node->right;
    }

    /*新しいノードの接続*/
    node=(struct tnode *)malloc(sizeof(struct tnode));
    if(node==NULL){
      printf("！注意！メモリを確保できませんでした\a\n");
      exit(1);
    }
    strcpy(node->name,na);
    strcpy(node->tel,te);
    node->left=node->right=NULL;
    if (strcmp(na,old->name)<=0)
      old->left=node;
    else
      old->right=node;
  }

  /*ファイルを閉じる*/
  close(fp);
  return 0;
}

/**    辞書順にソートし、出力する関数       **/
void sort(struct tnode *node){
  if(node!=NULL){
    sort(node->left);
    printf("%-25s%15s\n",node->name,node->tel);
    sort(node->right);
  }
}

/**   二分探索木からデータを検索する関数     **/
int search(char scname[], char sctel[])
{
    node=root;
    while(1){
      if(strcmp(scname,node->name)==0) break;
      if(strcmp(scname,node->name)<0){
        if(node->left==NULL) break;
        node=node->left;
      } else {
        if(node->right==NULL) break;
        node=node->right;
      }
    }

    if(strcmp(scname,node->name)==0){
       if(strcmp(sctel,node->tel)==0){
        printf("\n［結果］見つかりました\n\n");
      } else {
        printf("\n［結果］番号が違う可能\性があります\n\n");
      }
    }

    if(strcmp(scname,node->name)!=0){
      printf("\n［結果］見つかりませんでした\n\n");
    }
  return 0;
}


/**     二分探索木にデータを追加する関数      **/
int insert(char scname[], char sctel[])
{
  node=root;
  while(node!=NULL){
    old=node;
    if(strcmp(scname,node->name)==0){      //同じ名前があったときの処理
      printf("既に同じ名前があります\n");
      break;
    }

    if(strcmp(scname,node->name)<0){
      node=node->left;
    } else {
      node=node->right;
    }
  }

  node=(struct tnode *)malloc(sizeof(struct tnode));
  strcpy(node->name,scname);
  strcpy(node->tel,sctel);
  node->left=node->right=NULL;

  if(strcmp(scname,node->name)<0){
    old->left=node;
  } else {
    old->right=node;
  }
    return 0;
}
ページトップ
non
記事: 1097
登録日時: 15年前

Re: 二分探索木について

#4

投稿記事 by non » 15年前

このプログラムは２分木を作る部分（mktree関数）は本当に動いていますか？
１個目のnodeのleftとrightがnullになっていないのだけど。
non
ページトップ
閉鎖

“C言語何でも質問掲示板” へ戻る