二分探索木について
Posted: 2011年2月17日(木) 17:36
二分探索木に対して、新しいデータを挿入する関数、削除する関数、および、データを検索する関数を作成したいのですが新しいデータの挿入とデータの削除がわかりません。
新しいデータの挿入は一応挿入できているのですが、正しく二分探索木に
挿入されていないほか、上書きされてしまう場合もあります。
削除する関数は色々調べながら書いてたら、ごちゃごちゃになってしまって
どうしていいかわからなくなってしまいました。
どなたかアドバイスまたは解法を教えていただけないでしょうか。
どうかよろしくお願いします。
新しいデータの挿入は一応挿入できているのですが、正しく二分探索木に
挿入されていないほか、上書きされてしまう場合もあります。
削除する関数は色々調べながら書いてたら、ごちゃごちゃになってしまって
どうしていいかわからなくなってしまいました。
どなたかアドバイスまたは解法を教えていただけないでしょうか。
どうかよろしくお願いします。
/** ヘッダファイル **/
#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; /* コピーしておいたアドレスを返す */
}