Help us understand the problem. What is going on with this article?

JavaScriptで木構造をラクに扱う

はじめに

この記事はJavaScriptで木構造をラクに扱う方法について、ロゴスウェア株式会社の社内勉強会で取り上げたものです。

1. 木構造を楽に扱うためのライブラリ

以下の2つがオススメです。

2. tree-model-js

木構造のデータについて、ノードの検索やフィルタ等々の操作をうまいことやってくれるライブラリです。

2-1. 呼び出し方

const TreeModel = require('tree-model');
const tree = new TreeModel();

2-2. 期待するデータの形式

tree-model-jsでは、入れ子になっている木構造のオブジェクトを入力にとります。
ここでは以下のような組織図の木構造のデータを例にします。

組織図

org.png

上記組織図を表すオブジェクト

以下のようにchildrenプロパティの配列に子組織のオブジェクトを入れて表現します。

const treeDataStructure = {
  id: 1,
  name: '全社',
  children: [
    {
      id: 11,
      name: 'つくばオフィス'
      children: [
        {
          id: 111,
          name: 'システムアンドサービスグループ'
        }
      ]
    },
    {
      id: 12,
      name: '東京オフィス',
      children: [
        {
          id: 121,
          name: 'スイートプロダクトデザイングループ'
        },
        {
          id: 122,
          name: 'アクティブ・ラーニングデザイングループ'
        }
      ]
    },
    {
      id: 13,
      name: '不明のグループ'
    }
  ]
};

2-3. Rootノードオブジェクトを作成する

tree-model-jsparseヘルパーに上記の入れ子のデータを入れて、対象の木構造のRootノードのオブジェクトを作成します。

// 木構造のオブジェクトをパースしてRootノードオブジェクトを作成
const root = tree.parse(treeDataStructure);

2-4. ノードを検索する

idが121のノードを検索してノードを取得する例です。

const node121 = root.first(node => node.model.id === 121);
console.log(node121.model);
// modelプロパティを使えば、ノードのプロパティを取得できる。
// -> { id: 121, name: 'SPD' }

2-5. ノードをフィルターする

idが100以上のノードを全て取得する例です。

const nodesGt100 = root.all(node => node.model.id > 100);

2-6. ノードを走査する

ツリーを上から辿って、ノードのidを順番に出力する例です。

root.walk(node => { console.log(node.model.id) });
/*
1
11
111
12
121
122
13
*/

2-7. 探索アルゴリズムを指定する

上記いずれのAPI(first, all, walk)も、オプションを指定すれば探索アルゴリズムを指定できます。

root.walk({ strategy: 'breadth' /* 幅優先探索 */ }, node => { console.log(node.model.id) });
/*
1
11
12
13
111
121
122
*/

以下の3種類がサポートされています。

種類 オプション
幅優先探索 { strategy: 'breadth' }
深さ優先探索(ルートから) { strategy: 'pre' }
深さ優先探索(末端から)  { strategy: 'post' }

3. list-to-tree

フラットなリストから、2-2. 期待するデータの形式で記載した 入れ子になっている木構造のオブジェクト に変換するライブラリです。

const LTT = require('list-to-tree');

const nodeList = [
  { id: 1, parent: 0 },
  { id: 11, parent: 1 },
  { id: 111, parent: 11 }
];

const treeDataStructure = new LTT(
  nodes,
  { key_id: 'id', key_parent: 'parent', key_child: 'children' }
).GetTree()[0];

console.log(JSON.stringfy(treeDataStructure, null, 2));
/*
{
  "children": [
    {
      "children": [
        {
          "id": 111,
          "parent": 11
        }
      ],
      "id": 11,
      "parent": 1
    }
  ],
  "id": 1,
  "parent": 0
}
*/

4. tree-model-js と list-to-tree を組み合わせる

2つを組み合わせれば、
1. フラットな木構造のデータから
2. 入れ子になっている木構造のオブジェクトに変換し、
3. tree-model-jsのRootノードオブジェクトを作成できます。

const TreeModel = require('tree-model');
const LTT = require('list-to-tree');

// 1. フラットな木構造のデータ
const nodeList = [
  { id: 1, parent: 0 },
  { id: 11, parent: 1 },
  { id: 111, parent: 11 }
];

// 2. 入れ子になっている木構造のオブジェクト
const treeDataStructure = new LTT(
  nodes,
  { key_id: 'id', key_parent: 'parent', key_child: 'children' }
).GetTree()[0];

// 3. tree-model-jsのRootノードオブジェクトを作成
const root = tree.parse(treeDataStructure);

最後に

間違いや改善点等があればご指摘ください。

参考リンク

horiuchie
株式会社OKAN / JavaScript, React, React Native, Ramda.js, AWS, Python / パンダが好き / 🐼PANDA(Positive ANalytic aDAptive)/ 和歌山 / ENTJ型 / Backlog
https://www.wantedly.com/users/125262687
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした