Stern-Brocot树是什么，能解释下吗？

P1797 【模板】Stern-Brocot 树 洛谷同步题解。 前置知识：\(a \perp b\) 等价于存在 \(x, y\) 使得 \(ax + by = 1\)。 Stern-Brocot 树是一个包含着所有 \(m \perp n\) 的全部非负的分数 \(\frac{m}{n}\) 的二叉树结构；其思想是从 \(0\) 阶 Stern-Brocot 序列 \(\{\frac{0}{1}, \frac{1}{0} \}\) 出发，高阶 Stern-Brocot 序列由以下递归操作定义： 对于一个 \(k\) 阶 Stern-Brocot 序列，在其任意两个相邻分数 \(\frac{m}{n}\) 与 \(\frac{m'}{n'}\) 之间插入它们的中位分数 \(\frac{m + m'}{n + n'}\) 后形成的序列即为 \(k + 1\) 阶 Stern-Brocot 序列。 例如： \(1\) 阶是 \(\{ \frac{0}{1}, \frac{1}{1}, \frac{1}{0} \}\)。 \(2\) 阶是 \(\{ \frac{0}{1}, \frac{1}{2}, \frac{1}{1}, \frac{2}{1}, \frac{1}{0} \}\)。 \(3\) 阶是 \(\{ \frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1}, \frac{3}{2}, \frac{2}{1}, \frac{3}{1}, \frac{1}{0} \}\)。 容易看作二叉树的结构： 每个分数都是 \(\frac{m + m'}{n + n'}\) 的形式，其中 \(\frac{m}{n}\) 是左上方离它最近的祖先，\(\frac{m'}{n'}\) 是右上方离它最近的祖先。 oi-wiki 上的图较为形象，大家可以看着理解下： 为什么树上的都是最简分数？为什么不会重复出现某个分数？为什么所有可能的非负的最简分数都会在树上出现？ 容易发现这样一个性质，如果 \(\frac{m}{n}\) 和 \(\frac{m'}{n'}\) 在某一阶的 Stern-Brocot 序列中相邻，那么必然满足： \[m'n - mn' = 1 \] 证明考虑数学归纳法，初始 \(0\) 阶时有 \(1 \cdot 1 - 0 \cdot 0 = 1\)；若当前 \(k\) 阶 Stern-Brocot 序列中满足条件，那么在 \(\frac{m}{n}\) 与 \(\frac{m'}{n'}\) 中间插入的 \(\frac{m + m'}{n + n'}\)，相当于要证明： \[(m' + m)n - m(n + n') = 1 \] \[m'(n + n') - (m + m') n' = 1 \] 第一个直接拆开 \(m'n + mn - mn - mn' = m'n - mn' = 1\)，第二个同理；于是得证。 同时，上面 \(m'n - mn' = 1\) 这个式子也可以说明 \(m \perp n, m' \perp n'\)，那么可以得到树上的所有分数必然是最简分数。 然后来考虑插入的分数的大小关系，显然有： \[\frac{m}{n} < \frac{m + m'}{n + n'} < \frac{m'}{n} \] 即一个中位分数在它原先两个值的中间，于是树上必然没有重复的分数。 好，接下来要证所有正的最简分数 \(\frac{a}{b}\) 都在树上出现，考虑反证法，初始显然： \[\frac{m = 0}{n = 1} < \frac{a}{b} < \frac{m' = 1}{n' = 0} \] 然后假设当前阶段有： \[\frac{m}{n} < \frac{a}{b} < \frac{m'}{n'} \] 考虑 \(\frac{m + m'}{n + n'}\) 与 \(\frac{a}{b}\) 的大小关系： 若 \(\frac{m + m'}{n + n'} = \frac{a}{b}\)，与命题矛盾，退出。 若 \(\frac{m + m'}{n + n'} < \frac{a}{b}\)，令 \(m \gets m + m', n' + n\)。 否则 \(\frac{m + m'}{n + n'} > \frac{a}{b}\)，令 \(m' \gets m + m', n' \gets n + n'\)。