二叉树：从元素的签名中获取元素的路径
Binary trees: Getting the path of an element from its signature
假设您有一个对图像进行分类的二叉树。每个节点都是不同的二进制测试。当图像被馈送到树时，会生成一条穿过树的唯一路径。
路径被描述为与树的深度一样长的二进制字。
例如，对于一个 2 级二叉树，路径的一个例子是 (0,1)（（左，右）因此结束于树从左数第二个叶子）。
我们还假设对于任何被提供给树的图像，所有节点测试都是可执行的。因此，我们可以为任何图像定义一个签名：这个签名是一个二进制字，长度是节点数。
例如，对于 2 级二叉树，签名示例为 s = {0,1,1}
s[i]是第i个节点测试的二进制结果。
我正在寻找一种从图像签名中获取图像路径的方法。
一种天真的方法是从签名的索引跳转到具有适当递减跳跃长度的索引。
但是，我想知道是否可以按位计算得出结果（如果需要，可以重新组织签名中的索引）。
这可能吗？如果是，如何？
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 个不同的选择，因此可以在 table.
中查找路径
伪代码：
if (x&(1<<30))
x >>= 15;
path = lookup[x & 0x7fff];
lookup 是一个可以预先计算的 2**15 长度的数组。
假设您有一个对图像进行分类的二叉树。每个节点都是不同的二进制测试。当图像被馈送到树时，会生成一条穿过树的唯一路径。
路径被描述为与树的深度一样长的二进制字。
例如，对于一个 2 级二叉树，路径的一个例子是 (0,1)（（左，右）因此结束于树从左数第二个叶子）。
我们还假设对于任何被提供给树的图像，所有节点测试都是可执行的。因此，我们可以为任何图像定义一个签名：这个签名是一个二进制字，长度是节点数。
例如，对于 2 级二叉树，签名示例为 s = {0,1,1}
s[i]是第i个节点测试的二进制结果。
我正在寻找一种从图像签名中获取图像路径的方法。
一种天真的方法是从签名的索引跳转到具有适当递减跳跃长度的索引。
但是，我想知道是否可以按位计算得出结果（如果需要，可以重新组织签名中的索引）。
这可能吗？如果是，如何？
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 个不同的选择，因此可以在 table.
中查找路径伪代码：
if (x&(1<<30))
x >>= 15;
path = lookup[x & 0x7fff];
lookup 是一个可以预先计算的 2**15 长度的数组。