从二叉树遍历到yield，然后到协程、异步

用最新的模型生成很老的知识点，一种又新又旧的学习体验。

前言

这是一篇跨越 3年 又新又旧的文章。
（或者说单纯鸽了这么久，上次写作的细节仍历历在目）

当时写作时 ChatGPT 都没落地，为了调一个 Blog 展示效果还得花上许多时间查文档，试实现。

现在 AI 的存在已经让手写 Blog 这种类似以前游戏中为了节省算力资源预先渲染好的的 “过场动画” 大部分时候没什么意义了，想要查询什么知识点的时候，直接实时生成一篇 Post，通识知识质量还高于绝大多数。

看了一下时间，正好是来上海的第一份工作，封控将要结束，从共享办公室搬到自己租的办公楼时候。

这张生成图真的太抽象了，而且我说了我是 2025年3月去的百度，不知道 2023 和 “虚桌” 是什么意思。。。

那个时候刚刚才接触云服务，又正值 AI 普及方兴未艾，面对公司都是谷歌退下来的老人，没想到自己两年后也会去百度走一遭。

一晃也真的是又 3年 过去了，再不抓紧总结点什么的话，感觉都留不下自己的痕迹。

本文理论部分大规模参考以下视频，甚至可以当成是学习读书笔记。当视频看到第4遍，同时再加上不断地应用 ayscio 相关的架构，总算把这个抽象的概念越看越具体了。

yield 是什么

yield的作用
首先yield就是return，不要想多了，所以搭配yield from func()能够递归，就是这么简单；

只是说普通的函数返回的是一个value或者obj，而yield返回的是一个生成器对象。
生成器的定义&同迭代器的区别
在python中实现了__iter__和__next__方法，可以迭代操作的对象就叫迭代器；
构建迭代器的时候，并不一次性加载所有元素到内存，只有调用next方法的时候才会返回需要的该元素；
生成器就是一种迭代器，由生成器函数返回；
生成器函数就是上文中的 return -> yield的函数；

我当年的说法本身没什么问题，但是太过流于表面，从性质进行总结，而不是真正看它怎么实现的。

源码

当前我并没有阅读 Python 源码的计划，因此仅在豆包的指导下，涉猎 Objects/genobject.c 等文件，理解了调用栈等相关概念的实现部分。

概念

要想真正知道 yield 是什么，一定要先应用，再来看概念，而不是像传统9年义务教育那样反其道而行之，此处略去应用的部分。

在一定的使用积累之后，我们对这个这个概念的感觉就没有那么抽象了。这个时候再查阅 Python 官方文档 https://docs.python.org/3/reference/expressions.html#yield-expressions

expression： 就像正则表达式，会有返回值的那种。

statement： 就像 print 语句，不会有返回值。

这里顺便提一个一个我一直搞混淆的概念 生成器表达式，会返回一个生成器。

在以前，我一直把 “列表生成式” 读做了 “列表生成器”，与本处讨论的 “生成器” 产生了不应当的混淆，对我早期学习、与面试造成了巨大的困难。

为了行文统一，我们可以像列表生成式那样，用生成器生成式来称呼它，

在文档中提到，当一个正常的 function / method 中只要出现了 yield 表达式，它就不再是一个平凡的 function / method， 而是一个生成器了。

在这里引入了生成器这个新概念，因此我们先用一点专门的篇幅去讨论。

迭代器是什么

生成器是一种迭代器，那么自然地又要先入栈一个新概念。

迭代是什么

更加自然地，我们再次入栈一个新概念： 迭代，和可迭代对象

迭代是什么

首先迭代可以是一个数学的定义，就类似于高中学习的 “递推公式” 中的这种项于项之间的关系。

迭代（英语：iteration），亦作疊代，是重复反馈过程的活动，其目的通常是为了接近并且到达所需的目标或结果。每一次对过程的重复被称为一次“迭代”，而每一次迭代得到的结果会被用来作为下一次迭代的初始值。

可迭代对象是什么

具体的来说，在 Python 里面，可以跟在 in 关键字后面的就是 可迭代对象。

抽象的来说，可迭代对象（Iterable）： 能够被迭代（遍历）的对象，作为 “数据容器”，提供迭代的 “数据来源”，但不负责迭代的具体逻辑（如 “如何获取下一个元素”“是否迭代结束”）

按照视频中的拆解 Python 实现后发现，实现了 __iter__ 方法，用来随时返回容器里面的数据的对象，就叫做可迭代对象。而且也满足上述定义：能返回自身作为被迭代的对象，且不需要知道对象之间（如何迭代）关系。

迭代器是什么

很明显的能够看到，由于可迭代对象（Iterable）只是 “数据容器”，且不知道迭代逻辑，因此不具备 “惰性计算” 的能力，还是一股脑加载到内存里面的。

