多分木データ構造は様々な応用分野で利用されますが、実装方法は使用目的によって大きく異なります。本実装は組み込みシステム向けに設計されたシンプルな多分木で、スレッド管理などの用途を想定しています。

データ構造定義

#define MAX_CHILDREN 32
#define NODE_NAME_LENGTH 32

typedef struct tree_node {
    long identifier;
    struct tree_node* parent_ptr;
    int child_count;
    struct tree_node* child_nodes[MAX_CHILDREN];
    void* user_data;
} tree_node_t;

typedef struct node_list {
    tree_node_t* node_data;
    struct node_list* next_ptr;
} node_list_t;

typedef int (*name_callback_t)(long id, char* name_buffer);

typedef struct tree_structure {
    tree_node_t root_node;
    char initialized;
    int stack_index;
    char stack_data[MAX_CHILDREN][NODE_NAME_LENGTH];
    T_hSemaphore semaphore_lock;
    name_callback_t name_callback;
} tree_structure_t;

主要API関数

tree_node_t* find_tree_node(tree_structure_t* tree, long target_id);
int insert_child_node(tree_structure_t* tree, long parent_id, long child_id);
int insert_sibling_node(tree_structure_t* tree, long sibling_id, long new_id);
int remove_tree_node(tree_structure_t* tree, long target_id);
tree_structure_t* create_tree(void);
int initialize_tree(tree_structure_t* tree, long root_id, name_callback_t callback);
node_list_t* convert_tree_to_list(tree_structure_t* tree, long start_id);
node_list_t* get_child_nodes_list(tree_structure_t* tree, long parent_id);
int print_tree_linear(tree_structure_t* tree, long start_id);
int print_tree_hierarchical(tree_structure_t* tree, long start_id);

ノード操作の実装例

static tree_node_t* create_new_node(void) {
    tree_node_t* new_node = (tree_node_t*)memory_allocate(sizeof(tree_node_t));
    new_node->child_count = 0;
    memset(new_node->child_nodes, 0, MAX_CHILDREN * sizeof(tree_node_t*));
    return new_node;
}

static tree_node_t* recursive_node_search(tree_node_t* current_node, long target_id) {
    tree_node_t* result = NULL;
    
    if (current_node != NULL) {
        if (target_id == current_node->identifier) {
            result = current_node;
        } else {
            for (int i = 0; i < current_node->child_count && result == NULL; i++) {
                result = recursive_node_search(current_node->child_nodes[i], target_id);
            }
        }
    }
    return result;
}

ツリー表示機能

この実装では2種類の表示方法を提供します：

• 線形表示: ノードを連鎖的に表示
• 階層表示: インデントを使って木構造を視覚的に表現

static void display_node_hierarchical(tree_structure_t* tree, tree_node_t* node) {
    char node_name[16];
    char prefix[8];
    
    get_node_name(tree, node->identifier, node_name);
    prefix[0] = '\0';
    
    // 階層表示のためのプレフィックス生成
    if (tree->stack_index > 0) {
        tree_node_t* parent = node->parent_ptr;
        int prefix_index = 0;
        
        if (node == parent->child_nodes[0]) {
            prefix[prefix_index] = '-';
            tree->stack_data[tree->stack_index][prefix_index++] = '|';
        } else if (node == parent->child_nodes[parent->child_count - 1]) {
            prefix[prefix_index] = '`';
            tree->stack_data[tree->stack_index][prefix_index++] = ' ';
        } else {
            prefix[prefix_index] = '|';
            tree->stack_data[tree->stack_index][prefix_index++] = '|';
        }
        prefix[prefix_index] = '-';
        tree->stack_data[tree->stack_index][prefix_index++] = ' ';
    }
    
    // 表示処理の続き...
}