二次ツリーノードの幅を最初のインデックスで再帰的にインデックスする

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); 

パターンは明確である - しかし、どのようにプログラム的に1することができます - あまりにも多くのクロックサイクルを消費することなく（これは組み込みデバイスである） - 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などを構築してください。

Answer 1

n番目のノードを見つけるには、nを2回繰り返して残りの部分を記録したパスに従います。 1が右を意味し、0が左を意味する場合には、残りの部分によって逆に作成される「経路」に従う。例えば

、6'th項目（インデックス= 5）を追加する：
6/2 = 3（0）
3/2 = 1（1）

ルート外出先から意味右左。