再帰関数を使わずに木構造を処理する

ディレクトリ構造等、木構造を連想配列（jsonとか）で表現しているようなデータを再帰関数を使わずにパースします。
再帰する代わりにスタックを使いノードデータをpushしてpop（又はshift）します。本記事のサンプルは２分岐ではなく複数の枝が付いている場合の実装となります。
メモリの容量であったりノード数を制限したい場合等に有用かと思います。

実装

ソースコード

def parse(data):
    stack = data
    depth = [0] * len(data)
    preDepth = 0
    currentDepth = 1
    while len(stack) > 0:
        idepth = depth[-1] + 1
        v = stack.pop()
        d = depth.pop()
        
        # 階層が深くなった時の処理
        if d > preDepth:
            currentDepth += 1
        # 深い階層から戻ってきた時の処理
        if d < preDepth:
            currentDepth -= 1
        
        preDepth = d
        print("{}".format("    " * currentDepth), end="")
        print("{}({})".format(v["name"], d))
        if "next" in v:
            stack.extend(reversed(v["next"]))
            nsize = len(v["next"])
            depth.extend([idepth] * nsize)

def main():
    data = [
        {
            "name": "root",
            "next": [
                {
                    "name": "next1-1",
                    "next": [
                        {
                            "name": "next1-1-1",
                        }
                    ]
                },
                {
                    "name": "next1-2",
                    "next": [
                        {
                            "name": "next1-2-1",
                        },
                        {
                            "name": "next1-2-2",
                        },
                    ]
                },
                {
                    "name": "next1-3",
                    "next": [
                        {
                            "name": "next1-3-1",
                        },
                        {
                            "name": "next1-3-2",
                            "next": [
                                {
                                    "name": "next1-3-2-1",
                                },
                            ]
                        },
                    ]
                },
                {
                    "name": "next1-4",
                    "next": []
                }
            ]
        }
    ]
    parse(data)

if __name__ == "__main__":
    main()
# python main.py

実行結果

    root(0)
        next1-1(1)
            next1-1-1(2)
        next1-2(1)
            next1-2-1(2)
            next1-2-2(2)
        next1-3(1)
            next1-3-1(2)
            next1-3-2(2)
                next1-3-2-1(3)
            next1-4(1)

以上です。