在可迭代对象的基础上，再实现 __next__ 方法，体现出对象之间（如何迭代）关系，就得到了迭代器。

具体的来说：迭代器（Iterator）： 实现了迭代协议（Iterator Protocol）的对象，是 “迭代的具体执行者”—— 负责按顺序生成下一个元素、记录迭代状态、判断迭代结束。

正如同常见的 递推公式 需要知道 自己 和 之后其他项 之间（如何迭代）关系，因此迭代器 除了也有 __iter__ 方法返回它自身以外， 还有 __next__ 方法返回之后（如何迭代）关系的 “其他项”。

最贴合迭代概念的数据结构就是链表，可以通过 head指针 指向自己，再通过 self.next 属性指向下一个被迭代的项。

我们现在讲完了迭代器这个还算能有具体数据结构能对应的概念，但是我们先不急着扩展到生成器，先按照文章开头说的，应用一下。

yield 怎么应用

同样我们先从我们最熟悉的普通函数入手，看看我们能怎么实现迭代这个动作。

手动实现迭代这个动作概念

在这里我们设定一个最简单的目标： 在不借助额外数据结构的帮助下，如何迭代地输出 1, 2, 3。

迭代地输出，意味着我们要运行3次这个函数，并且每次依次返回 1, 2, 3，一次性返回肯定是不可以的。

def func():  # 普通函数
    return 1
    return 2
    return 3

print(func())
print(func())
print(func())

很自然地，我们发现 return 之后的代码不会执行，因此我们只能引入分支实现输出不同的值。

def func():  # 普通函数 + 分支
    if exection_count == 1:
        return 1
    if exection_count == 2:
        return 2
    if exection_count == 3:
        return 3

print(func())
print(func())
print(func())

想法很自然，报错的时候就发现，我们并没有定义这个用来计数的 exection_count。

最简单的做法就是把 exection_count 设计成一个全局变量，并且每次执行就增加一次。

exection_count = 1
def func():  # 普通函数 + 分支 + 全局变量（用来计数）
    if exection_count == 1:
        return 1
    if exection_count == 2:
        return 2
    if exection_count == 3:
        return 3

print(func())
exection_count += 1
print(func())
exection_count += 1
print(func())

当然这样实现的代码 func 很不独立，也有把这个 exection_count 放到 func 里面并自动 +1 的办法，这里不展开，对本文来说没有区别。

用 yield 实现迭代这个动作概念

def gen():  # 生成器函数
    yield 1
    yield 2
    yield 3

it = gen()
print(it)  # <generator object gen at 0x1066d0a90>

print(next(it))  # 1
print(next(it))  # 2
print(next(it))  # 3

print(next(it))  # StopIteration

还记得链表吗，在不追求严谨，仅为了形象的情况下，现在假设我们有一个最典型的 空值节点 作为表头的一个链表， 这个空值节点，也就是头节点，就是这里单纯为了标记整个生成器起点的 it = gen()，然后我们需要依次遍历整个链表，就需要移动沿着链表的迭代关系移动指针看，也是同样用的 next。

最后链表的尾节点的 next 指向了一个 None，再对 None.next 就会报错。

这里就没必要贴图了，假如对链表都不熟悉，那就应该去刷题，而不是再看 yield 这个概念。

同样的，优雅地遍历生成器很自然地就是：

import sys
def gen():  # 生成器函数
    yield 1
    yield 2
    yield 3

it = gen()
while True:
    try:
        print(next(it))
    except StopIteration:
        sys.exit()

yield 与树的遍历 - 写本文的契机

中序遍历一个BST

BST 是 二叉搜索树（Binary Search Tree）的缩写，也称为二叉查找树或二叉排序树。它的核心特性是：任何一个节点的左子树中所有节点的值都小于该节点的值，而右子树中所有节点的值都大于该节点的值；并且它的左、右子树本身也都是二叉搜索树。

其实这里用二叉树就可以了，但 leetcode 上用的 BST，就原封不动抄过来了。

思路

说起来这也是我刚毕业的时候面试微软的第一道题一个类型。

当访问完了一个结点准备访问它子节点的时候，很自然的接着访问 .left 或者 .right 就行。

但是这时把 visit 指针挪开了，自己当前的位置就丢掉了，比如我现在访问 .left ，等访问结束的时候，我如何才能继续访问 .right呢？

很自然的，我们需要一个清单来维护先后访问节点的顺序，不至于一旦开始访问，就丢掉了现在的位置。

使用普通函数实现 （栈）

首先有个大原则，就是选择好访问辅助 “清单” 的数据结构，当时面试微软时，我就是没有第一时间想起，浪费时间搞了心态。

