pythonツリー遍歴

pythonを使用して実装されたツリー遍歴(幅優先と深さ優先を含む)

ef dfs():
    tree = {
        'A': ['B', 'C'],
        'B': ['D', 'E'],
        'C': ['F', 'G'],
        'D': ['H', 'I'],
        'E': [],
        'F': [],
        'G': [],
        'H': [],
        'I': []
    }
    leaf = []
    to_crawl = deque(['A'])
    while to_crawl:
        current = to_crawl.popleft()
        print current, to_crawl
        children = tree[current]
        if len(children)> 0:
            # width first
            # to_crawl.extend(children)
            # depth first
            to_crawl.extendleft(children[::-1])
            print to_crawl
        else:
            leaf.append(current)
    print leaf

図の遍歴については少し調整すればよいが,主に図が考慮すべき重複遍歴の問題であるため,どのノードを遍歴したかを記録し,新しいchildrenを得るたびに遍歴したノードを減算すればよい.