如何确定元组构成的二叉树中任意元素的深度或判断其是否存在？

安全阿岳

2026-7-3

二元组生成树的存在性判断与深度计算方法

问题背景

我定义了两个操作二元组(x, y)的函数：

def f1(t: tuple[int, int]):
    x,y = t
    return (x, x + y)
def f2(t: tuple[int, int]):
    x,y = t
    return (x + y, y)

以(1,1)作为起始元组，反复调用这两个函数可生成一棵二叉树，例如(1,1)的子节点为(1,2)和(2,1)，每个节点还能继续分支。

我的问题是：如何直接判断任意二元组(a,b)是否存在于这棵树中？若存在，如何计算它的深度？

我已总结出以下规律：

树具有对称性：若(a,b)存在，则(b,a)也存在，且深度相同（比如f1(f1((1,1)))=(1,3)，对应f2(f2((1,1)))=(3,1)）。
重复调用f1会生成(1,n)形式的节点；由f2的推导可知，所有(n, n+1)形式的节点都在树中，且深度为n。
若(n,m)的两个元素均为偶数，或互为倍数，则该节点不在树中。
若m > n且m = k*n ±1（k为整数），则(n,m)存在且可计算深度，此结论源于(n, n+1)存在的事实。

我希望避免使用DFS等生成树的方式解决，这类方法会遇到“何时停止生成以判断目标不存在”的问题。

正向生成是通过f1/f2增大元素，逆向则通过减法逐步缩小元素，直到得到(1,1)（存在）或无法得到（不存在），完全无需生成树结构。

所有存在于树中的二元组(a,b)必须满足最大公约数gcd(a,b)=1：

根节点(1,1)的gcd为1；
f1(x,y)的gcd是gcd(x, x+y)=gcd(x,y)，f2(x,y)的gcd是gcd(x+y,y)=gcd(x,y)，因此所有生成节点的gcd都继承自父节点，始终为1。

这直接验证了你总结的规律：两元素均为偶数时gcd≥2，互为倍数且倍数>1时gcd等于较小元素（大于1），这类节点都不存在。

利用对称性，先假设a ≥ b（若b > a则交换两者，最终结果一致）：

若a == b：仅当a=b=1时存在（深度为0），其他情况直接判定不存在。
若b == 1：(a,1)必然存在，深度为a-1（从(1,1)重复调用f2 a-1次即可得到）。
若b > 1：
1. 计算k = a // b，r = a % b；
2. 若r == 0：说明a是b的倍数且k>1，判定不存在；
3. 若r != 0：逆向等价于从(r, b)通过k次f2操作得到(a,b)，因此累计深度增加k，接着对(b, r)重复上述逆向步骤。

5 ≥ 3，k=5//3=1，r=2，深度+1（累计1），处理(3,2)；
3 ≥ 2，k=3//2=1，r=1，深度+1（累计2），处理(2,1)；
2 ≥1，深度+1（累计3），得到(1,1)，因此(5,3)的深度为3。
正向验证：(1,1)→(2,1)→(3,2)→(5,3)，共3步，符合计算结果。

gcd(6,4)=2≠1，直接判定不存在。

内容的提问来源于stack exchange，提问作者AnthonyML