algorithm - 通过广度优先索引递归索引二叉树节点

Question

问题:我需要能够通过索引从未知高度的完美二叉树中递归地检索节点。

由于高度属性未知，似乎唯一有意义的索引形式是广度优先索引(根据标题):

          0
    1           2
3       4   5       6

问题是，在每个节点似乎很难知道要采取哪个方向，以及如何将递归请求中的索引转换到该子节点......或者也许我只是没有思考清楚。

Node Navigate(Index):
Index 0: return this;
Index 1: return Left.Navigate(0);
Index 2: return Right.Navigate(0);
Index 3: return Left.Navigate(1);
Index 4: return Left.Navigate(2);
Index 5: return Right.Navigate(1);
Index 6: return Right.Navigate(2);
...
Index 7: return Left.Navigate(3);
Index 8: return Left.Navigate(4);
Index 9: return Left.Navigate(5);
Index 10: return Left.Navigate(6);
Index 11: return Right.Navigate(3);
Index 12: return Right.Navigate(4);
Index 13: return Right.Navigate(5);
Index 14: return Right.Navigate(6);

模式很清晰 - 但如何以编程方式 - 不消耗太多时钟周期(这是嵌入式设备) - 从 Index 中选择一个节点并转换 Index到该节点导航的参数？我错过了一个简单的转变吗？

---

这是我最终使用的实现，基于 yurib 的答案:

public class Node
{
  public Node Left, Right;

  public Node(int levels)
  {
      if (levels == 0) return;
      Left = new Node(levels - 1);
      Right = new Node(levels - 1);
  }

  public Node Navigate(int index)
  {
      if (index == 0) return this;

      // we want 1 based indexing.
      int oneBased = index + 1;
      // level is how many levels deep we are looking, stored as 1 << depth.
      int level = 1;  
      // find level - it's equal to the highest bit in "oneBased". Find it.
      for (int i = oneBased; (i >>= 1) != 0; )
      {
          level *= 2;
      }

      // level adjusted for our children.
      int subLevel = level >> 1;
      // clear our level bit, set our children's level bit.
      int childIndex = ((oneBased & ~level) | subLevel) - 1;

      // is the node we're looking for over half way through level? go right.
      if ((oneBased & subLevel) != 0)
          return Right.Navigate(childIndex);
      else
          return Left.Navigate(childIndex);  // otherwise it's in our left tree.
  }
}

它是用于测试的 C#，尽管实际上对 Navigate 的每次调用都是在不同的嵌入式设备上处理的，因此需要递归，而不是简单地遵循伪代码、构建 List 等。感谢 yurib : )。

Answer 1

要找到第 n 个节点，请遵循将 n 重复除以 2 并跟踪余数所创建的路径。当 1 表示向右，0 表示向左时，沿着余数反向创建的“路线”。

例如，添加第 6 个项目(索引 = 5):
6/2 = 3 (0)
3/2 = 1 (1)

这意味着从根开始向右、向左。