(修正)C言語 二分探索木
Posted: 2013年7月27日(土) 00:18
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node_type{
char *data;
struct node_type *left;
struct node_type *right;
};
struct node_type *root;
char buff[128];
void insert(struct node_type *pt,char *word){
char *data;
if(pt == NULL){
pt = (struct node_type *)malloc(sizeof(struct node_type));
pt->data = (char *)malloc(sizeof(char)*(strlen(word)+1));
pt->left = NULL;
pt->right = NULL;
strcpy(pt->data,word);
root = pt->data;
printf("%s\n",pt->data);
printf("根を作る%s\n",root);
return;
}
//printf("%s\n",pt);
data = pt;
printf("root = %s\n",data);
printf("pt->left== %d\n",pt->left);
printf("pt->right== %d\n",pt->right);
if(strcmp(data,word) == 0){
printf("同じ文字\n");
return;
}
if(strcmp(data,word) < 0){
if(pt->right != NULL){
printf("右の子へ\n");
insert(pt->right,word);
return;
}
else{
pt = (struct node_type *)malloc(sizeof(struct node_type));
pt->data = (char *)malloc(sizeof(char)*(strlen(word)+1));
strcpy(pt->data,word);
pt->right = pt->data;
printf("右の子作成%s\n",pt->right);
return;
}
}
if(strcmp(data,word) > 0){
if(pt->left != NULL){
printf("左の子へ\n");
insert(pt->left,word);
return;
}
else {
pt = (struct node_type *)malloc(sizeof(struct node_type));
pt->data = (char *)malloc(sizeof(char)*(strlen(word)+1));
strcpy(pt->data,word);
pt->left = pt->data;
printf("左の子作成%s\n",pt->left);
return;
}
}
return;
}
int count(struct node_type *pt){
if(pt==NULL)
return 0;
else
return count(pt->left)+count(pt->right)+1;
}
int main(){
int nodes;
root = NULL;
while(scanf("%s",buff) != EOF){
insert(root,buff);
}
nodes = count(root);
printf("%d\n",nodes);
exit(0);
}
入力単語:this is my pen your pen is over there
実行結果:
this
根を作るthis
root = this
pt->left== (null)
pt->right== (null)
左の子作成is
root = this
pt->left== (null)
pt->right== is
左の子作成my
root = this
pt->left== (null)
pt->right== is
左の子作成pen
root = this
pt->left== (null)
pt->right== is
右の子へ
root = is
pt->left== (null)
pt->right== my
右の子へ
root = my
pt->left== (null)
pt->right== pen
右の子へ
root = pen
pt->left== (null)
pt->right== (null)
右の子作成your
root = this
pt->left== (null)
pt->right== is
左の子作成pen
root = this
pt->left== (null)
pt->right== is
左の子作成is
root = this
pt->left== (null)
pt->right== is
左の子作成over
root = this
pt->left== (null)
pt->right== is
左の子作成there
9
といったように、根をthisとして次のisが左の子として作成しているのにpt->rightに入ってます。
どうしてこうなるんでしょうか？
また型についてもどうすれば良いか教えて頂きたいです。