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

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

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

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

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

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に結果を格納してきます。

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()メソッドを用意してください。
＊二分探索木の性質については以下の記事を参考にしてください。

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

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を返します。

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=/