二分探索木の文字列検索の実装

前回

二分探索木の実装と削除の実装

今回

前回は、二分探索木の削除アルゴリズムを追加しました。伴って、前々回の設計から大幅に変更しました。
今回は、文字列検索のアルゴリズムを追加しました。文字列検索アルゴリズムの実装は、searchNodeForKey関数にまとまっています。

参考ページ

サメベース. SAMEBASE
【[C言語]二分探索木から要素を削除する関数の実装[コード付]】

参考文献

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

［改訂新版］C言語による標準アルゴリズム事典
奥村晴彦　著

準備

console

gcc sample.c -o sample
./sample

ソースコード

sample.c

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

typedef struct Node {
	long i;
	char key[12];
	struct Node* left;
	struct Node* right;
} Node;

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

Node* insertNode(Node* pNode, long insert_data, char *key) {
	if (pNode == NULL) {
		Node* new_node = treeAllocate();
		new_node->i = insert_data;
		strcpy(new_node->key,key);
		new_node->left = NULL;
		new_node->right = NULL;
		return new_node;
	}
	if (insert_data < pNode->i) {
		pNode->left = insertNode(pNode->left, insert_data,key);
	} else if (insert_data > pNode->i) {
		pNode->right = insertNode(pNode->right, insert_data,key);
	}
	return pNode;
}

Node* findMin(Node* node) {
	Node* current = node;
	while (current && current->left != NULL)
		current = current->left;
	return current;
}

Node* deleteNode(Node* root, long key) {
	if (root == NULL)
		return root;
	if (key < root->i)
		root->left = deleteNode(root->left, key);
	else if (key > root->i)
		root->right = deleteNode(root->right, key);
	else {
		if (root->left == NULL) {
			Node* temp = root->right;
			free(root);
			return temp;
		}
		else if (root->right == NULL) {
			Node* temp = root->left;
			free(root);
			return temp;
		}
		Node* temp = findMin(root->right);
		root->i = temp->i;
		strcpy(root->key,temp->key);
		root->right = deleteNode(root->right, temp->i);
	}
	return root;
}

Node* searchNode(Node* pNode, long search_data) {
	if (pNode == NULL || pNode->i == search_data) {
		return pNode;
	}
	if (search_data < pNode->i) {
		return searchNode(pNode->left, search_data);
	} else {
		return searchNode(pNode->right, search_data);
	}
}

Node* searchNodeForKey(Node *q,char *key){
	Node *p=q;
	if(p!=NULL){
		
		if(strcmp(p->key,key)==0){
			return p;
		}
	
		p=searchNodeForKey(p->left,key);
		if(p!=NULL){
			return p;
		}
		else{
			p=q;
		}
		
		p=searchNodeForKey(p->right,key);
		if(p!=NULL){
			return p;
		}
		else{
			return NULL;
		}
	}
	else{
		return NULL;
	}
	return q;
}

void walkNode(Node* root) {
	if (root == NULL) {
		return;
	}
	walkNode(root->left);
	printf("%ld,", root->i);
	printf("%s \n", root->key);
	walkNode(root->right);
}

int main(void){
	Node* root = NULL;
	root = insertNode(root, 7,"Cho");
	root = insertNode(root, 2,"Chie");
	root = insertNode(root, 1,"Chroe");
	root = insertNode(root, 0,"Mike");
	root = insertNode(root, 5,"Michel");
	root = insertNode(root, 3,"Rooter");
	root = insertNode(root, 4,"Yuki");
	root = insertNode(root, 6,"Ayaka");
	root = insertNode(root, 8,"Aki");
	root = insertNode(root, 9,"Yuji");

	printf("\npre＿order: ");
	walkNode(root);
	root = deleteNode(root, 2);
	printf("\npre＿order: ");
	walkNode(root);
	printf("%ld\n",root->i);
	root = deleteNode(root, 7);
	printf("1\n");
	walkNode(root);
	printf("1\n");
	Node* find_node=NULL;
	printf("1\n");
	find_node=searchNodeForKey(root,"Ayataka");
	if(find_node!=NULL){
		printf("%ld,%s\n",find_node->i,find_node->key);
	}else{
		printf("Not Found.\n");
	}
	
	find_node=searchNodeForKey(root,"Mike");
	if(find_node!=NULL){
		printf("%ld,%s\n",find_node->i,find_node->key);
	}else{
		printf("Not Found.\n");
	}
	
	
	return 0;
}

実行結果

console1

pre＿order: 0,Mike 
1,Chroe 
2,Chie 
3,Rooter 
4,Yuki 
5,Michel 
6,Ayaka 
7,Cho 
8,Aki 
9,Yuji 

pre＿order: 0,Mike 
1,Chroe 
3,Rooter 
4,Yuki 
5,Michel 
6,Ayaka 
7,Cho 
8,Aki 
9,Yuji 
7
1
0,Mike 
1,Chroe 
3,Rooter 
4,Yuki 
5,Michel 
6,Ayaka 
8,Aki 
9,Yuji 
1
1
Not Found.
0,Mike