其次我们都知道在《数据结构》这门课里面会学到遍历一个数据结构的时候，有 深度优先(DFS) 和 广度优先(BFS) 两种方式，如果不清楚可以先 上课 + 刷题。

然后很科学的是，先人设计出了 FIFO(先进先出)的队列，可以遍历的时候先放入当前节点，然后依次放入子节点（暂时不访问），进入子节点之前，再统一访问队列中的节点，这样就把本来树中不能直接体现的层级关系体现了出来；

同时还设计出了 LIFO(后进先出)的栈，专门用于深度优先遍历。栈的核心思想是”后进先出“：最后放入栈的元素最先被访问，这让栈天然适合实现深度优先的访问模式。

最后和本文 栈 和本文主题关系密切，必须单独一个章节描述。

为什么栈能够实现深度优先遍历？

栈的LIFO特性决定了访问顺序：优先处理最近遇到的节点。这种特性天然地实现了”深度优先“的遍历策略——总是沿着当前路径走到最深，再回退处理其他分支。

举个例子，对于树结构 A -> (B, C)，B -> (D, E)：

    A
   / \
  B   C
 / \
D   E

栈的工作过程：

• 先将根节点A入栈
• 弹出A，访问A，并将A的子节点按右左顺序入栈：先C后B（这样B会在C之前被访问）
• 弹出B，访问B，并将B的子节点按右左顺序入栈：先E后D
• 弹出E，访问E（E是叶子节点，无子节点可入栈）
• 弹出D，访问D（D是叶子节点，无子节点可入栈）
• 弹出C，访问C（C是叶子节点，无子节点可入栈）

最终访问顺序：A → B → D → E → C，完美实现了深度优先遍历。

队列 vs 栈的本质区别

• 队列(FIFO)：保证层级顺序，先遇到的节点先处理子节点，实现广度优先
• 栈(LIFO)：保证深度优先，后遇到的节点先被处理，优先探索深度方向

总结一下：
队列 vs 栈 都是辅助我们记住当前遍历属性的 “清单”， 发生在我们访问到当前节点，将要进入下一个节点之前。

现在让我们看看具体的栈实现：

import random

class TreeNode(object):  # 定义一个二叉树
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

value_list = [random.randint(1, 100) for _ in range(10)]
print(value_list)

node = TreeNode(value_list.pop(0))
node.left = TreeNode(value_list.pop(0))
node.right = TreeNode(value_list.pop(0))
node.left.left = TreeNode(value_list.pop(0))
node.left.right = TreeNode(value_list.pop(0))
node.right.left = TreeNode(value_list.pop(0))
node.right.right = TreeNode(value_list.pop(0))

result = []
stack = []

def in_order_visit(node: TreeNode):
    # 从根节点开始，一直往左走，将路径上的节点都压入栈
    current = node
    while current is not None or stack:
        # 先遍历左子树，将所有左节点压入栈
        while current is not None:
            stack.append(current)
            current = current.left

        # 弹出栈顶节点（最左边的节点）
        current = stack.pop()
        result.append(current.val)

        # 转向右子树
        current = current.right

    return result


# 测试中序遍历
result = in_order_visit(node)
print("中序遍历结果:", result)

# 验证结果是否正确 - 中序遍历应该得到升序排列（如果树是BST的话）
print("排序验证:", sorted([n.val for n in [node, node.left, node.right, node.left.left, node.left.right, node.right.left, node.right.right]]))

# 打印树结构
def print_tree(node, level=0):
    if node:
        print_tree(node.right, level + 1)
        print(' ' * 4 * level + '->', node.val)
        print_tree(node.left, level + 1)

print("\n树结构:")
print_tree(node)

我这里写完了才发现是普通二叉树，而不是搜索的，鉴于题中给定的是构造好的树，且在本文中没有区别，就不管了。

使用递归实现

递归的思想这里不展开了，请咨询查阅《数据结构》，这里想表述的是，递归会自动维护一个栈，当在函数中调用自身的时候，会将当前的变量和状态都封存到这个栈的一个帧中，因此不需要手动维护 stack = [] 这个全局变量了。

def in_order_visit(node: TreeNode):
    if node == None:  # 递归基
        return

    # 按照中序遍历的
    in_order_visit(node.left)  # 如果有左子树，则先访问左子树
    print(node.val)  # 走到这里说明访问过左子树了，现在要访问当前节点
    in_order_visit(node.right)  # 最后访问右子树

in_order_visit(node)

优雅，无需多言。 而且甚至还高度抽象，非常直观地符合中序遍历的定义。

生成器实现

既然递归可以自行维护一个栈，那么我们是不是还可以更进一步，再抽象一个高度，解放双手呢？

