binarytree二叉树节点DFS深度优先搜索遍历，基于栈，非递归，python

注意对已经访问过的节点的处理，在while循环中，如果在栈回退时候，遇到之前访问过的节点，则直接弹出。弹出的情况还有一种就是该节点没有左右子节点了，表明到了尽头。

import random

from binarytree import build

def app():
    data = []
    for i in range(8):
        data.append(i)
    random.shuffle(data)

    root = build(data)
    root.pprint(index=True, delimiter=',')

    nodes = my_travel_dfs(root)
    print('深度遍历', nodes)

# 深度遍历，从左至右
def my_travel_dfs(root):
    visit_path = []
    stack = [root[0]]

    while True:
        print('-----')

        if len(stack) == 0:
            break

        visit_node = stack[0]
        print('访问', visit_node.value)

        if visit_node in visit_path:
            print(visit_node.value, '已经访问')
            print('弹出', stack[0].value)
            del (stack[0])

            continue
        else:
            visit_path.append(visit_node)

        left_node = visit_node.left
        right_node = visit_node.right

        if right_node != None:
            stack.insert(0, right_node)
        if left_node != None:
            stack.insert(0, left_node)

        if left_node == None and right_node == None:
            print('弹出', stack[0].value)
            del (stack[0])

        print('stack', stack)
        print('search_path', visit_path)

    return visit_path

if __name__ == '__main__':
    app()

输出：

_____0,2_____
          /             \
       _1,5_           _2,0_
      /     \         /     \
   _3,6     4,3     5,1     6,7
  /
7,4

-----
访问 2
stack [Node(5), Node(0), Node(2)]
search_path [Node(2)]
-----
访问 5
stack [Node(6), Node(3), Node(5), Node(0), Node(2)]
search_path [Node(2), Node(5)]
-----
访问 6
stack [Node(4), Node(6), Node(3), Node(5), Node(0), Node(2)]
search_path [Node(2), Node(5), Node(6)]
-----
访问 4
弹出 4
stack [Node(6), Node(3), Node(5), Node(0), Node(2)]
search_path [Node(2), Node(5), Node(6), Node(4)]
-----
访问 6
6 已经访问
弹出 6
-----
访问 3
弹出 3
stack [Node(5), Node(0), Node(2)]
search_path [Node(2), Node(5), Node(6), Node(4), Node(3)]
-----
访问 5
5 已经访问
弹出 5
-----
访问 0
stack [Node(1), Node(7), Node(0), Node(2)]
search_path [Node(2), Node(5), Node(6), Node(4), Node(3), Node(0)]
-----
访问 1
弹出 1
stack [Node(7), Node(0), Node(2)]
search_path [Node(2), Node(5), Node(6), Node(4), Node(3), Node(0), Node(1)]
-----
访问 7
弹出 7
stack [Node(0), Node(2)]
search_path [Node(2), Node(5), Node(6), Node(4), Node(3), Node(0), Node(1), Node(7)]
-----
访问 0
0 已经访问
弹出 0
-----
访问 2
2 已经访问
弹出 2
-----
深度遍历 [Node(2), Node(5), Node(6), Node(4), Node(3), Node(0), Node(1), Node(7)]