Рекурсивно индексировать бинарный узел дерева по ширине первого индекса

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 в параметр для Navigate для этого узла? Я пропускаю простое преобразование?

---

Вот реализация, которую я в итоге использовал, опираясь на ответ Юриба:

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 на два и отслеживания остатка. следуйте «маршруту», созданному остатком в обратном порядке, когда 1 означает правое, а 0 означает левое.

например, чтобы добавить 6-й элемент (индекс = 5):
6/2 = 3 (0)
3/2 = 1 (1)

это означает, что от корня идите направо, налево.