是的可以的。

前文已经说过使用 yield 之后，原来的函数就成为一个生成器，能够使用的时候再把栈帧加载到内存

def in_order_visit_gen(node: TreeNode):
    if node is None:
        return None

    # 有错的版本
    yield visit_bst(node.left)
    yield node.val
    yield visit_bst(node.right)


it = in_order_visit_gen(node)
while True:
    try:
        print(next(it))
    except StopIteration:
        break

当我们运行的时候，惊讶的发现，并没有像刚刚那样，直接优雅的递归进去，而是仅仅返回了生成器（不接着递归了）。

<generator object in_order_visit_gen at 0x1083ff940>
26
<generator object in_order_visit_gen at 0x1083ff940>

简单来说，想要递归一个生成器的时候，要额外使用 yield from 关键字， 优雅的提供了判断， 如果还能 next() 则递归进去， 如果到底了，则自动处理 StopIteration。

def in_order_visit_gen(node: TreeNode):  # 最终版本，优雅，简洁
    if node is None:
        return None

    yield from in_order_visit_gen(node.left)
    yield node.val
    yield from in_order_visit_gen(node.right)


it = in_order_visit_gen(node)
while True:
    try:
        print(next(it))
    except StopIteration:
        break

最终版本连递归都不需要我们维护，正如递归会自动维护一个栈一样，递归一个生成器的时候它会自动维护相关上下文，又向上屏蔽了一些细节。

由 yield from 走向协程

yield from 额外还有 双向通信 的特点，本文知识点已经够多了，这里就先省略。

生成器和迭代器的区别

话说这是之前遇到很高频的面试问题了，以前并没有系统的学习过，也只是从用法上进行了一些回答，回想起来不甚满意。

总的来说，正如之前 yield 相关的代码展示的那样， yield 自动维护了相关的计数，手动维护全局变量。

在屏蔽底层 C语言 实现的细节下，我认为我们已经阐述清楚了 迭代器 这个概念，接下来我们继续讨论生成器。

我们往底层实现来看，发现 迭代器 是很自然用了共享的 “清单” 变量，每次操作的时候，都需要维护这个 “清单” 变量，而生成器会自动的利用封存的 栈帧 来维持这个状态。

这张图是刚开始使用，没有按照 文生图 提示词规则，而是直接使用自然语言描述得到的版本，宝贵的是能明显凸显出当生成器调用 .next() 的时候，会保存栈帧这个动作，因此这张图还是保留了下来。

多进程、多线程、协程的区别

在我刚接触编程的时候，我就尝试用生活化的例子构建场景进行学习，现在终于可以轻松实现了。

根本定义：

1. 进程是 资源分配 的最小单位；
2. 线程是 CPU执行 的最小单位；
3. 异步是具有 主动释放CPU执行 能力的执行程序（与上两者完全不是一个层面的概念）。

进程:

1. 具有真正并行的能力（需要硬件 + 操作系统支持）；
2. 正所谓 “并行计算”， 是真正能同时计算执行的；

线程：

1. “并发执行”，需要疯狂切上下文，实际上一个单位时间只能有一个线程在执行；
2. 多线程本身并不能增加执行能力，除非当前有多个核心 + 语言的多线程支持多核心调用；
3. 续：Python 3.14 前的 CPython解释器的 GIL 就是在 进程级 加上了 全局互斥锁， 因此一个同一时刻只能有一个线程能够被执行，就算有多个核心，也只有一把锁。多线程本身和多进程概念并不互斥。

异步：

1. 需要代码本身有释放能力，也就是通过上文的生成器实现；
2. 需要修改之前的代码，也就是出现经典的面试题： 如果异步代码中出现了同步的代码会怎么样-会占用整个进程导致其他的协程卡死；
3. await 高度借鉴了 yield from，通过 事件循环 监控区分后面接的 可等待对象（Awaitable） 是否完成
4. 续：还没完成-就像上文中的递归，返回自己然后继续等待；完成-协程抛出 StopIteration 表示执行完成。

后记

本文从再次提笔到今天写后记，总共用时 10个 自然日，篇幅已经很长了，要是再展开协程，不知道要写到什么时候。
正如参考视频开篇提到的，只有当自己亲自总结的时候，才会发现原来对相关知识还是理解太浅薄了。

这些天查了很多资料，也高强度请教 AI， 还动手写了很多古老的代码，工作间隙也在想如何举例，润色。

没有打游戏，少量刷视频，没想到还是做了不少东西。

上周五是我人生中有一个最低谷（或者专业点，极低谷）的时候，想到放弃，想到逃避，压抑地话都说不出来。

好在开了个好头，希望我在之后的学习中能再接再厉，表现越来越好。