algorithm - 应用对数在树中导航

Question

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

我不再记得如何练习该技术。有人可以重新介绍我吗？

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

Answer 1

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

例如:

• n = 11

• 11的二进制是1011

• 我们总是忽略第一个 1，因为它会出现在每个数字中(第 n 阶的所有节点都是二进制数，有 n+1 个数字，第一个数字是 1)。我们剩下 011，表示从根部向左，然后向右，然后向右。

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

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