ツリー構造をc言語で実装してみました。サンプルコードあり。

ツリー構造のデータ構造

構造体で下記のように表現しています。
各ノードには、値と左右のノードへのポインタを定義しています。

typedef struct node{
	int value;
	struct node* pLeftNode;
	struct node* pRightNode;
}node_t;

また、ツリー構造の先頭を定義するため、別途tree_tを定義しています。

typedef struct tree{
	node_t* pRootNode;
}tree_t;

ツリー構造の各関数

まずは、実際にツリーにノードを挿入する関数です。
ツリーの先頭から各ノードをたどって行き、登録されていなければ、新しくノードを作成してvalueを格納します。

挿入しようとしているvalueとノードのvalueを比較して、挿入しようとしているvalueが小さければ左のノードを、大きければ右のノードをたどって行きます。再帰関数で実現しています。

node_t* insertNode(node_t* pNode, int value){
		
	if(pNode == NULL){
		return initNode(value);
	}
	
	if(value == pNode->value){
		printf("already registered\n");
	}else if(value < pNode->value){
		pNode->pLeftNode = insertNode(pNode->pLeftNode, value);
	}else{
		pNode->pRightNode = insertNode(pNode->pRightNode, value);
	}
	
	return pNode; 
}

int insertNodeInTree(tree_t* pTree, int value){
	node_t* pNode = NULL;
	
	if(pTree == NULL){
		printf("arg chk error");
		return -1;
	}
	
	pTree->pRootNode = insertNode(pTree->pRootNode, value);
	printfTree(pTree);
	
	return 0;
}

下記は、ノードを実際に作成するサブ関数になります。
メモリを確保して、値を代入します。
終端ノードになるので、左右のノードへのポインタにはNULLを代入します。

node_t* initNode(int value){
	node_t* pNode = NULL;
	
	pNode = (node_t*)malloc(sizeof(node_t));
	if(pNode == NULL){
		printf("malloc error\n");
		return NULL;
	}
	pNode->value = value;
	pNode->pLeftNode = NULL;
	pNode->pRightNode = NULL;
	
	return pNode;
}

下記は、各ノードのメモリを解放する関数になります。
再帰関数で全てのノードを順にたどって行き、free()していきます。

void freeNode(node_t* pNode){
	if(pNode == NULL){
		return;
	}
	freeNode(pNode->pLeftNode);
	freeNode(pNode->pRightNode);
	free(pNode);
	
	return;
}

int freeNodeInTree(tree_t* pTree){
	if(pTree == NULL){
		printf("arg chk error");
		return -1;
	}
	freeNode(pTree->pRootNode);
	pTree->pRootNode = NULL;
	printfTree(pTree);
	
	return 0;
}

ツリーの中の最大値と階層レベルを表示する関数です。
ツリーの先頭から終端ノードに行き着くまで、右のノードをたどって行きます。
右終端ノードに最大値が格納されています。

int printfMaxAndLevel(tree_t* pTree){
	node_t* pNode = NULL;
	int level = 1;
	
	if(pTree == NULL){
		printf("arg chk error");
		return -1;
	}
	if(pTree->pRootNode == NULL){
		printf("No node\n");
		return -1;
	}
	
	pNode = pTree->pRootNode;
	while(pNode->pRightNode != NULL){
		pNode = pNode->pRightNode;
		level++;
	}
	printf("max=%d level=%d\n", pNode->value, level);
	
	return -1;
}

ツリーの中の最小値と階層レベルを表示する関数です。
ツリーの先頭から終端ノードに行き着くまで、左のノードをたどって行きます。
左終端ノードに最小値が格納されています。

int printfMinAndLevel(tree_t* pTree){
	node_t* pNode = NULL;
	int level = 1;
	
	if(pTree == NULL){
		printf("arg chk error");
		return -1;
	}
	if(pTree->pRootNode == NULL){
		printf("No node\n");
		return -1;
	}
	
	pNode = pTree->pRootNode;
	while(pNode->pLeftNode != NULL){
		pNode = pNode->pLeftNode;
		level++;
	}
	printf("min=%d level=%d\n", pNode->value, level);
	
	return -1;
}

下記は、ツリーに指定したvalueの値が格納されているノードが存在するかを表示する関数になります。
再帰関数で全てのノードをたどって行きます。

int findNode(node_t* pNode, int value){
	if(pNode == NULL){
		return -1;
	}
	
	if(value == pNode->value){
		return 0;
	}else if(value < pNode->value){
		return findNode(pNode->pLeftNode, value);
	}else{
		return findNode(pNode->pRightNode, value);
	}
}

int findNodeInTree(tree_t* pTree, int value){
	if(pTree == NULL){
		printf("arg chk error");
		return -1;
	}
	if(findNode(pTree->pRootNode, value) == 0){
		printf("existed\n");
	}else{
		printf("Not existed\n");
	}
	
	return 0;
}

スポンサーリンク

サンプルコード

下記がサンプルコードになります。

#include 
#include 

typedef struct node{
	int value;
	struct node* pLeftNode;
	struct node* pRightNode;
}node_t;

typedef struct tree{
	node_t* pRootNode;
}tree_t;

