c言語_三分木を実装する

main.c

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


#define NAME 32
#define TRUE 1
#define LEFT -1
#define MIDDLE 0
#define RIGHT 1


typedef void(*DISPLAY)(void*);
typedef int(*COMPARE)(void*, void*);
typedef struct _tree3{
    void *data;
    struct _tree3 *left;
    struct _tree3 *middle;
    struct _tree3 *right;
}TriNode;
typedef struct _employee{
    char name[NAME];
    unsigned char age;
}Employee;


int compareEmployee(Employee *e1, Employee *e2){
    if ((e1->age) > (e2->age)) {
        return LEFT;
    } else if ((e1->age)==(e2->age)){
        return MIDDLE;
    } else {
        return RIGHT;
    }
}


void displayEmployee(Employee* employee){
    printf("%s\t%d\n", employee->name, employee->age);
}


void insertTriNode(TriNode **Root, COMPARE compare, void *data){

    TriNode *node = (TriNode*) malloc(sizeof(TriNode));
    node->data=data;
    node->left=NULL;
    node->middle=NULL;
    node->right=NULL;

    TriNode *root= *Root;

    if(root==NULL){
        *Root=node;
        return;
    }

    while(TRUE){
        if(compare((root)->data, data)==LEFT){
            if ((root)->left != NULL) {
                root = (root)->left;
            } else {
                (root)->left = node;
                break;
            }
        } else if(compare((root)->data, data)==MIDDLE){
            if ((root)->middle != NULL) {
                root = (root)->middle;
            } else {
                (root)->middle = node;
                break;
            }
        } else {
            if ((root)->right != NULL) {
                root = (root)->right;
            } else {
                (root)->right = node;
                break;
            }
        }
    }
}


void inOrder(TriNode *root, DISPLAY display){
    if (root != NULL){
        inOrder(root->left, display);
        display(root->data);
        inOrder(root->middle, display);
        inOrder(root->right, display);
    }
}


int main(int argc, const char *argv[]) {

    Employee *suzuki = (Employee*)malloc(sizeof(Employee));
    strcpy(suzuki->name, "suzuki");
    suzuki->age = 25;

    Employee *tanaka = (Employee*)malloc(sizeof(Employee));
    strcpy(tanaka->name, "tanaka");
    tanaka->age = 15;

    Employee *asa = (Employee*)malloc(sizeof(Employee));
    strcpy(asa->name, "asa");
    asa->age = 18;

    Employee *unko = (Employee*)malloc(sizeof(Employee));
    strcpy(unko->name, "unko");
    unko->age = 10;

    TriNode *tree = NULL;
    insertTriNode(&tree, (COMPARE)compareEmployee, suzuki);
    insertTriNode(&tree, (COMPARE)compareEmployee, tanaka);
    insertTriNode(&tree, (COMPARE)compareEmployee, asa);
    insertTriNode(&tree, (COMPARE)compareEmployee, unko);

    inOrder(tree, (DISPLAY) displayEmployee);

}

実行結果：

main.o

unko    10
tanaka  15
asa     18
suzuki  25

　
三分木型のデータ構造を持つ構造体TriNodeは、各ノードに構造体Employeeのポインタをデータとして保持する。

関数insertTriNodeは、構造体TriNodeのノードへ新たに構造体Employeeを追加する。追加される構造体Employeeが左・真ん中・右のどの枝に属するかは、関数compareEmployeeによって決まる。

関数inOrderは通りがけ順で、構造体TriNodeの各Nodeに属する構造体Employeeが保持しているデータ(nameとage)を表示する。
　
参考：

詳説Cポインタ　

　
　
　
どやっ！