递归指数通过其广度优先指数

Question

问题二叉树节点：我需要能够递归通过索引检索未知高度的完美二叉树一个节点。

由于未知height属性的似乎是有道理的索引的唯一形式是广度优先索引（按照标题）：

  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＃进行测试，但在现实中每个呼叫进行浏览不同的嵌入式设备上进行处理，因此需要为递归而不是简单地跟随伪代码，建立一个List等感谢yurib :)。

Answer 1

找到第n个节点沿着通过将n重复除以2而创建的路径并跟踪其余部分。当1代表正确，0代表离开时，按照剩余部分创建的“路线”。

例如，要添加6'th项（索引= 5）：
6/2 = 3（0）
3/2 = 1（1）

从根部装置去右左。