void printfNode(node_t* pNode){
	if(pNode == NULL){
		printf("No node\n");
		return;
	}
	
	printf("%d\n", pNode->value);
	printf("Left  ");
	printfNode(pNode->pLeftNode);
	printf("Right ");
	printfNode(pNode->pRightNode);
	
	return;
}

void printfTree(tree_t* pTree){
	if(pTree == NULL){
		printf("arg chk error");
		return;
	}
	printf("Root  ");
	printfNode(pTree->pRootNode);
	printf("\n");
	
	return;
}

tree_t* initTree(){
	tree_t* pTree = NULL;
	
	pTree = (tree_t*)malloc(sizeof(tree_t));
	if(pTree == NULL){
		printf("malloc error\n");
		return NULL;
	}
	pTree->pRootNode = NULL;
	
	return pTree;
}

node_t* initNode(int value){
	node_t* pNode = NULL;
	
	pNode = (node_t*)malloc(sizeof(node_t));
	if(pNode == NULL){
		printf("malloc error\n");
		return NULL;
	}
	pNode->value = value;
	pNode->pLeftNode = NULL;
	pNode->pRightNode = NULL;
	
	return pNode;
}

node_t* insertNode(node_t* pNode, int value){
		
	if(pNode == NULL){
		return initNode(value);
	}
	
	if(value == pNode->value){
		printf("already registered\n");
	}else if(value < pNode->value){
		pNode->pLeftNode = insertNode(pNode->pLeftNode, value);
	}else{
		pNode->pRightNode = insertNode(pNode->pRightNode, value);
	}
	
	return pNode; 
}

int insertNodeInTree(tree_t* pTree, int value){
	node_t* pNode = NULL;
	
	if(pTree == NULL){
		printf("arg chk error");
		return -1;
	}
	
	pTree->pRootNode = insertNode(pTree->pRootNode, value);
	printfTree(pTree);
	
	return 0;
}

void freeNode(node_t* pNode){
	if(pNode == NULL){
		return;
	}
	freeNode(pNode->pLeftNode);
	freeNode(pNode->pRightNode);
	free(pNode);
	
	return;
}

int freeNodeInTree(tree_t* pTree){
	if(pTree == NULL){
		printf("arg chk error");
		return -1;
	}
	freeNode(pTree->pRootNode);
	pTree->pRootNode = NULL;
	printfTree(pTree);
	
	return 0;
}

int printfMaxAndLevel(tree_t* pTree){
	node_t* pNode = NULL;
	int level = 1;
	
	if(pTree == NULL){
		printf("arg chk error");
		return -1;
	}
	if(pTree->pRootNode == NULL){
		printf("No node\n");
		return -1;
	}
	
	pNode = pTree->pRootNode;
	while(pNode->pRightNode != NULL){
		pNode = pNode->pRightNode;
		level++;
	}
	printf("max=%d level=%d\n", pNode->value, level);
	
	return -1;
}

int printfMinAndLevel(tree_t* pTree){
	node_t* pNode = NULL;
	int level = 1;
	
	if(pTree == NULL){
		printf("arg chk error");
		return -1;
	}
	if(pTree->pRootNode == NULL){
		printf("No node\n");
		return -1;
	}
	
	pNode = pTree->pRootNode;
	while(pNode->pLeftNode != NULL){
		pNode = pNode->pLeftNode;
		level++;
	}
	printf("min=%d level=%d\n", pNode->value, level);
	
	return -1;
}

int findNode(node_t* pNode, int value){
	if(pNode == NULL){
		return -1;
	}
	
	if(value == pNode->value){
		return 0;
	}else if(value < pNode->value){
		return findNode(pNode->pLeftNode, value);
	}else{
		return findNode(pNode->pRightNode, value);
	}
}

int findNodeInTree(tree_t* pTree, int value){
	if(pTree == NULL){
		printf("arg chk error");
		return -1;
	}
	if(findNode(pTree->pRootNode, value) == 0){
		printf("existed\n");
	}else{
		printf("Not existed\n");
	}
	
	return 0;
}

int main(){
	tree_t* pTree = NULL;	
	
	pTree = initTree();
	
	insertNodeInTree(pTree, 2);
	insertNodeInTree(pTree, 3);
	insertNodeInTree(pTree, 1);
	insertNodeInTree(pTree, 6);
	insertNodeInTree(pTree, 5);
	insertNodeInTree(pTree, 5);
	
	printfMinAndLevel(pTree);
	printfMaxAndLevel(pTree);
	findNodeInTree(pTree, -1);
	findNodeInTree(pTree, 6);
	freeNodeInTree(pTree);
	
	return 0;
}

下記が実行結果になります。

 $ gcc -o sample sample.c
 $ ./sample 
Root  2
Left  No node
Right No node

Root  2
Left  No node
Right 3
Left  No node
Right No node

Root  2
Left  1
Left  No node
Right No node
Right 3
Left  No node
Right No node

Root  2
Left  1
Left  No node
Right No node
Right 3
Left  No node
Right 6
Left  No node
Right No node

Root  2
Left  1
Left  No node
Right No node
Right 3
Left  No node
Right 6
Left  5
Left  No node
Right No node
Right No node

already registered
Root  2
Left  1
Left  No node
Right No node
Right 3
Left  No node
Right 6
Left  5
Left  No node
Right No node
Right No node

min=1 level=2
max=6 level=3
Not existed
existed
Root  No node