C言語で書いてみました

■ 2分探索木（平成9年午後問9）

#include <stdio.h>

/* 一種 平成9年午後問9 */
/* 2分探索木 */
typedef struct _NODE {
    int Key;
    struct _NODE *P_Pointer;
    struct _NODE *L_Pointer;
    struct _NODE *R_Pointer;
} NODE;

NODE *t = NULL; /* ルートノードへのポインタ */

void insert(NODE *k)
{
    NODE *x, *w;
    
    if (t == NULL) {
        t = k; /* ルートノード */
        return;
    }
    
    x = t;
    while (x != NULL && k->Key != x->Key) {
        w = x;
        if (k->Key < x->Key) 
            x = x->L_Pointer;
        else
            x = x->R_Pointer;
    }
    if (x == NULL) {
        k->P_Pointer = w;
        if (k->Key < w->Key)
            w->L_Pointer = k;
        else
            w->R_Pointer = k;
    }
}

#define MAXSIZE 100
NODE *stack[MAXSIZE+1];
int top;

void push(NODE *x)
{
    if (top >= MAXSIZE) {
        puts("スタックが満杯です");
    } else {
        top++;
        stack[top] = x;
    }
}

NODE *pop(void)
{
    if (top <= 0) return NULL;
    top--;
    return stack[top+1];
}

void print(void)
{
    NODE *x = t;
    top = 0;
    while (1) {
        while (1) {
            push(x);
            x = x->L_Pointer;
            if (x == NULL) break;
        }
        while (1) {
            x = pop();
            printf("%d ", x->Key);
            x = x->R_Pointer;
            if (x != NULL || top == 0) break;
        }
        if (x == NULL && top == 0) break;
    }
    putchar('\n');
}

int main()
{
    int i, size;
    NODE k[] = {
        { 25, NULL, NULL, NULL },
        { 18, NULL, NULL, NULL },
        { 28, NULL, NULL, NULL },
        { 15, NULL, NULL, NULL },
        { 22, NULL, NULL, NULL },
        { 26, NULL, NULL, NULL },
        { 30, NULL, NULL, NULL },
        { 20, NULL, NULL, NULL },
        { 32, NULL, NULL, NULL },
    };

    size = sizeof(k) / sizeof(k[0]);
    for (i = 0; i<size; i++) insert(k+i);
    print();
    printf(" Address Key P-Pointer L-Pointer R-Pointer\n");
    for (i = 0; i < size; i++) {
        printf("%8x  %2d  %8x  %8x  %8x\n", 
            &(k[i]), k[i].Key, k[i].P_Pointer,
            k[i].L_Pointer, k[i].R_Pointer);
    }

    return 0;
}