二分探索木のシンプルな例(C#)

二分探索木とは

数字を効率よく探したり、並べ替えたりするための特別な木の形をしたデータの仕組み。
左に小さな数字、右に大きな数字があり、探す時間を短くできる。

3分程度の解説動画
https://www.youtube.com/watch?v=6FETCw6ikgw

コード例

using System;

// ノードクラス：二分探索木の各ノードを表す
public class TreeNode
{
    public int Value; // ノードの値
    public TreeNode Left; // 左の子ノード
    public TreeNode Right; // 右の子ノード

    public TreeNode(int value) // コンストラクタ
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

// 二分探索木クラス
public class BinarySearchTree
{
    public TreeNode Root; // 木のルートノード

    public BinarySearchTree() // コンストラクタ
    {
        Root = null;
    }

    // 値を挿入するメソッド
    public void Insert(int value)
    {
        Root = InsertRecursive(Root, value);
    }

    // 再帰的にノードを挿入するヘルパーメソッド
    private TreeNode InsertRecursive(TreeNode node, int value)
    {
        if (node == null)
        {
            return new TreeNode(value); // 新しいノードを作成
        }

        if (value < node.Value)
        {
            node.Left = InsertRecursive(node.Left, value); // 左の子に挿入
        }
        else if (value > node.Value)
        {
            node.Right = InsertRecursive(node.Right, value); // 右の子に挿入
        }

        return node;
    }

    // 中間順序走査（In-order Traversal）メソッド
    public void InOrderTraversal()
    {
        InOrderTraversalRecursive(Root);
    }

    // 再帰的に中間順序走査を行うヘルパーメソッド
    private void InOrderTraversalRecursive(TreeNode node)
    {
        if (node != null)
        {
            InOrderTraversalRecursive(node.Left); // 左の子を走査
            Console.WriteLine(node.Value); // ノードの値を表示
            InOrderTraversalRecursive(node.Right); // 右の子を走査
        }
    }

    // 値を検索するメソッド
    public bool Search(int value)
    {
        return SearchRecursive(Root, value);
    }

    // 再帰的に値を検索するヘルパーメソッド
    private bool SearchRecursive(TreeNode node, int value)
    {
        if (node == null)
        {
            return false; // ノードが見つからない場合
        }

        if (value == node.Value)
        {
            return true; // ノードが見つかった場合
        }

        if (value < node.Value)
        {
            return SearchRecursive(node.Left, value); // 左の子を検索
        }
        else
        {
            return SearchRecursive(node.Right, value); // 右の子を検索
        }
    }
}

使用例

// プログラムのエントリーポイント
class Program
{
    static void Main(string[] args)
    {
        BinarySearchTree bst = new BinarySearchTree();
        bst.Insert(5);
        bst.Insert(3);
        bst.Insert(7);
        bst.Insert(2);
        bst.Insert(6);
        bst.Insert(8);

        Console.WriteLine("In-order Traversal:");
        bst.InOrderTraversal();

        Console.WriteLine("Search for 2: " + bst.Search(2)); // true
        Console.WriteLine("Search for 9: " + bst.Search(9)); // false
    }
}

挿入した値

5, 3, 7, 2, 6, 8

bst.InOrderTraversal(); による出力

2, 3, 5, 6, 7, 8 //小さい順に並び変えられている

木構造

        5
       /  \
      3     7
     /     / \
    2     6   8

理解のポイント

TreeNodeのフィールドとして自身の型の変数を持っている点。

また、下図のような構造をはじめから頭に置いておくと良さそう。

            null
        /          \
      null          null
     /    \         /   \
    null   null   null   null

BinarySearchTreeで上から順にnullにノードを挿入していくイメージ。