Binary Tree を作ってみた

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 に上げてある。

• gist: 375570 - Binary Tree Sample- GitHub

git clone git://gist.github.com/375570.git btree

もしよければ、改変などご自由に。

参考文献

参考にはしたけれど、分かりにくい本なのであまりお勧めできない。