JavaScript ツリー構造の深さ優先アルゴリズムを 1 つの記事でマスターする

木

とは何ですか? 実生活では、柳、ポプラ、桃の木にかかわらず、木は私たちの生活のどこにでも見られると思いますが、木は抽象化されたものです。

以下に示すように

、階層構造のモデルになります。

たとえば、以下に示すように、会社の組織構造をツリーで表すことができます。

組織構造に加えて、家系図、州や都市などもツリー構造を使用して表現できます。

ツリーの用語

以下に示すように、ツリーには多くの用語があります。

• ツリー: n (n≥0) 個のノードの有限集合。 n=0の場合、
• ノード次数: ノードのサブツリーの数。たとえば、ノード B の次数は 2 です。ノード A の次数は 3、
• ツリーの次数はツリーのすべてのノードの中で最大の次数です。たとえば、上の図では、ツリーの次数は 3、
• 次数は 0 のノードです。リーフノードとも呼ばれます;
• 子ノード: 上の図に示されているように;
• ルートノード:
• 上の図に示されているように;
• ツリーの深さ: ツリー内のすべてのノードの最大レベル。たとえば、上の図のツリーの深さは 3、
• ノード レベル: たとえば、E ノードのレベルは 3、ノード レベルは親ノード レベル + 1、ルート ノードのレベルは 1 です。 ;
• パス:あるノードから別のノードへのチャネル、たとえば A→H のパスはADH ;
• パスの長さ:あるノードから別のノードまでの距離、たとえば A→H のパス

JavaScript のツリー構造は、

DOM ツリー、カスケード選択、ツリー コンポーネントなど、フロントエンドで最も一般的なデータ構造の 1 つであると言えます。JavaScript

はツリー データ構造を提供しませんが、使用できます。オブジェクトと配列を使用してツリーをシミュレートします。

たとえば、次のコード:

consttree = {
  値: 'A'、
  子供たち： [
    {
      値: 'B'、
      子供たち： [
        { 値: 'E'、子: null }、
        { 値: 'F'、子: null }、
      ]、
    }、
    {
      値: 'C'、
      子: [{ 値: 'G'、子: null }]、
    }、
    {
      値: 'D'、
      子供たち： [
        { 値: 'H'、子: null }、
        { 値: 'I'、子: null }、
      ]、
    }、
  ]、

幅優先および深さ優先のトラバーサル アルゴリズムの利点

深

さ優先

いわゆる深さ優先のトラバーサル アルゴリズムは、ツリーのブランチを可能な限り深く検索します。そのトラバーサル順序は次のとおりです。

実装のアイデアは次のとおりです。

• ルート ノードにアクセスし、
• ルート ノードのchildrenの深さ優先トラバーサル (再帰) を続行します。

実装

コードは次のとおりです。

  console.log(root.value)
  root.children && root.children.forEach(dfs) // 以下と一致します // if (root.children) {
  // root.children.forEach(child => {
  //dfs(子)
  // })
  // }
}
dfs(tree) //このツリーは以前に定義されたツリーです/* 結果 A
B
E
F
C
G
D
H
私
*/

ご覧のとおり、順序は画像と一致しています。これは、アルゴリズムに問題がないことを意味します。

幅の優先順位

いわゆる幅の優先順位は、ルート ノードに最も近いノードを順番に訪問することです。その走査順序は次のとおりです。

実装のアイデアは次のとおりです。

• キューを作成し、
• キューの先頭をキューから取り出してアクセスし、
• ステップ 2 と 3 を
• childrenに
繰り返します。
• キューは空です。

実装コードは次のとおりです。

function bfs(root) {
  // 1. 新しいキューを作成し、ノードをキューに追加します const q = [root]
  // 4 繰り返し while (q.length > 0) {
    const node = q.shift() // 2 キ​​ューヘッドがデキューされました console.log(node.value)
    // チームのリーダーである 3 人の子供がチームに追加されます node.children &&
      node.children.forEach(child => {
        q.push(子)
      })
  }
}
bfs(ツリー)
/* 結果 A
B
C
D
E
F
G
H
私
*/

ご覧のとおり、順序は画像と一致しています。これは、アルゴリズムに問題がないことを意味します。