我们很多时候需要个性化遍历, 但是, 此时稍微不注意就会出问题

以中序遍历为例:

正常的回调函数写法

# 回调函数写法, 是深度还是广度取决于回调函数执行的时机, 下面这个是深度写法, 广度只需在一开始执行即可
def tramid(mid,do):
    """中序遍历指定节点的子树"""    
    # 广度优先在这里直接回调
    do('广度优先')    
    s= getson(mid)  # 获取指定节点的儿子列表
    if not s: 
        do('深度优先') # 处理当前节点, 如果没有儿子, 直接返回
        return  # 如果没有儿子, 返回
    big, meid, mini = tri(s)  # 分割成哥哥、中间、弟弟三部分
    tramid(meid, do)  # 先处理中间节点
    # * 中子节点处理, 中子节点已经遍历了, 兄弟还没遍历
    # 然后也要从中间向两边处理
    while mini or big:
        if big: tramid(big.pop(), do)  # 处理哥哥节点
        if mini: tramid(mini.pop(0), do)  # 处理弟弟节点
    do('深度优先')  # 处理当前节点

优雅写法

  • 深度优先
# 优雅地yield
def traverse_gen(mid):
    s = getson(mid)
    if not s:
        yield mid
        return
    big, meid, mini = tri(s)
    if meid: yield from traverse_gen(meid)
    while mini or big:
        if big: yield from traverse_gen(big.pop())
        if mini: yield from traverse_gen(mini.pop(0))
    yield mid
  • 广度优先
# 优雅的stack
re=[]
def traverse_stack(root_id):
    stack = [root_id]
    while stack:
      	s = getson(mid)
        if not s: continue
        big, meid, mini = tri(s)
        re+=[mini]
        while mini or big:
        if big:
            stack+=[big.pop()]
        if mini:
            stack+=[mini.pop()]
  • stack搞深度中序优先, 就不那么优雅了.
# 如果stack要中序深度优先, 需要标记入栈或者再搞一个栈, 不然直接搞出来的就是先序深度优先或者中序广度优先
# 纯示例, 细节请忽略:

def traverse_post_stack(root_id, visit):
    stack = [(root_id, False)]
    while stack:
        mid, visited = stack.pop()
        if visited:
            visit(mid)  # 现在才处理节点, 处理访问过一次的节点, 这样就深度优先了.
        else:
            stack.append((mid, True))  # 标记：下次弹出时处理
            s = getson(mid)
            if not s:
                continue
            big, meid, mini = tri(s)
            for node in reversed(mini):
                stack.append((node, False))
            if meid:
                stack.append((meid, False))
            for node in reversed(big):
                stack.append((node, False))
严格中序宽度优先遍历
  • stack递归
# 逻辑简单, 清晰, 直接
def tram(mid):
    s = getson(mid)
    big, meid, mini = tri(s)
    stack=[]
    if meid: 
        yield meid
        stack.append(meid)
    while mini or big:
        if big:
            b= big.pop() 
            yield b
            stack.append(b)
        if mini: 
            m= mini.pop(0)
            yield m
            stack.append(m)
    for i in stack: yield from tram(i)
  • 单stack迭代(有点过度优化)
from collections import deque

def tram_bfs(mid):
    queue = deque([mid])
    while queue:
        nid = queue.popleft()
        s = getson(nid)
        if not s:
            yield nid
            continue
        big, meid, mini = tri(s)
        # 先 yield 并入队 meid、big、mini
        if meid:
            yield meid
            queue.append(meid)
        while mini or big:
          if big:
              b= big.pop() 
              yield b
              queue.append(b)
          if mini: 
              m= mini.pop(0)
              yield m
              queue.append(m)
# 从优化的角度讲, 这个走到了尽头
# 他优化了最小数据结构(全部只有一个stack), 且没有递归开销