[javascript]子ノードを全探査する

子ノードを取得するのはchildNodesで一発ですが、子供の子供までひっくるめて、全部のノード探索するコードを考える。

root
-node1
--node1-1
--node1-2
---node1-2-1
-node2
--node2-1

こんな感じのノードを、この順番のままにリストアップする（rootはいらない）という命題。順番が味噌です。

●再帰を使わないノード探査

最初、再帰しないで書いてみようと思った。すぐに再帰に頼りがちだけど、ループでもこんなの余裕だろうと。これが、なんとも意味なかった。
利点がないのでした。きっと、木構造の探査にありがちな、末端から上に見ていく命題にしておけばもっと簡単だったかもしれません。
コードを乗せておきます。

// 再帰しないノード探査
function　searchNodesLoop(root)
{
    var list = [];
    var stack = [];
    var node = root.firstChild;
    while (node != null)
    {
        // まず自分を処理
        list.push(node);
        // 子供の有無をチェック
        if (node.firstChild != null)
        {
            // 自身に次のノードがあればスタックに積む（戻ってこれなくなるから）
            if (node.nextSibling != null) {
                stack.push(node.nextSibling);
            }
            node = node.firstChild;
        }
        else if (node.nextSibling != null) {
            // 自分の次のノードの有無を確認
            node = node.nextSibling;
        }
        else {
            // どんづまりの場合はスタックから呼ぶ
            node = stack.pop();
        }
    }
    return list;
}

結局、小一時間くらい、あれこれやった。

●再帰を使ったノード探査

なんだかなあと釈然としなかったので、再帰するのも書いてみた。

// 再帰を使ったノード探査
function　searchNodes(root)
{
    var list = [];
    var search = function (node)
    {
        while (node != null)
        {
            // 自分を処理
            list.push(node);
            // 子供を再帰
            search(node.firstChild);
            // 次のノードを探査
            node = node.nextSibling;
        }
    }
    search(root.firstChild);
    return list;
}

めっちゃ簡単に書けた。javascriptならではなところがいくつかありますが、構造がシンプルなので、それもまたよいのではないかと。

あえて言えば、searchNodes関数内でローカルに作られるsearch関数は、関数が呼ばれるたびに作成されてしまう。これは無駄なので、クロージャーを駆使して改善しておくとよいかもしれません。この辺は可読性との兼ね合いですか。

まあこれで十分。
当然のことだけれど、再帰使わないのがよいというわけではないですね。