二分探索木を使った関数管理方法

前回

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

今回

前回は、文字列検索のアルゴリズムを追加しました。伴って、文字列検索アルゴリズムの実装の関数searchNodeForKey関数を追加しました。
今回は、関数ポインタを内包した構造体Helloを木構造で管理します。伴って、f関数,structHelloAllocate関数、in_struct関数、in_struct_at_delete関数を追加しました。また、treeWalk関数内を変更しました。
f関数では、「Hello.」をコンソールに出力しています。in_struct関数、in_struct_at_delete関数では、構造体Nodeに対して中の値を代入しています。

参考ページ

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

参考文献

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

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

準備

console

clang sample.c -o sample
./sample

もしくはオンラインコンパイラを使用します。
オンラインコンパイラ
Cコンパイラを使用します。

ソースコード

sample.c

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

typedef struct Hello{
	long i;
	struct Hello* (*u)(struct Hello*);
}Hello;

typedef struct Hello* (*fupo)(struct Hello*);

Hello* f(Hello* v){
	printf("Hello.%ld.¥n",v->i);
	return v;
}

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

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

Hello* structHelloAllocate(){
	return (Hello*)malloc(sizeof(Hello));
}

Node* in_struct(Node *new_node,long insert_data, char *key,long type, void *data){
	new_node->i = insert_data;
	strcpy(new_node->key,key);
	new_node->type=type;
	new_node->data=data;
	new_node->left = NULL;
	new_node->right = NULL;
	return new_node;
}

Node* in_struct_at_delete(Node *root,Node *temp){
	root->i = temp->i;
	strcpy(root->key,temp->key);
	root->type=temp->type;
	root->data=temp->data;
	return root;
}

Node* insertNode(Node* pNode, long insert_data, char *key,long type, void *data) {
	if (pNode == NULL) {
		Node* new_node = treeAllocate();
		in_struct(new_node,insert_data,key,type,data);
		return new_node;
	}
	if (insert_data < pNode->i) {
		pNode->left = insertNode(pNode->left, insert_data,key,type,data);
	} else if (insert_data > pNode->i) {
		pNode->right = insertNode(pNode->right, insert_data,key,type,data);
	}
	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);
		in_struct_at_delete(root,temp);
		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);
	if(root->type==0){
		printf("%ld \n", ((Hello*)root->data)->i);
		((Hello*)root->data)->u((Hello*)root->data);
	}
	walkNode(root->right);
}

int main(void){
	Hello lo[10];
	long i=0;
	for(i=0;i<10;i++){
		lo[i].i=i;
		lo[i].u=f;
	}
	long type=0;
	Node* root = NULL;
	root = insertNode(root, 7,"Cho", type, (void*)   &lo[0]);
	root = insertNode(root, 2,"Chie", type, (void*)  &lo[1]);
	root = insertNode(root, 1,"Chroe", type, (void*) &lo[2]);
	root = insertNode(root, 0,"Mike", type, (void*)  &lo[3]);
	root = insertNode(root, 5,"Michel", type, (void*)&lo[4]);
	root = insertNode(root, 3,"Rooter", type, (void*)&lo[5]);
	root = insertNode(root, 4,"Yuki", type, (void*)  &lo[6]);
	root = insertNode(root, 6,"Ayaka", type, (void*) &lo[7]);
	root = insertNode(root, 8,"Aki", type, (void*)   &lo[8]);
	root = insertNode(root, 9,"Yuji", type, (void*)  &lo[9]);

	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 
3 
Hello.3.¥n1,Chroe 
2 
Hello.2.¥n2,Chie 
1 
Hello.1.¥n3,Rooter 
5 
Hello.5.¥n4,Yuki 
6 
Hello.6.¥n5,Michel 
4 
Hello.4.¥n6,Ayaka 
7 
Hello.7.¥n7,Cho 
0 
Hello.0.¥n8,Aki 
8 
Hello.8.¥n9,Yuji 
9 
Hello.9.¥n
pre＿order: 0,Mike 
3 
Hello.3.¥n1,Chroe 
2 
Hello.2.¥n3,Rooter 
5 
Hello.5.¥n4,Yuki 
6 
Hello.6.¥n5,Michel 
4 
Hello.4.¥n6,Ayaka 
7 
Hello.7.¥n7,Cho 
0 
Hello.0.¥n8,Aki 
8 
Hello.8.¥n9,Yuji 
9 
Hello.9.¥n7
1
0,Mike 
3 
Hello.3.¥n1,Chroe 
2 
Hello.2.¥n3,Rooter 
5 
Hello.5.¥n4,Yuki 
6 
Hello.6.¥n5,Michel 
4 
Hello.4.¥n6,Ayaka 
7 
Hello.7.¥n8,Aki 
8 
Hello.8.¥n9,Yuji 
9 
Hello.9.¥n1
1
Not Found.
0,Mike