Binary Tree Sample

btree.c

/**********************************************************************************/
/* 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 */

Makefile

# Binary Tree sample program
#  Author: Masayuki Ataka  <[email protected]>
PROGRAM = btree

CC = gcc
CFLAGS = -W -Wall -g -O2 -std=c99
CPPFLAGS = -DDEBUG

all: $(PROGRAM)

$(PROGRAM): btree.o
	$(CC) $(CFLAGS) $(CPPFLAGS) -o $@ $^

btree.o: btree.c

#
# clean
#
RM = rm -f
clean:
	$(RM) *~
	$(RM) *.o

distclean: clean
	$(RM) $(PROGRAM)