導入組織階層、州、市、郡、動物や植物の分類など、ツリー状のデータ構造によく遭遇します。以下はツリー構造の例です。 実際のアプリケーションでは、特に 1 対多の親/子ノード関係がある場合、この情報を次の構造として保存するのが一般的です。 定数データ = [ { id: 56, 親ID: 62 }, { id: 81, 親ID: 80 }, { id: 74, 親ID: null }, { id: 76, 親ID: 80 }, { id: 63, 親ID: 62 }, { id: 80, 親ID: 86 }, { id: 87, 親ID: 86 }, { id: 62, 親ID: 74 }, { id: 86, 親ID: 74 }, ]; では、このオブジェクト配列形式を階層ツリー形式に変換するにはどうすればよいでしょうか?実際、JavaScript オブジェクト参照の特性を利用すると、実装は非常に簡単です。再帰なしで O(n) 時間で実行できます。 用語 便宜上、まずいくつかの用語を定義しましょう。配列内の各要素 (つまり、ツリー図内の各円) を「ノード」と呼びます。ノードは、複数のノードの「親ノード」になることも、特定のノードの「子ノード」になることもできます。上図では、ノード 86 はノード 80 とノード 87 の「親ノード」であり、ノード 86 はノード 74 の子ノードです。ツリーの最上位ノードは「ルートノード」と呼ばれます。 アイデアツリー構造を構築するには、次のものが必要です。
参照はオブジェクト ツリーに格納されていることがわかります。そのため、このタスクは O(n) 時間で完了できます。 ID配列インデックスのマッピング関係を確立する必須ではありませんが、このマッピング関係により、要素の場所をすばやく見つけ、親要素への参照を見つけやすくなります。 const idMapping = data.reduce((acc, el, i) => { acc[el.id] = i; acc を返します。 }, {}); マッピングの結果は次のようになります。後でその有用性がわかります。
ツリー構造の構築ここで、このツリー構造の構築を開始します。オブジェクトの配列を反復処理し、各要素の親オブジェクトを見つけて、要素への参照を追加します。これで、この idMapping が要素の検索にどれほど便利であるかがわかるはずです (一定時間)。 根付かせる; データ.forEach(el => { // ルートノードを決定する if (el.parentId === null) { ルート = el; 戻る; } // マッピング テーブルを使用して親要素を見つけます const parentEl = data[idMapping[el.parentId]]; // 現在の要素を親要素の `children` 配列に追加します。parentEl.children = [...(parentEl.children || []), el]; }); 終わり! console.log を使用してルートを出力し、次を確認します。 コンソールログ(ルート);
原理なぜこれが可能なのでしょうか?これは、データ配列内の各要素がメモリ内のオブジェクトへの参照であり、forEach ループ内の el 変数が実際にはメモリ内のオブジェクトを指し、parentEl もオブジェクトを参照するためです。 メモリ内のオブジェクトが子配列を参照する場合、これらの子要素も自身の子要素配列を参照できます。これらの関連付けはすべて参照を通じて完了します。 要約するオブジェクト参照は JavaScript の最も基本的な概念の 1 つであり、より多くの学習と理解が必要です。この概念を本当に理解すると、厄介なバグを回避し、一見複雑に見える問題に対して比較的単純な解決策を見つけることができます。 上記は、JavaScript でツリー構造を構築するための効率的なアルゴリズムの詳細についての簡単な説明です。ツリー構造を構築するための JavaScript アルゴリズムの詳細については、123WORDPRESS.COM の他の関連記事をご覧ください。 以下もご興味があるかもしれません:
|
<<: mysql-8.0.11-winx64.zip の詳細なインストール チュートリアル
>>: Linux CentOS 6.5 ifconfig が IP を照会できない問題の解決方法
Navicat を使用してリモート Linux MySQL データベースに接続すると、不明なエラー ...
この記事では、VMware Workstation14 ProにUbuntu 16.04をインストー...
1. transform 属性を使用して、画像を拡大せずに表示します (パスの問題は必要に応じて修正...
目次序文: 1.DEFINERの簡単な紹介2. いくつかの注意点要約:序文: MySQL データベー...
目次502 不正なゲートウェイ エラーの発生1. 502 不正なゲートウェイ エラーとは何ですか? ...
WeChat アプレット プロジェクトを書いていたとき、その中に「都市選択」機能がありました。作者は...
今日の画面解像度は、320 ピクセル (iPhone) ほど小さいものから、2560 ピクセル以上 ...
コンストラクタの借用この手法の基本的な考え方は単純です。サブタイプ コンストラクター内からスーパータ...
通常、私たちが構築する Docker イメージはサイズが大きく、多くのディスク領域を占有します。コン...
目次ターゲット思考分析コード着陸要約するターゲットトークンの有効期限切れシナリオの処理トークンは、ユ...
需要背景:ミニプログラムページに GIF ダイナミック画像を挿入しますが、GIF 画像は通常サイズが...
Docker Swarm は、Docker によって開発されたコンテナ クラスター管理サービスです。...
MySQL 5.x と MySQL 8.0.X のいくつかの違いapplication.proper...
この記事では、MySQL の null (IFNULL、COALESCE、NULLIF) に関連する...
序文今日 GitHub を閲覧していたところ、SQL を最適化および書き換えるための sora とい...