Javascript でツリー階層をデータで持たせる

はしがき

ディレクトリ階層であったり、組織構成図であったり、ツリーで表現されるものを JavaScript 上でデータで持たせたい場合がある。クラスを使うと簡単に実現することができるので備忘録をかねて書いておくことにした。実装方法はリンクリストの一種となっている。

まずはクラスの定義

これから定義する　Node　クラスのインスタンスがそれぞれのノードに対応する。例えばグループ階層が以下のようになっているとする。

ROOT - GROUP_A - GROUP_A_1 
               - GROUP_A_2
     - GROUP_B - GROUP_B_1 
               - GROUP_B_2
               - GROUP_B_3

このときにそれぞれのグループがそれぞれの　Node　クラスインスタンス　に対応するようにする。また各　Node　クラスインスタンスから親と子孫に自由にアクセスできるようにしたい。つまり上記の例だと各グループから自分の親（の親...）や子供（の子供...）にアクセスできるようにできたらいろいろと便利である。

というわけで、まずクラスの定義から。

class Node {
    
    /**
    * @param {string} nodeName ノードの名前
    */
    constructor(nodeName) {
        this.name = nodeName
        this.parent = null;
        this.childrenArray = [];
    }

    /**
    * @param {Node} childNode
    */
    addChild(childNode) {
        this.childrenArray.push(childNode);
        childNode.parent = this;
    }

}

addChild() メソッドでノードに対して子ノードを追加している。引数はやはり Node クラスインスタンスである。

childeNode.parent = this;

の部分は、引数で渡されたインスタンスの親として this を指定している。実のところ何をやっているかといえば、参照の代入、ようするにC言語風にいえばポインタの代入である。以上の処理で親子関係が構築される。

階層の実装

このクラスを使って最初にあげたディレクトリ階層を実際に実装してみるとこんな感じだ。

const root = new Node('ROOT');

const group_A = new Node('GROUP_A');
const group_B = new Node('GROUP_B');

root.addChild(group_A);
root.addChild(group_B);

const group_A_1 = new Node('GROUP_A_1');
group_A.addChild(group_A_1);

// 以下同様に...

これを実装したのちに、console.log(root); を実行してみれば、ROOTから配下へのすべてのグループへのリンクが階層というかツリーの形で構築されているのを確かめることができる。

さて、人間は欲深い生き物である。ツリーができたからには、ツリー上のどこかのノードから配下にあるノードを検索できたらいろいろと便利なので実装しなくてはいけない状況に置かれるかもしれない。

子孫検索

というわけで、ノード配下にある子孫ノードから指定した名前のノードを検索する機能を実装したいと思う。再帰処理が好きなので再帰処理で実装してみる。

ただし、ツリー階層が以下のように配下に同じ名前のノードを複数持つ場合全部を洗い出せるように実装した。例えば以下のようなディレクトリ階層があったとして「ROOT」配下の「DOCUMENTS」フォルダをすべて検索したいときなどでも使えるようにした。

ROOT - PROJECT1 - DOCUMENTS 
                - CODES
     - PROJECT2 - DOCUMENTS 
                - CODES

検索メソッドはこんな感じである。

class Node {

    /**
    * 配下のノードから指定したノード名を検索（自分自身も検索対象に含む）
    * @param {array} searchResult 検索結果を格納するための配列
    * @param {string} searchName 検索するノード名
    */
    searchChildren(searchResult, searchName) {
        if (this.name === searchName) searchResult.push(this);
        this.childrenArray.forEach(child => child.searchChildren(searchResult, searchName));
    }
}

呼び出すときはこんな感じでうまくいくはずである。

const searchResult = [];
root.searchChildren(searchResult, 'DOCUMENTS');

さて、人間は欲深い生き物である。子孫の検索ができたのなら親の検索もしたいとだれかがいいだすかもしれない。

親の検索

親の検索はこんな感じになるだろう。ROOTにたどり着いた場合、親はないのでそこで処理を止めないと落ちるので注意が必要である。

class Node {

    /**
    * 親のノードから指定したノード名を検索（自分自身も検索対象に含む）
    * @param {array[Node]} searchResult 検索結果を格納するための配列
    * @param {string} searchName 検索するノード名
    */
    searchParents(searchResult, searchName) {
        if (this.name === searchName) searchResult.push(this);
        if (this.parent === null) return;
        this.parent.searchParents(searchResult, searchName);
    }
}

さて、人間は欲深い生き物である。あるノードからツリー上にあるすべてのノードを対象にして指定の名前をもつ全てのノードを検索したい、と言い出す人がいるかもしれない。

ツリー全体の検索

ツリー全体の検索となると、あるノードから始まって親を見つけて、親の子供を検索して、その中には自分も含まれているからそれは除外して、でもって同時に自分の子孫も検索して、で、親の親の子孫も検索して兄弟やいとこも検索して、、、と考えていくとしっちゃかめっちゃかになってしまいコードがスパゲッティになってしまう。もはやヘルタースケルターである。

こういうときは深呼吸をしてポカリスエットの味を思い出しながらシンプルに考えればよい。

• まずルートまでたどり着く
• ルートから検索

で、一発である。そこでまずはルートにたどり着くメソッドを用意してあげて、そこから　searchChildren() を呼べば良いだけの話だ。ミニマルである。

class Node {

    /* 所属ツリーのルートの取得
    * @return {Node}
    */
    getRoot() {
        if (this.parent === null) return this;
        else return this.parent.getRoot();
    }

    /**
    * 自分が属するツリーから指定したノード名を検索（自分自身を検索対象に含める）
    * 　@param {array[Node]} searchResult 検索結果を格納するための配列
    * 　@param {string} searchName 検索するノード名
    */
    searchAll(searchResult, searchName) {
        const root = this.getRoot();
        root.searchChildren(searchResult, searchName);
    }

}

実行は以下のように行えば良い。

const searchResult = [];
GROUP_B_3.searchAll(searchResult, 'GROUP_A_1');

階層深度をもとめる

ツリー構造において階層の深度が数字で欲しい場合がある。以下の例でROOTは「０」、「GROUP_A, GROUP_B」は「1」、「GROUP_A_1,...」は「2」といった具合にだ。

ROOT - GROUP_A - GROUP_A_1 
               - GROUP_A_2
     - GROUP_B - GROUP_B_1 
               - GROUP_B_2
               - GROUP_B_3

せっかくなのでそのメソッドも実装しておく。

class Node {

    /* 深度の取得
    * @return {number}
    */
    getDepth() {
        if (this.parent === null) return 0;
        return this.parent.getDepth() + 1;
    }
}

実行の際は

const depth = GROUP_B_3.getDepth();
console.log(depth); // ... 2 

その他

DOM操作メソッドがどう実装されているかまで調べる時間はなかったが、今回実装した Node.addChild()は要するにDOM操作でいうところの appendChild() だ。そうやって考えればイメージしやすいと思われます。

上記の構造を利用して、KintoneAPIでcybozu.com 共通設定で設定されている、組織情報を取得、ツリー構造化する記事を書きました。
KintoneAPIで組織情報一覧を取得してツリー構造化する