找出元素是否在左子树或右子树中的最快方法

Question

如果构建二叉树如下

• 根是 1
• 元素 n 的左子元素是 2*n
• 元素 n 的右子元素是 (2*n)+1

如果我得到一个数字 n，找出它是在根的左子树还是右子树中的最快方法是什么？左子树是否有一些容易确定的数学性质？

注意：这不是一个家庭作业问题，尽管它是我试图解决的一个更大的算法问题的一部分。

Answer 1

考虑二进制数字。每个子级都是父级编号，根据它是在左边还是在右边，在其后面附加 0 或 1。

这意味着根左侧的所有内容将以二进制形式从 10 开始，而右侧的所有内容将以二进制形式从 11 开始。

这意味着您应该能够仅使用一些移位操作然后进行一些比较来确定它位于哪一侧。

我应该注意，我不知道这是否是最有效的方法，但它很容易确定左子树的数学属性。

正如其他人所指出的，0 或 1 附加的结果意味着每个数字都对通过子树的路径进行编码。第一个 1 代表树的根，从那时起，0 表示在该点选取左分支，1 表示选取右分支。

因此，二进制 1001101 表示左、左、右、右、左、右。

这样做的一个明显的结果是，二进制数字的数量将准确确定该数字在树中的深度。所以 1 是顶层（第 1 级）。10 将处于第二级（做出一项选择）。我的示例 1001101 将位于第 7 级（做出了六个选择）。我应该注意，我不熟悉二叉树术语，因此不确定根通常是否被视为第一级或零级，这就是为什么我也明确说明所做选择的数量。

最后一个观察（如果尚未观察到）是，数字也将从上到下、从左到右计数。所以第一层是1。下一层是左边2，右边3。下面的级别将是 4、5、6、7，然后是 8、9、10、11、12、13、14、15 等下面的行。这在数学上不再有用，但如果您尝试可视化它可能会有所帮助。