应用对数来导航树

我曾经知道一种使用对数从树的一片叶子移动到树的下一个“有序”叶子的方法。我认为它涉及获取“当前”叶子的位置值（排名？）并将其用作从根向下到新目标叶子的新遍历的种子 - 一直使用对数函数测试来确定是否沿着右或左节点向下到达叶子。

我已经不记得如何运用这项技术了。有谁可以重新介绍一下我吗？

我也不记得该技术是否要求树是平衡的，或者它是否适用于 n 树或仅适用于二叉树。任何信息，将不胜感激。

既然您提到了向左还是向右，我假设您正在专门讨论二叉树。在这种情况下，我认为你是对的，有办法。如果您的节点从左到右、从上到下编号，从 1 开始，那么您可以通过取节点编号的 log2 来找到排名（树中的深度）。要从根再次找到该节点，可以使用数字的二进制表示形式，其中 0 = 左，1 = 右。

例如：

• n = 11

• 11的二进制是1011

• 我们总是忽略前一个 1，因为它对于每个数字都会存在（等级 n ​​的所有节点都将是具有 n+1 位的二进制数，第一位数字是 1）。我们剩下 011，这表示从根开始向左，然后向右，然后向右。

如果要找到下一个有序叶子，请获取当前叶子的编号并加一，然后使用此方法从根开始遍历。

我相信这只适用于平衡二叉树。