JavaScriptで二分木のノード（Node）を定義する方法

木構造（ツリー）を構成する個々の要素は「ノード」と呼ばれます。二分木はノードの集合体であるため、二分木を定義する前に、まずノードそのものを定義する必要があります。

ここでは、left・right・data という3つのプロパティを持つ、シンプルなノード定義を作成していきましょう。それぞれのプロパティの役割は以下のとおりです。

• left ― このノードの左の子ノードへの参照を保持します。

• right ― このノードの右の子ノードへの参照を保持します。

• data ― このノードに格納したいデータへの参照を保持します。

ノード構造のコード例

それでは、このような構造をコードで表現してみましょう。

class Node {
    constructor(data, left = null, right = null) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}

このように、Node クラスは data・left・right の3つのプロパティを受け取るコンストラクタとして定義されています。

実際の実装では、値は葉（リーフ）の位置に挿入していくことが多いため、left と right を null のまま初期化したノードを生成するケースがほとんどです。

BinarySearchTreeクラス内での定義

利便性を高めるために、この Node クラスは、後ほど作成する BinarySearchTree（二分探索木）クラスのプロパティとして定義するのがおすすめです。こうすることで、使用する場所の中にクラスを閉じ込めることができ、コードの整理やカプセル化がしやすくなります。

多分木の場合との違い

なお、左右2つの子ノードを明示的に持つこの形式は、二分木に特有のものです。B木やB+木のような多分木（マルチウェイツリー）の場合は、子ノードを配列などのコンテナとして保持する children プロパティを定義します。木構造の種類によってノードの設計が変わる点は、押さえておくとよいでしょう。