二分探索木への挿入

質問

今学校で二分探索木を勉強しています。二分探索木に要素を挿入したいのですが、うまくいかないのでアドバイスをいただけないでしょうか。ファイル中の英文を単語に分けてその出現頻度をカウントするプログラムです。とりあえず二分探索木を作るところまではなんとか完成させたいです。

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

typedef struct node Node;
struct node{
char *word;
int count;
Node *left,*right;
};

Node *root=NULL;
Node *compose(FILE *fp);
void inorder(Node *p);

int main(int argc, char *argv[])
{
FILE *fp;
Node *new;

fp=fopen(argv[1],"r");
if(fp==NULL){
puts("ファイルを開けません");
return(-1);
}
new=(Node *)malloc(sizeof(Node *));
new=compose(fp);
inorder(new);
return (0);
}

Node *compose(FILE *fp)
{
Node **p,*new;
char buf[20];
p=&root;
while(fscanf(fp,"%[-a-z-A-Z0-9_]",buf)!=EOF){

while(*p!=NULL){
(*p)->count=0;　　/*countを０で初期化したいけどwhileの外にこの1行を出すとエラーが出る*/
buf[0]=tolower(buf[0]);
strdup(buf);
if(strcasecmp(buf,(*p)->word)==0){　　　/*if文にしかはいらない…*/
(*p)->count++;

printf("%d\n",(*p)->count);

}else if(strcasecmp(buf,(*p)->word)<0){
p=&(*p)->left;
}else{
p=&(*p)->right;
}
}
new=(Node *)malloc(sizeof(Node *));
new->left=NULL;
new->right=NULL;
new->word=buf;
*p=new;
fscanf(fp,"%*[^-a-z-A-Z0-9_]");
}
return(new);
}

void inorder(Node *p)
{
if(p==NULL)
return;

printf("%s",p->word);
if(p->count!=0){
printf("%d",p->count);
}
inorder(p->right);
inorder(p->left);

}

回答No.4

JaritenCat · ベストアンサー

なんとなく動くようにしてみました。参考にしていただければ。。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
typedef struct node Node;
struct node{
　char *word;
　int count;
　Node *left,*right;
};
Node *root=NULL;
void compose(FILE *fp);
void inorder(Node *p);
void strlower(char *s);

int main(int argc, char *argv[]) {
　FILE *fp;
　Node *new;

　fp=fopen(argv[1],"r");
　if(fp==NULL){ puts("ファイルを開けません"); return(-1); }
　compose(fp);
　inorder(root);
　return (0);
}
/* 文字列を小文字にする */
void strlower(char *s) {
　while(*s!=NULL) { *s=tolower(*s); s++; }
}
/* 木を作る */
void compose(FILE *fp) {
　Node **p,*new;
　char buf[256];
　while(1) {
　　fscanf(fp,"%[^a-zA-Z0-9]",buf); /* 英数字がくるまで読み飛ばす */
　　if (fscanf(fp,"%[a-zA-Z0-9]",buf)==EOF) break; /* ファイルから単語らしきものを読み込む */
　　strlower(buf); /* 文字列を小文字化 */
　　if (root==NULL) { /* 最初の単語ならすぐ登録 */
　　　new=(Node *)malloc(sizeof(Node));
　　　new->left=NULL; new->right=NULL; new->word=strdup(buf); new->count=1;
　　　root=new;
　　} else { /* 最初でなければ大小比較して挿入場所を探す */
　　　*p=root; /* 注目ノードを根に設定 */
　　　while(1){
　　　　if(strcmp(buf,(*p)->word)==0){ /* 同じデータがあればカウントアップして終わり */
　　　　　(*p)->count++; break;
　　　　} else if(strcmp(buf,(*p)->word)<0){ /* 新単語が小さければ左を見る */
　　　　　if ((*p)->left==NULL) { /* 子がなければ新規登録 */
　　　　　　new=(Node *)malloc(sizeof(Node));
　　　　　　new->left=NULL; new->right=NULL; new->word=strdup(buf); new->count=1;
　　　　　　(*p)->left=new; break;
　　　　　} else { /* 左を探す */
　　　　　　*p=(*p)->left;
　　　　　}
　　　　} else { /* 新単語が大きければ右を見る */
　　　　　if ((*p)->right==NULL) { /* 子がなければ新規登録 */
　　　　　　new=(Node *)malloc(sizeof(Node));
　　　　　　new->left=NULL; new->right=NULL; new->word=strdup(buf); new->count=1;
　　　　　　(*p)->right=new; break;
　　　　　}else{ /* 右を探す */
　　　　　　*p=(*p)->right;
　　　　　}
　　　　}
　　　}
　　}
　}
}
/* 小さい順に表示 */
void inorder(Node *p) {
　if (p==NULL) return;
　inorder(p->left);
　printf("%s %d\n",p->word, p->count);
　inorder(p->right);
}

お礼

お礼が遅くなってしまい申し訳ありません。
友人と相談して関数をもう一つ付け加えたら挿入できるようになりました。JaritenCatさんのソースもまた勉強の材料にさせていただきます。ありがとうございました！

回答No.3

asuncion

> if(strcasecmp(buf,(*p)->word)==0){　　　/*if文にしかはいらない…*/

構造体のメンバーwordには適切な値が入っていますか？

> *p=new;
> fscanf(fp,"%*[^-a-z-A-Z0-9_]");

ここのfscanf()の意味合いがわかりません。

回答No.2

Tacosan

変数 root の存在理由は?

補足

教科書にそう書いてあったのでそのまま参考にしました。

回答No.1

asuncion

「うまくいかない」とか「エラーが出る」というのは、
何をしたとき（コンパイル時？実行時？）に
どううまくいかなかったりどんなエラーが出たり（エラーメッセージは？）するのでしょうか。

補足

うまくいかないというのはソースコード内でコメントアウトしてあるやつのことです。わかりにくくてすみません。
(*p)->count=0;　をwhile文よりも前に置くと、実行時にwhich has no line number information.というエラー？が出ます。コンパイラはgccです。