連結リストを使って二分探索木を実装するC++プログラムの解説

本記事では、連結リスト（リンクリスト）を使用して二分探索木（Binary Search Tree: BST）を実装するC++プログラムを紹介します。二分探索木は、各ノードが最大2つの子を持つ木構造データであり、「左の子には親より小さい値、右の子には親より大きい値」を配置する規則に従うことで、高速なデータの挿入・検索を実現できるデータ構造です。

アルゴリズム

プログラム全体の流れは、以下の疑似コードのとおりです。

開始
    ツリーのノードを入力として受け取る。
    データ d、左ポインタ l、右ポインタ r を持つ構造体 nod を定義する。
    ノードをツリーに挿入する関数 create() を作成する：
        ノード数のカウンタとして c = 0 を初期化する。
        c < 6 の間 while ループを繰り返す：
            ルートノードの値を入力する。
            ノードの値を入力し、ルートより大きければ右側へ、小さければ左側へ挿入する。
    中順走査（inorder）でノードを巡回する関数 inorder() を作成する：
        「左 – 根 – 右」の順に処理する。
    前順走査（preorder）でノードを巡回する関数 preorder() を作成する：
        「根 – 左 – 右」の順に処理する。
    後順走査（postorder）でノードを巡回する関数 postorder() を作成する：
        「左 – 右 – 根」の順に処理する。
    main() から各関数を呼び出し、結果を出力する。
終了

サンプルコード

#include <iostream>
using namespace std;

struct nod {
    nod *l, *r;
    int d;
}*r = NULL, *p = NULL, *np = NULL, *q;

void create() {
    int v,c = 0;
    while (c < 6) {
        if (r == NULL) {
            r = new nod;
            cout<<"enter value of root node\n";
            cin>>r->d;
            r->r = NULL;
            r->l = NULL;
        } else {
            p = r;
            cout<<"enter value of node\n";
            cin>>v;
            while(true) {
                if (v< p->d) {
                    if (p->l == NULL) {
                        p->l = new nod;
                        p = p->l;
                        p->d = v;
                        p->l = NULL;
                        p->r = NULL;
                        cout<<"value entered in left\n";
                        break;
                    } else if (p->l != NULL) {
                        p = p->l;
                    }
                } else if (v >p->d) {
                    if (p->r == NULL) {
                        p->r = new nod;
                        p = p->r;
                        p->d = v;
                        p->l = NULL;
                        p->r = NULL;
                        cout<<"value entered in right\n";
                        break;
                    } else if (p->r != NULL) {
                        p = p->r;
                    }
                }
            }
        }
        c++;
    }
}

void inorder(nod *p) {
    if (p != NULL) {
        inorder(p->l);
        cout<<p->d<<endl;
        inorder(p->r);
    }
}

void preorder(nod *p) {
    if (p != NULL) {
        cout<<p->d<<endl;
        preorder(p->l);
        preorder(p->r);
    }
}

void postorder(nod *p) {
    if (p != NULL) {
        postorder(p->l);
        postorder(p->r);
        cout<<p->d<<endl;
    }
}

int main() {
    create();
    cout<<" traversal in inorder\n";
    inorder(r);
    cout<<" traversal in preorder\n";
    preorder(r);
    cout<<" traversal in postorder\n";
    postorder(r);
}

コードの解説

構造体 nod について

構造体 nod は、ノードの値を格納する d と、左の子を指すポインタ l、右の子を指すポインタ r で構成されています。各ノードが子ノードへのポインタを持つことで、連結リストのようにメモリ上で木構造を表現しています。

挿入処理 create()

create() 関数では、まずルートが空（NULL）の場合に最初の入力値をルートノードとして生成します。2つ目以降のノードは、ルートから辿りながら入力値と各ノードの値を比較し、小さければ左部分木へ、大きければ右部分木へと進みます。そして、空きポインタ（NULL）が見つかった位置に新しいノードを挿入します。この処理を6回繰り返すことで、合計6ノードの二分探索木が構築されます。

3種類の走査関数

inorder()（中順走査）、preorder()（前順走査）、postorder()（後順走査）は、いずれも再帰呼び出しを利用したシンプルな実装です。特に中順走査は二分探索木の性質上、すべての要素を昇順に出力できるという重要な特徴を持っています。

実行結果

enter value of root node
7
enter value of node
6
value entered in left
enter value of node
4
value entered in left
enter value of node
3
value entered in left
enter value of node
2
value entered in left
enter value of node
1
value entered in left
traversal in inorder
1
2
3
4
6
7
traversal in preorder
7
6
4
3
2
1
traversal in postorder
1
2
3
4
6
7

まとめ

このプログラムでは、ポインタベースの構造体（連結リストの考え方）を用いて二分探索木を構築し、中順・前順・後順の3つの走査を実装しました。実行結果を見ると、入力順序は 7 → 6 → 4 → 3 → 2 → 1 であったのに対し、中順走査では 1 → 2 → 3 → 4 → 6 → 7 と昇順にソートされた出力が得られています。これは二分探索木が持つ重要な性質の一つであり、探索アルゴリズムやソート処理の基礎として幅広く応用されています。