日: 2015年6月23日

単純な二分木を使ったソート。
構造体で二分木を表現するのと、malloc() / free() の練習。

#include
#include

#define MAX 10

typedef struct tree {
    int value;
    struct tree *left;
    struct tree *right;
} Tree;

void PrintArray(int ary[]);
void BTreeSort(int ary[], const int n);
Tree *Insert(Tree *root, int val);
int Traverse(Tree *root, int ary[], int n);
void FreeTree(Tree *root);

int main(void)
{
    int i;
    int ary[MAX];
    Tree *root = NULL;

    srand((unsigned)time(NULL));

    for (i = 0; i < MAX; i++) {
        ary[i] = rand() % 100;
    }
    printf("unsorted: ");
    PrintArray(ary);
    BTreeSort(ary, MAX);
    printf("sorted: ");
    PrintArray(ary);

    return 0;
}

void PrintArray(int ary[])
{
    int i;

    for (i = 0; i < MAX; i++) {
        printf("%2d ", ary[i]);
    }
    printf("\n");
}

void BTreeSort(int ary[], const int n)
{
    int i;

    Tree *root = NULL;
    for (i = 0; i < n; i++) {
        root = Insert(root, ary[i]);
    }
    Traverse(root, ary, 0);
    FreeTree(root);
}

Tree *Insert(Tree *root, int val)
{
    if (root == NULL) {
        root = (Tree *)malloc(sizeof(Tree));
        root->value = val;
        root->left = NULL;
        root->right = NULL;
    } else {
        if (val < root->value) {
            root->left = Insert(root->left, val);
        } else {
            root->right = Insert(root->right, val);
        }
    }

    return root;
}

int Traverse(Tree *root, int ary[], int n)
{
    if (root->left != NULL) {
        n = Traverse(root->left, ary, n);
    }
    ary[n++] = root->value;
    if (root->right != NULL) {
        n = Traverse(root->right, ary, n);
    }

    return n;
}

void FreeTree(Tree *root)
{
    if (root == NULL) {
        return;
    } else {
        FreeTree(root->left);
        FreeTree(root->right);
        free(root);
        return;
    }
}

takatoh@nightschool $ ./btreesort
unsorted: 80 77 21 42 50 76 88 48 32 19 
sorted:   19 21 32 42 48 50 76 77 80 88