algorithm - 应用对数导航树

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

我不再记得如何练习这项技术。谁能重新介绍我？

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

最佳答案

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

例如:

n = 11

二进制的

11是1011

我们总是忽略第一个数字，因为每个数字都会有第一个数字(等级n的所有节点都是具有n + 1个数字的二进制数字，其中第一个数字为1)。我们剩下的是011，也就是说从根开始先左移，然后右移，然后右移。

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

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