データ構造 - ツリー

ツリー（Tree）は代表的な非線形データ構造であり、ノードとノードを接続するエッジで構成され、要素間の「一対多」の階層関係を表すために使用されます。

ツリーの基本用語

ツリーの用語図解
Aルートノード
深さ0
B深さ1
C深さ1
D葉ノード
深さ2
E葉ノード
F葉ノード
ルートノード親ノードなし、唯一
子ノード直接の下位ノード
葉ノード子ノードなし
深さルートからそのノードまでの辺の数
高さそのノードから最も深い葉までの辺の数
二分木各ノードは最大2つの子を持つ

ツリー構造を理解するには、まずいくつかの基本用語を押さえる必要があります：

用語意味
ルートノード（Root）ツリーの開始ノードで、親ノードを持たない
子ノード（Child）あるノードに直接接続された次の層のノード
親ノード（Parent）あるノードに直接接続された前の層のノード
葉ノード（Leaf）子ノードを持たないノード、つまりツリーの末端
深さ（Depth）ルートノードからそのノードまでの辺の数。ルートの深さは0
高さ（Height）そのノードから最も深い葉ノードまでの辺の数

二分木の走査

二分木の4つの走査方法 – 同じツリーを例に
1
2
3
4
5

前順（根→左→右）

1 2 4 5 3

中順（左→根→右）

4 2 5 1 3

後順（左→右→根）

4 5 2 3 1

層順（レベル順）

1 2 3 4 5

一般的な4つの走査方法は次のとおりです：

走査方法訪問順序代表的な用途
前順走査根 → 左 → 右ツリーの複製、前置式の生成
中順走査左 → 根 → 右BSTの整列済みシーケンスを出力
後順走査左 → 右 → 根ツリーの削除、後置式の生成
層順走査レベルごとに左から右へBFS、レベルごとの出力

実例

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

struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int value) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->data = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

/* 前順走査：根 → 左 → 右 */
void preOrder(struct TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->data);   /* 最初に根を訪問 */
    preOrder(root->left);       /* 次に左部分木を走査 */
    preOrder(root->right);      /* 最後に右部分木を走査 */
}

/* 中順走査：左 → 根 → 右 */
void inOrder(struct TreeNode* root) {
    if (root == NULL) return;
    inOrder(root->left);        /* 最初に左部分木を走査 */
    printf("%d ", root->data);   /* 次に根を訪問 */
    inOrder(root->right);       /* 最後に右部分木を走査 */
}

/* 後順走査：左 → 右 → 根 */
void postOrder(struct TreeNode* root) {
    if (root == NULL) return;
    postOrder(root->left);      /* 最初に左部分木を走査 */
    postOrder(root->right);     /* 次に右部分木を走査 */
    printf("%d ", root->data);   /* 最後に根を訪問 */
}

int main() {
    /* 次のような二分木を構築:
           1
          / \
         2   3
        / \
       4   5   */
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("前順: "); preOrder(root);  printf("\n");  /* 1 2 4 5 3 */
    printf("中順: "); inOrder(root);   printf("\n");  /* 4 2 5 1 3 */
    printf("後順: "); postOrder(root); printf("\n");  /* 4 5 2 3 1 */
    return 0;
}

二分探索木（BST）

二分探索木（BST）— 左は小さく右は大きい
50
30
70
20
40
60
80

BSTの性質と操作

性質：左部分木のすべての値 < 根 < 右部分木のすべての値

挿入/探索：小さい場合は左部分木へ、大きい場合は右部分木へ。平衡時は O(log n)

中順走査で昇順シーケンスを出力：20 30 40 50 60 70 80

注意：1,2,3... の順に挿入するとリンクリストに退化して O(n) になる。AVL木で解決できる。

二分探索木（BST）要件：各ノードについて、左部分木のすべてのノードの値はそのノードより小さく、右部分木のすべてのノードの値はそのノードより大きいこと。

実例

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

struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

/* BST挿入：値の大小に応じて再帰的に適切な位置を探す
時間計算量：O(h)。hは木の高さ。平衡時は O(log n) */
struct TreeNode* insert(struct TreeNode* root, int value) {
    if (root == NULL) {
        struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        node->data = value;
        node->left = node->right = NULL;
        return node;
    }
    if (value < root->data) {
        root->left = insert(root->left, value);   /* 根より小さい場合は左部分木に挿入 */
    } else if (value > root->data) {
        root->right = insert(root->right, value); /* 根より大きい場合は右部分木に挿入 */
    }
    return root;  /* 等しい場合は無視（BSTは通常、重複する値を保存しない） */
}

/* BST探索：現在のノードと比較し、左または右に探索するかを決定 */
struct TreeNode* search(struct TreeNode* root, int target) {
    if (root == NULL || root->data == target) {
        return root;  /* 目標を見つけるか、葉ノードに到達 */
    }
    if (target < root->data) {
        return search(root->left, target);   /* 目標がより小さい場合は左部分木を探す */
    }
    return search(root->right, target);       /* 目標がより大きい場合は右部分木を探す */
}

/* 中順走査（BSTの順序性を検証） */
void inOrder(struct TreeNode* root) {
    if (root == NULL) return;
    inOrder(root->left);
    printf("%d ", root->data);
    inOrder(root->right);
}

int main() {
    struct TreeNode* root = NULL;
    int values[] = {50, 30, 70, 20, 40, 60, 80};

    /* 順に挿入してBSTを構築 */
    for (int i = 0; i < 7; i++) {
        root = insert(root, values[i]);
    }

    printf("BST中順走査（昇順）: ");
    inOrder(root);  /* 出力: 20 30 40 50 60 70 80 */
    printf("\n");

    /* 探索テスト */
    int target = 40;
    struct TreeNode* found = search(root, target);
    printf("%d %s\n", target, found ? "見つかりました！" : "見つかりません");
    /* 出力: 40 見つかりました！ */
    return 0;
}

BSTは理想的な場合（ツリーが平衡を保っている場合）、挿入・削除・探索はいずれも O(log n) を達成できます。しかし、データ自体が整列している場合（1, 2, 3, 4... の順で挿入するなど）、BSTはリンクリストに退化し、効率が O(n) に低下します。この問題を解決するために、コンピュータサイエンスではAVL木などの自己平衡二分探索木が開発されました。

その他の拡張