C 言語のアルゴリズムでは、初歩として勉強する二分木 (Binary Tree)。
思い返してみたら、実は一度もソースコードを書いたことがない。いくら何年もプログラム書いてるからって、それはないだろう! といふことでサンプル・コードを書いてみた。
/**********************************************************************************/
/* Sample Source of Binary Tree */
/**********************************************************************************/
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
struct node* left;
struct node* right;
int count;
int num;
} node_t;
static node_t* add_node(node_t* node, int num)
{
if (node == NULL){
node = (node_t*)malloc(sizeof(node_t));
if (node == NULL){
fprintf(stderr, "No nodes\n");
exit(1);
}
/* Set data */
node->num = num;
/* Child node is not available. */
node->left = node->right = NULL;
node->count = 1;
} else {
if (num < node->num){
node->left = add_node(node->left, num);
} else if (num > node->num) {
node->right = add_node(node->right, num);
} else {
node->count++;
}
}
return node;
}
static node_t* make_btree(int num[], int n, node_t* node)
{
for (int i=0; i<n; i++){
node = add_node(node, num[i]);
}
return node;
}
static void print_btree(node_t* node)
{
if (node == NULL){
return;
}
print_btree(node->left);
printf("%d(%d), ", node->num, node->count);
print_btree(node->right);
}
#if DEBUG
int main(void)
{
int n[] = { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, };
int m[] = { 1, 1, 1, 3, 5, 9, 17, 31, 57, };
node_t* nodes = NULL;
nodes = make_btree(n, sizeof(n)/sizeof(int), nodes);
nodes = make_btree(m, sizeof(m)/sizeof(int), nodes);
print_btree(nodes);
printf("\n");
return 0;
}
#endif /* DEBUG */
数字を二分木に追加していって、その重複度を数えるプログラム。
実行例はこの通り。
$ make gcc -W -Wall -g -O2 -std=c99 -DDEBUG -c -o btree.o btree.c gcc -W -Wall -g -O2 -std=c99 -DDEBUG -o btree btree.o $ ./btree 1(5), 2(1), 3(2), 5(2), 8(1), 9(1), 13(1), 17(1), 21(1), 31(1), 34(1), 55(1), 57(1),
与えた引数は、フィボナッチ数列とトリポナッチ数列の最小の数項。1 が 5 回。3 と 5 が 2 回。それ以外の数字は 1 回ずつ現れているのが見てとれる。
Source Codes
ソースコードの一式 (Makefile 含む) は、gist に上げてある。
git clone git://gist.github.com/375570.git btree
もしよければ、改変などご自由に。
参考文献
参考にはしたけれど、分かりにくい本なのであまりお勧めできない。
![Software Design ( ソフトウェアデザイン ) 2010年 05月号 [雑誌]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vVqMcdNs-zbZoo7UZDaWgYMKAbZQlNEXPzfo9_oPktV6jzYs58WAqPfc3Aa3N51mFQk247HhJxo0EZ0e3mvTUnN_UPbP6fow0gRmJlGy8yRBDInjCwk-c=s0-d)
