階層的なデータ構造（ツリー構造）は、親と子の関係を持つノードで構成されるデータ構造です。この解説では、C言語を使用してツリー探索を行う方法について説明します。

• ツリー構造の基本
• ツリー探索の基本
• 再帰的探索方法
• 反復的探索方法
• 具体的な例

ツリー構造の基本

ツリー構造は、以下のような特徴を持つデータ構造です：

• ルートノードが1つ存在します。
• 各ノードは1つの親ノードと0個以上の子ノードを持ちます。
• ノードはツリーの下層に分岐していきます。

典型的なツリー構造は二分木です。二分木は各ノードが最大で2つの子ノードを持つ木構造です。例えば、次のような二分木を考えます：

         1
        / \
       2   3
      / \   / \
     4   5 6   7
    

ツリー探索の基本

ツリー探索とは、ツリー構造内の全てのノードを訪問するプロセスです。ツリー探索には以下のような方法があります：

• 前順探索（Pre-order Traversal）
• 中順探索（In-order Traversal）
• 後順探索（Post-order Traversal）
• レベル順探索（Level-order Traversal）

それぞれの探索方法の順番は次の通りです：

• 前順探索：ノードを訪問 → 左の子ノード → 右の子ノード
• 中順探索：左の子ノード → ノードを訪問 → 右の子ノード
• 後順探索：左の子ノード → 右の子ノード → ノードを訪問
• レベル順探索：上から下に、左から右にノードを訪問

再帰的探索方法

再帰的なツリー探索は、親ノードを訪問した後、左または右の子ノードを再帰的に訪問する方法です。例えば、前順探索の再帰的な実装を考えてみましょう：

#include 

typedef struct Node {
    int value;
    struct Node* left;
    struct Node* right;
} Node;

void preOrderTraversal(Node* node) {
    if (node == NULL) return;
    printf("%d ", node->value);
    preOrderTraversal(node->left);
    preOrderTraversal(node->right);
}

int main() {
    Node root = {1, NULL, NULL};
    Node node2 = {2, NULL, NULL};
    Node node3 = {3, NULL, NULL};
    Node node4 = {4, NULL, NULL};
    Node node5 = {5, NULL, NULL};
    root.left = &node2;
    root.right = &node3;
    node2.left = &node4;
    node2.right = &node5;

    preOrderTraversal(&root);
    return 0;
}
    

このコードでは、ツリーを前順で探索し、ノードの値を表示します。

反復的探索方法

反復的な探索では、スタックやキューを使用してツリーを探索します。例えば、前順探索の反復的な実装は次のようになります：

#include 
#include 

typedef struct Node {
    int value;
    struct Node* left;
    struct Node* right;
} Node;

typedef struct Stack {
    Node* node;
    struct Stack* next;
} Stack;

void push(Stack** stack, Node* node) {
    Stack* newNode = (Stack*)malloc(sizeof(Stack));
    newNode->node = node;
    newNode->next = *stack;
    *stack = newNode;
}

Node* pop(Stack** stack) {
    if (*stack == NULL) return NULL;
    Stack* temp = *stack;
    Node* node = temp->node;
    *stack = (*stack)->next;
    free(temp);
    return node;
}

int isEmpty(Stack* stack) {
    return stack == NULL;
}

void iterativePreOrderTraversal(Node* root) {
    Stack* stack = NULL;
    push(&stack, root);
    while (!isEmpty(stack)) {
        Node* node = pop(&stack);
        if (node != NULL) {
            printf("%d ", node->value);
            push(&stack, node->right);
            push(&stack, node->left);
        }
    }
}

int main() {
    Node root = {1, NULL, NULL};
    Node node2 = {2, NULL, NULL};
    Node node3 = {3, NULL, NULL};
    Node node4 = {4, NULL, NULL};
    Node node5 = {5, NULL, NULL};
    root.left = &node2;
    root.right = &node3;
    node2.left = &node4;
    node2.right = &node5;

    iterativePreOrderTraversal(&root);
    return 0;
}
    

このコードでは、スタックを使って前順探索を反復的に行っています。

具体的な例

以下に、ツリー構造とその探索の具体例を示します。

         10
        /  \
       5   20
      / \   / \
     3   8 15 25
    

このツリーに対して前順探索を行うと、結果は「10 5 3 8 20 15 25」となります。

中順探索の場合、結果は「3 5 8 10 15 20 25」となります。

後順探索の場合、結果は「3 8 5 15 25 20 10」となります。