-4

例如：-有以二叉树结构连接的计算机。有 20 个房间，将每个房间视为二叉树中的一个级别，从房间 0（级别 0）开始，主计算机放置在其中，其所有子节点（计算机）都在房间 1（级别 1）中，依此类推。每台计算机根据其在房间中的位置进行编号，例如计算机 1、计算机 2、计算机 3 和计算机 4（房间 2 中计算机的最大数量等于 2 的 2 次幂）在房间 1（级别 1）中。现在从如果我想访问 12 号房间的计算机 756，那么最快的算法或方法是什么？

以上图为例，级别 4 共有 16 个节点（例如 1 到 16），即 2 的 4 次幂。如果树很大（例如树有 50 级），这是访问编号为的节点的最快算法50级时1,099,511,628,800

4

1 回答 1

4

如果我正确理解了您的问题，N并且L您希望找到从根到第th 级别的N第 th 节点的路径。L我将假设每个级别中的节点从左到右编号，N并且L从零开始。

如果您使用 的二进制表示，这很简单N： 表示N为二进制L位数。现在从最高有效位到最低有效位遍历这些位。0 表示你需要去左边的孩子，1 表示你需要去右边的孩子。

例如，要在级别 #3 中查找节点 #3：二进制中的节点编号为011. 所以从根本上，你向左、向右、向右。

于 2013-09-15T18:05:18.367 回答