【アルゴリズム】JavaScriptでツリー問題を解く

#はじめに
Qiitaの競技プログラミング研究月間ということで、アルゴリズムの記事を書いています。
今回はツリー問題をまとめました。

JavaScriptでアルゴリズムの勉強をされている方の参考になれば幸いです。
記事を順次まとめていきますので、その他の記事についてはマイページからご覧ください。

https://qiita.com/suzuki0430

https://qiita.com/official-events/5a0502a2d94ed6a00c30

#ツリー構築
ツリー構造を形成するNodeクラスとTreeクラスを作成してください。
＊Nodeクラスのインスタンスプロパティには自身のデータ`data`と初期値が空の子ノードの配列`children`、メソッドには`add()`と`remove()`を用意してください。
＊Treeクラスのインスタンスプロパティには初期値がnullの`root`、メソッドには各ノードで実行する関数を引数に与えて幅優先で実行する`traverseBF()`、深さ優先で実行する`traverseDF()`を用意してください。

##解答
以下が解答例です。

```js:index.js
class Node {
  constructor(data) {
    this.data = data;
    this.children = [];
  }

  add(data) {
    this.children.push(new Node(data));
  }

  remove(data) {
    this.children = this.children.filter((node) => {
      return node.data !== data;
    });
  }
}

class Tree {
  constructor() {
    this.root = null;
  }

  // 幅優先
  traverseBF(fn) {
    const arr = [this.root];
    while (arr.length) {
      const node = arr.shift();

      // 子ノードをarrの末尾に追加
      arr.push(...node.children);
      fn(node);
    }
  }

  // 深さ優先
  traverseDF(fn) {
    const arr = [this.root];
    while (arr.length) {
      const node = arr.shift();

      // 子ノードを配列の先頭に追加
      arr.unshift(...node.children);
      fn(node);
    }
  }
}
```

Nodeクラスの`add()`メソッドでは、子ノードの配列`children`に`this.children.push(new Node(data))`でノードを追加しています。
また、`remove()`メソッドでは、`filter`を使うことで`children`からノードを削除しています。

幅優先探索は出発点に近い点から順に探索する手法です。
キューと同じFIFOの性質をもちます。

`traverseBF()`では、まず`root`のノードのみが入った配列`arr`を用意します。
`while(arr.length)`内で`arr`の先頭ノードを`node`として取得して、`arr.push(...node.children)`で`arr`の末尾に`node`の子ノードを追加します。
最後に`node`を引数として`fn()`を実行します。
これを`arr`に追加するノードがなくなるまで繰り返していきます。

一方、深さ優先探索はとにかく行けるとこまで行ってそれ以上進めなくなったら一歩戻ってまた探索するという手法です。
スタックと同じLIFOの性質をもちます。

`traverseDF()`内の処理の大きな流れは`traverseBF()`と同様なのですが、`arr`の先頭ノードを`node`として取得した後は、`arr.unshift(...node.children)`で`arr`の**先頭**に`node`の子ノードを追加するといった違いがあります。


#ツリーの各階層の幅
ツリーの各階層のノードの個数をルートから順に配列で出力してください。

```
     0
   / |  \
 1   2   3
 |       |
 4       5
 Answer: [1, 3, 2]
```

##解答
ノードの配列をつくり、階層のノード数を数え終わったら末尾に's'を追加します。
次の`s`がくるまでの配列の個数をその階層のノードの個数としてカウントし、`counters`に結果を格納してきます。

```js:index.js
function levelWidth(root) {
  // arrとcountersの初期値
  const arr = [root, 's'];
  const counters = [0];

  while (arr.length > 1) {
    // arrの先頭を取得
    const node = arr.shift();

    // nodeが's'(階層のノードのカウントがおわった)のときcountersに0、arrの末尾に's'を追加
    if (node === 's') {
      counters.push(0);
      arr.push('s');
    } else {
      // 's'の後に子ノードを追加
      arr.push(...node.children);
      // 階層のノードをカウント
      counters[counters.length - 1]++;
    }
  }
  return counters;
}
```

#二分探索木
二分探索木を構成するNodeクラスを作成してください。
＊Nodeクラスのインスタンスプロパティには`data` `left` `right`を用意し、メソッドには適切な位置にノードを追加する`insert()`メソッド、同じデータが含まれていればその値を返す`contains()`メソッドを用意してください。
＊二分探索木の性質については以下の記事を参考にしてください。

https://www.geeksforgeeks.org/binary-search-tree-data-structure/

##解答
以下が回答例です。

```js:index.js
class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }

  insert(data) {
    if (data < this.data && this.left) {
      this.left.insert(data);
    } else if (data < this.data) {
      this.left = new Node(data);
    } else if (data > this.data && this.right) {
      this.right.insert(data);
    } else if (data > this.data) {
      this.right = new Node(data);
    }
  }

  contains(data) {
    if (this.data === data) {
      return this;
    }

    if (this.data < data && this.right) {
      return this.right.contains(data);
    } else if (this.data > data && this.left) {
      return this.left.contains(data);
    }

    return null;
  }
}
```
`insert()`で、追加するデータがノードの値より小さく左側の子ノードが存在している場合`if (data < this.data && this.left)`には、`this.left.insert(data)`のように`insert()`を再帰呼び出しします。

`contains()`でも同様に、探したいデータが存在するまで`this.right.contains(data)`のように再帰呼び出しを行います。
一致するデータがなければnullを返します。

#二分探索木のバリデーション
引数に与えたノードが二分探索木のルールに従っているかどうか判定してください。

##解答
`node` `min` `max`を引数に与えて、`false`になる条件式を何個かつくります。
これらの条件を全部満たさなければtrueを返します。

```js:index.js
function validate(node, min = null, max = null) {
  if (max !== null && node.data > max) {
    return false;
  }

  if (min !== null && node.data < min) {
    return false;
  }

  if (node.left && !validate(node.left, min, node.data)) {
    return false;
  }

  if (node.right && !validate(node.right, node.data, max)) {
    return false;
  }

  return true;
}
```

#参考資料
https://www.udemy.com/share/101WNkCEEZd11VRno=/

https://manabitimes.jp/math/1247