재귀 적으로 지수의 폭 첫 번째 인덱스

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 변환? 쉬운 변형이 빠졌습니까? 실제로 이동 호출 할 때마다 다른 임베디드 장치에서 처리하고 있지만

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 번호입니다, 따라서 필요 : 여기

---

내가 yurib의 대답에 구축하여 결국 구현입니다 단순히 의사 코드를 따르는 대신 재귀를 위해 List 등을 구축하십시오. 감사합니다. yurib :).

Answer 1

n 번째 노드를 찾으려면 n을 2로 나누고 나머지를 추적하여 생성 된 경로를 따르십시오. 1은 오른쪽을 의미하고 0은 왼쪽을 의미 할 때 역순으로 나머지에 의해 생성 된 "경로"를 따릅니다.

예컨대 6'th 항목 (인덱스 = 5)를 추가 할 :
가 6/2 = 3 (0)
3/2 = 1 (1) 루트에서 의미

이동을 오른쪽 왼쪽.