[JS]Data Structure - Tree

4977 ワード
TIL データ構造 tree テキストリンク

Tree


ツリーはノードからなる階層データ構造であり、グラフィックです.
  • には、1つまたは複数のルートノード(最上位ノード)があります.
  • 本のノード(最上位ノード)は、0個以上のサブノードを有することができる.
  • サブノードは、ルートノードと同様にサブノードを有し、定義を繰り返すことができる.

    • グラフの一種?


    ツリーは、図に示すように、ノード(頂点)と幹線(エッジ)で構成されます.ここで,有向図はループが存在しない有向図であるが,ツリーは無ループ図である.
    これは方向性のある非循環図形です.

    ツリー簡略化用語のまとめ

  • ノード:ツリーを構成する要素(例えば、A、B、C、D)をノードと呼ぶ.
  • root:上図に示すように、最上位ノードをルートノードと呼ぶ.
  • dept:ルートノードに対して他のノードにアクセスする距離をdepthと呼ぶ.
  • edge:ノードとノードを結ぶ線を幹線(edge)と呼びます.
  • leaf:サブノードが存在しないノードをleafと呼ぶ.(上図では、H、I、Jがleafになります.)
  • Siblings:同じ親ノードと同じ深さのノードにSibling関係があります.

    • Tree実装


    Method

  • insertNode:ノードをツリーに追加します.
  • contains:ツリーにノードが存在するかどうかを返します.
    • class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }

  insertNode(value) {
    const tree = new TreeNode(value);// 새로운 TreeNode를 생성
    this.children.push(tree); // 생성한 TreeNode를 자식 노드에 push
  }

  contains(value) {
    let bool = false;
    if (this.value === value) {//입력받은 value가 존재하면 true를 return
      bool = true;
    } else {
      for (const item of this.children) {
        if (item.contains(value)) { // 재귀를 통해 자식노드에 value가 존재하면 true를 return
          bool = true;
        }
      }
    }
    return bool;
  }
}

module.exports = TreeNode;
    黒馬プログラマーString,StringBufferとStringBuilderの違い
    1. Javacript - JSON