C++で実装する二分探索木（BST）：挿入・削除・検索・走査の完全ガイド

二分探索木（Binary Search Tree：BST）は、データを効率的に管理できるように整理された二分木です。BSTのすべてのノードは、以下の性質を満たす必要があります。

• ノードの右部分木に含まれるキーは、必ずその親ノードのキーより大きい。
• ノードの左部分木に含まれるキーは、必ずその親ノードのキーより小さい。
• すべてのキー値は重複しない（一意である）。
• 各ノードが持てる子の数は最大2つまで。

これらの性質により、BSTでは平均的にO(log n)の時間で要素の検索・挿入・削除が可能になり、整列済みデータの取り扱いにも適しています。本記事では、C++を用いてBSTに対する基本的な操作（検索・挿入・削除・走査）を実装する方法を解説します。

クラス設計の概要

このプログラムでは、BSTクラスを作成し、以下のメンバ関数を実装します。

• search()：指定した値をBST内から検索します。根（ルート）から順に比較しながら深さをカウントし、見つかった場合は「値とその深さ」を出力します。値が現在のノードより小さければ左の子へ、大きければ右の子へ移動します。
• insert()：新しい要素を木に挿入します。木が空の場合はそのデータを根として登録します。空でない場合は、値を既存ノードと比較し、小さければ左の子として、そうでなければ右の子として再帰的に配置します。なお、同じ値がすでに存在する場合は挿入を行いません。
• del()：木から要素を削除します。削除対象ノードの子の状態に応じて、次の4つのケース関数を呼び出します。
• casea()：左の子も右の子も存在しない場合（葉ノード）に呼び出されます。
• caseb()：子が1つだけ存在する場合（左のみ、または右のみ）に呼び出されます。
• casec()：左右両方の子を持つ場合に呼び出されます。このケースでは、右部分木の中で最小の値を持つノード（中間順後続ノード）を削除位置に移動させます。
• inorder() / preorder() / postorder()：それぞれ「左→根→右」「根→左→右」「左→右→根」の順序でノードを巡回（トラバース）します。
• show()：木の構造を見やすい形で画面に表示します。

サンプルコード

#include <iostream>
#include <cstdlib>
using namespace std;

struct nod // ノードの宣言
{
    int info;
    struct nod *l; // 左の子
    struct nod *r; // 右の子
} *r;

class BST
{
public: // メンバ関数の宣言
    void search(nod *, int);
    void find(int, nod **, nod **);
    void insert(nod *, nod *);
    void del(int);
    void casea(nod *, nod *);
    void caseb(nod *, nod *);
    void casec(nod *, nod *);
    void preorder(nod *);
    void inorder(nod *);
    void postorder(nod *);
    void show(nod *, int);
    BST()
    {
        r = NULL;
    }
};

// 要素の位置を検索する（親と該当ノードを返す）
void BST::find(int i, nod **par, nod **loc)
{
    nod *ptr, *ptrsave;
    if (r == NULL)
    {
        *loc = NULL;
        *par = NULL;
        return;
    }
    if (i == r->info)
    {
        *loc = r;
        *par = NULL;
        return;
    }
    if (i < r->info)
        ptr = r->l;
    else
        ptr = r->r;
    ptrsave = r;
    while (ptr != NULL)
    {
        if (i == ptr->info)
        {
            *loc = ptr;
            *par = ptrsave;
            return;
        }
        ptrsave = ptr;
        if (i < ptr->info)
            ptr = ptr->l;
        else
            ptr = ptr->r;
    }
    *loc = NULL;
    *par = ptrsave;
}

// 検索処理（見つかった深さを出力）
void BST::search(nod *root, int data)
{
    int depth = 0;
    nod *temp = root;
    while (temp != NULL)
    {
        depth++;
        if (temp->info == data)
        {
            cout << "\nData found at depth: " << depth << endl;
            return;
        }
        else if (temp->info > data)
            temp = temp->l;
        else
            temp = temp->r;
    }
    cout << "\n Data not found" << endl;
    return;
}

