algorithm - 二叉树 : Getting the path of an element from its signature

Question

假设您有一个对图像进行分类的二叉树。每个节点都是不同的二进制测试。当图像被馈送到树时，会生成一条穿过树的唯一路径。

路径被描述为与树的深度一样长的二进制词。

例如，对于一个 2 级二叉树，路径的一个例子是 (0,1)((左，右)因此结束于树从左数第二个叶子)。

我们还假设对于任何被提供给树的图像，所有节点测试都是可执行的。因此，我们可以为任何图像定义一个签名:这个签名是一个二进制字，其长度是节点的数量。

例如，对于 2 级二叉树，签名的示例是 s = {0,1,1}

s[i] 是第 i 个节点测试的二进制结果。

我正在寻找一种从图像签名中获取图像路径的方法。

一种天真的方法是从签名的索引跳转到具有适当递减跳跃长度的索引。

但是，我想知道是否可以按位计算得出结果(如果需要，可以重新组织签名中的索引)。

这可能吗？如果是，如何？

Answer 1

1 个阶段有 1 个测试。

2 个阶段有 1+2 个测试。

3 个阶段有 1+2+4 个测试。

4 个阶段有 1+2+4+8 个测试。

5 个阶段有 1+2+4+8+16=31 次测试。

更快地计算路径的一种方法是测试第一个位，然后提取对应的一组 15 位映射到接下来的 4 个阶段。只有 2**15=32768 个不同的选择，所以路径可以在表格中查找。

伪代码:

 if (x&(1<<30))
    x >>= 15;
 path = lookup[x & 0x7fff];

查找是一个 2**15 长度的数组，您可以预先计算。