二分探索木の実装

参考文献

改訂第4版 C言語によるはじめてのアルゴリズム入門　2017年11月25日
河西朝雄　著

準備

console

gcc sample.c -o sample
./sample

ソースコード

sample.c

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

typedef struct Node{
	struct Node *left;
	struct Node *right;
	char data[12];
}Node;

Node* tree_allocate();

double drand()
{
	double rndno=0.0;/*生成した乱数*/
	
	while((rndno=(double)rand()/RAND_MAX)==1.0);
	rndno=rndno*2-1 ;/*-1から1の間の乱数を生成*/
	return rndno;
}

Node* tree_allocate(){
	return (Node*)malloc(sizeof(Node));
}

Node* generate_tree(Node *p,char *w){
	if(p==NULL){
		p=tree_allocate();
		strcpy(p->data,w);
		p->left=p->right=NULL;
	}
	else if(strcmp(w,p->data)<0){
		p->left=generate_tree(p->left,w);
	}
	else {
		p->right=generate_tree(p->right,w);
	}
	return p;
}

Node* search(Node *p,char *key){
	if(p==NULL||strcmp(key,p->data)==0){
		return p;
	}
	if(strcmp(key,p->data)<0){
		return search(p->left,key);
	}
	else {
		return search(p->right,key);
	}
}

void tree_walk(Node *p){
	
	if(p!=NULL){
		tree_walk(p->left);
		tree_walk(p->right);
		printf("%s \n",p->data);
		
	}
}

int main() {
	char dat[12];
	Node *root;
	root=NULL;
	while(scanf("%s",dat)!=EOF){
		root=generate_tree(root,dat);
	}
	Node *q=search(root,"Cho");
	if(q!=NULL){
		printf("%s \n",q->data);
	}
	else {
		printf("Not Found. \n");
	}
	
	tree_walk(root);
	
	return 0;
}

実行結果

console1

Eos    
Cho
Michel
Chroe
Karen
Lisa
Yamato
Ligree
Ken
Chroe 
Cho 
Chroe 
Chroe 
Cho 
Ken 
Ligree 
Lisa 
Karen 
Yamato 
Michel 
Eos 

console2

Michel 
Chroe
Karen
Lisa
Yamato
Ligree
Ken
Chroe
Not Found. 
Chroe 
Ken 
Ligree 
Lisa 
Karen 
Chroe 
Yamato 
Michel