C言語で書いてみました

■ 2分探索木（平成18年秋午後1問5）

/*
 *  ソフトウェア開発技術者
 *  平成18年度秋午後1問5
 *
 *  2分探索木
 *
 */

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

#define SAIKI   1

#define TRUE    1
#define FALSE   0

typedef struct tag_node {
    int value;
    struct tag_node *left;
    struct tag_node *right;
} node;

int lookup(int x, node *t)
{
#if SAIKI==0
    while (t != NULL) {
        if (x == t->value)
            return TRUE;
        else {
            if (x < t->value)
                t = t->left;
            else
                t = t->right;
        }
    }
    return FALSE;
#else /* 再帰呼出し法 */
    if (t == NULL)
        return FALSE;
    if (x == t->value)
        return TRUE;
    else {
        if (x < t->value)
            return lookup(x, t->left);
        else
            return lookup(x, t->right);
    }
#endif
}

node *insert(int x, node *t)
{
    if (t == NULL) {
        t = (node *)malloc(sizeof(node));
        t->value = x;
        t->left = NULL;
        t->right = NULL;
    } else {
        if (x < t->value)
            t->left = insert(x, t->left);
        else if (x > t->value)
            t->right = insert(x, t->right);
    }
    return t;
}

/* 表示 */
void print(node *t)
{
    if (t == NULL) {
        printf("N ");
        return;
    }
    printf("%d ", t->value);
    print(t->left);
    print(t->right);
}

/* テスト */
int main()
{
    int i, data[] = { 20, 8, 2, 15, 36, 53, 78, 64 };
    node root = { 44, NULL, NULL };

    for (i = 0; i < sizeof(data)/sizeof(int); i++)
        insert(data[i], &root);

    /* 設問1 */
    insert(40, &root);
    insert(34, &root);
    insert(38, &root);
    print(&root);

    return 0;
}