JavaScriptで木構造をラクに扱う

# はじめに

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

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

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

* tree-model-js
  * https://github.com/joaonuno/tree-model-js
* list-to-tree
  * https://github.com/DenQ/list-to-tree

# 2. tree-model-js

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

## 2-1. 呼び出し方

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

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

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

**組織図**

![org.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/549788/1cf5bbfc-34d7-db1f-204b-9b74956f9f44.png)

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

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

```js
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ノードオブジェクトを作成する（parse）

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

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

## 2-4. ノードを検索する（first）

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

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

## 2-5. ノードをフィルターする（filter）

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

```js

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

## 2-6. ノードを走査する（walk）

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

```js

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

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

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

```js

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

```

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

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


# 3. list-to-tree

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

``` js
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 を組み合わせる

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

``` js
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);
```

# 最後に

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

# 参考リンク
* tree-model-js
  * https://github.com/joaonuno/tree-model-js
* list-to-tree
  * https://github.com/DenQ/list-to-tree