// 挿入処理
void BST::insert(nod *tree, nod *newnode)
{
    if (r == NULL)
    {
        r = new nod;
        r->info = newnode->info;
        r->l = NULL;
        r->r = NULL;
        cout << "Root Node is Added" << endl;
        return;
    }
    if (tree->info == newnode->info)
    {
        cout << "Element already in the tree" << endl;
        return;
    }
    if (tree->info > newnode->info)
    {
        if (tree->l != NULL)
        {
            insert(tree->l, newnode); // 左部分木へ再帰的に挿入
        }
        else
        {
            tree->l = newnode;
            (tree->l)->l = NULL;
            (tree->l)->r = NULL;
            cout << "Node Added To Left" << endl;
            return;
        }
    }
    else
    {
        if (tree->r != NULL)
        {
            insert(tree->r, newnode); // 右部分木へ再帰的に挿入
        }
        else
        {
            tree->r = newnode;
            (tree->r)->l = NULL;
            (tree->r)->r = NULL;
            cout << "Node Added To Right" << endl;
            return;
        }
    }
}

// 削除処理
void BST::del(int i)
{
    nod *par, *loc;
    if (r == NULL)
    {
        cout << "Tree empty" << endl;
        return;
    }
    find(i, &par, &loc);
    if (loc == NULL)
    {
        cout << "Item not present in tree" << endl;
        return;
    }
    if (loc->l == NULL && loc->r == NULL) // 子なし
    {
        casea(par, loc);
        cout << "item deleted" << endl;
    }
    if (loc->l != NULL && loc->r == NULL) // 左の子のみ
    {
        caseb(par, loc);
        cout << "item deleted" << endl;
    }
    if (loc->l == NULL && loc->r != NULL) // 右の子のみ
    {
        caseb(par, loc);
        cout << "item deleted" << endl;
    }
    if (loc->l != NULL && loc->r != NULL) // 子が2つ
    {
        casec(par, loc);
        cout << "item deleted" << endl;
    }
    free(loc);
}

// ケース A：削除対象が葉ノードの場合
void BST::casea(nod *par, nod *loc)
{
    if (par == NULL)
    {
        r = NULL;
    }
    else
    {
        if (loc == par->l)
            par->l = NULL;
        else
            par->r = NULL;
    }
}

// ケース B：削除対象が子を1つだけ持つ場合
void BST::caseb(nod *par, nod *loc)
{
    nod *child;
    if (loc->l != NULL)
        child = loc->l;
    else
        child = loc->r;
    if (par == NULL)
    {
        r = child;
    }
    else
    {
        if (loc == par->l)
            par->l = child;
        else
            par->r = child;
    }
}

// ケース C：削除対象が2つの子を持つ場合
void BST::casec(nod *par, nod *loc)
{
    nod *ptr, *ptrsave, *suc, *parsuc;
    ptrsave = loc;
    ptr = loc->r;
    while (ptr->l != NULL) // 右部分木の最小値を探索
    {
        ptrsave = ptr;
        ptr = ptr->l;
    }
    suc = ptr;
    parsuc = ptrsave;
    if (suc->l == NULL && suc->r == NULL)
        casea(parsuc, suc);
    else
        caseb(parsuc, suc);
    if (par == NULL)
    {
        r = suc;
    }
    else
    {
        if (loc == par->l)
            par->l = suc;
        else
            par->r = suc;
    }
    suc->l = loc->l;
    suc->r = loc->r;
}

// 前順走査（根 → 左 → 右）
void BST::preorder(nod *ptr)
{
    if (r == NULL)
    {
        cout << "Tree is empty" << endl;
        return;
    }
    if (ptr != NULL)
    {
        cout << ptr->info << " ";
        preorder(ptr->l);
        preorder(ptr->r);
    }
}

// 中間順走査（左 → 根 → 右）
void BST::inorder(nod *ptr)
{
    if (r == NULL)
    {
        cout << "Tree is empty" << endl;
        return;
    }
    if (ptr != NULL)
    {
        inorder(ptr->l);
        cout << ptr->info << " ";
        inorder(ptr->r);
    }
}

// 後順走査（左 → 右 → 根）
void BST::postorder(nod *ptr)
{
    if (r == NULL)
    {
        cout << "Tree is empty" << endl;
        return;
    }
    if (ptr != NULL)
    {
        postorder(ptr->l);
        postorder(ptr->r);
        cout << ptr->info << " ";
    }
}

// 木の構造を表示
void BST::show(nod *ptr, int level)
{
    int i;
    if (ptr != NULL)
    {
        show(ptr->r, level + 1);
        cout << endl;
        if (ptr == r)
            cout << "Root->: ";
        else
        {
            for (i = 0; i < level; i++)
                cout << " ";
        }
        cout << ptr->info;
        show(ptr->l, level + 1);
    }
}

int main()
{
    int c, n, item;
    BST bst;
    nod *t;
    while (1)
    {
        cout << "1.Insert Element " << endl;
        cout << "2.Delete Element " << endl;
        cout << "3.Search Element" << endl;
        cout << "4.Inorder Traversal" << endl;
        cout << "5.Preorder Traversal" << endl;
        cout << "6.Postorder Traversal" << endl;
        cout << "7.Display the tree" << endl;
        cout << "8.Quit" << endl;
        cout << "Enter your choice : ";
        cin >> c;
        switch (c)
        {
        case 1:
            t = new nod;
            cout << "Enter the number to be inserted : ";
            cin >> t->info;
            bst.insert(r, t);
            break;
        case 2:
            if (r == NULL)
            {
                cout << "Tree is empty, nothing to delete" << endl;
                continue;
            }
            cout << "Enter the number to be deleted : ";
            cin >> n;
            bst.del(n);
            break;
        case 3:
            cout << "Search:" << endl;
            cin >> item;
            bst.search(r, item);
            break;
        case 4:
            cout << "Inorder Traversal of BST:" << endl;
            bst.inorder(r);
            cout << endl;
            break;
        case 5:
            cout << "Preorder Traversal of BST:" << endl;
            bst.preorder(r);
            cout << endl;
            break;
        case 6:
            cout << "Postorder Traversal of BST:" << endl;
            bst.postorder(r);
            cout << endl;
            break;
        case 7:
            cout << "Display BST:" << endl;
            bst.show(r, 1);
            cout << endl;
            break;
        case 8:
            exit(1);
        default:
            cout << "Wrong choice" << endl;
        }
    }
}

実行例

このプログラムを実行すると、メニュー形式で各操作を選択できます。以下は実際の実行例です。

1.Insert Element
2.Delete Element
3.Search Element
4.Inorder Traversal
5.Preorder Traversal
6.Postorder Traversal
7.Display the tree
8.Quit
Enter your choice : 1
Enter the number to be inserted : 6
Root Node is Added

Enter your choice : 1
Enter the number to be inserted : 7
Node Added To Right

Enter your choice : 1
Enter the number to be inserted : 5
Node Added To Left

Enter your choice : 1
Enter the number to be inserted : 4
Node Added To Left

Enter your choice : 3
Search:
7
Data found at depth: 2

Enter your choice : 3
Search:
1
Data not found

Enter your choice : 4
Inorder Traversal of BST:
4 5 6 7

Enter your choice : 5
Preorder Traversal of BST:
6 5 4 7

Enter your choice : 6
Postorder Traversal of BST:
4 5 7 6

Enter your choice : 7
Display BST:
      7
Root->: 6
    5
  4

Enter your choice : 2
Enter the number to be deleted : 1
Item not present in tree

Enter your choice : 5
Preorder Traversal of BST:
6 5 4 7

Enter your choice : 2
Enter the number to be deleted : 5
item deleted

Enter your choice : 7
Display BST:
7
Root->: 6
4

Enter your choice : 8

まとめ

本プログラムでは、C++のクラスを使って二分探索木（BST）の主要な操作——挿入、削除（3つの子パターンへの対応）、検索（深さの表示付き）、そして3種類の走査（前順・中間順・後順）——を実装しました。特に中間順走査を行うと、BSTの性質によりキーが昇順に出力される点が重要です。また、削除処理では「葉ノード」「子1つ」「子2つ」の3つのケースを正しく処理することで、木の構造を保ったまま要素を除去できます。データ構造とアルゴリズムの学習において、BSTは非常に重要な基礎となるので、ぜひコードを実際に動かして挙動を確認してみてください。