C#で再帰を使って二分探索木を反転（ミラー化）する方法

二分探索木（Binary Search Tree）を反転するとは、木の左右を入れ替えて、木全体を鏡像に変換することです。本記事では、C#の再帰処理を用いて二分探索木を反転する方法を、コード例とともにわかりやすく解説します。

反転の基本的な考え方

まず、InvertABinarySearchTree メソッドを呼び出し、対象のノードを引数として渡します。このメソッドの処理の流れは以下の通りです。

• ノードが null の場合は、そのまま null を返します（ベースケース）。
• ノードが null でない場合は、左の子と右の子それぞれに対して InvertABinarySearchTree を再帰的に呼び出します。
• 再帰呼び出しの結果を受け取り、右の子の値を左の子に、左の子の値を右の子に代入して左右を入れ替えます。

この処理をすべてのノードに適用することで、最終的な出力は元の木の鏡像となります。

実装例

public class TreesPgm{
    public class Node{
        public int Value;
        public Node LeftChild;
        public Node RightChild;
        public Node(int value){
            this.Value = value;
        }
        public override String ToString(){
            return "Node=" + Value;
        }
    }
    public Node InvertABinarySearchTree(Node node){
        if (node == null){
            return null;
        }
        Node left = InvertABinarySearchTree(node.LeftChild);
        Node right = InvertABinarySearchTree(node.RightChild);
        node.LeftChild = right;
        node.RightChild = left;
        return root;
    }
}

コードのポイント

• ベースケース： ノードが null のときに null を返すことで、再帰の無限ループを防いでいます。
• 再帰的な左右の反転： 左右の子部分木をそれぞれ先に反転してから、親ノードの左右ポインタを入れ替えます。
• 計算量： 各ノードを一度だけ訪問するため、時間計算量は O(n)、再帰の深さは木の高さに依存します。

入力例

    1
  3   2

出力例

    1
  2   3

入力ではルート「1」の左に「3」、右に「2」が配置されていますが、反転後は左右が入れ替わり、「2」が左に、「3」が右に配置されていることが確認できます。このように再帰を活用すると、シンプルなコードで木構造の反転を実現できます。