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

typedef struct tree {
    int data;
    struct tree *prevPtr;
    struct tree *nextPtr;
} BTREE;

BTREE *insert(BTREE *Btree, int data);

void inOrder(BTREE *Btree);
void preOrder(BTREE *Btree);
void postOrder(BTREE *Btree);

void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int main(void)
{
    int i, item;
    BTREE *tmpPtr, *rootPtr = NULL;
    int data[15];
    tmpPtr = rootPtr;

    srand(time(NULL));

    for (i=0; i<15; i++){
	data[i]=i+1;
    }
    for (i=0; i<15; i++){
    	item = i + rand() % (15 - i);
	swap(&data[i], &data[item]);
    }

    printf("2分木に挿入する値:\n");
    for (i=0; i<15; i++) {
	printf("%3d", data[i]);
	rootPtr = insert(rootPtr, data[i]);
    }
    printf("\n\n先順走査\n");
    preOrder(rootPtr);

    printf("\n\n中順走査\n");
    inOrder(rootPtr);

    printf("\n\n後順走査\n");
    postOrder(rootPtr);
    printf("\n");

    return 0;
}

BTREE *insert(BTREE *treePtr, int val)
{
    if (treePtr == NULL) {
	treePtr = (BTREE *)malloc(sizeof(BTREE));
	if (treePtr != NULL) {
	    treePtr->data = val;
	    treePtr->prevPtr = NULL;
	    treePtr->nextPtr = NULL;
	} else {
	    printf("メモリ不足で %d を挿入できません\n", val);
	}
    } else {
	if ( val < treePtr->data ) {
	    treePtr->prevPtr = insert(treePtr->prevPtr, val);
	} else if ( val > treePtr->data ) {
	    treePtr->nextPtr = insert(treePtr->nextPtr, val);
	} else {
	    printf("重複\n");
	}
    }
    return treePtr;
}

void preOrder(BTREE *treePtr)
{
    if (treePtr != NULL) {
	printf("%3d", treePtr->data);
	inOrder(treePtr->prevPtr);
	inOrder(treePtr->nextPtr);
    }
}

void postOrder(BTREE *treePtr)
{
    if (treePtr != NULL) {
	inOrder(treePtr->prevPtr);
	inOrder(treePtr->nextPtr);
	printf("%3d", treePtr->data);
    }
}    

void inOrder(BTREE *treePtr)
{
    if (treePtr != NULL) {
	inOrder(treePtr->prevPtr);
	printf("%3d", treePtr->data);
	inOrder(treePtr->nextPtr);
    }
}