«Восхождение» на двоичное дерево

Question

Есть ли способ залезть на дерево прямо на номер, не посещая другие ветки?Например, если у меня есть номер 11, я должен посетить его, перейдя к 2, затем к 5, а затем к 11 без какого-либо поиска.

                                 0
                            /         \
                           /           \
                          /             \
                        1                2
                      /    \           /    \
                     /      \         /      \ 
                    3        4        5       6
                   / \      / \      / \     / \
                  /   \    /   \    /   \   /   \
                 7     8  9    10   11  12  13  14 

Я убил много раз единственное, что получилтеперь, чтобы получить первый маршрут (1 или 2) числа N, нужно (n-1) / 2, пока n не станет равным 1 или 2. Пример: (12 - 1) / 2 => (5 - 1) / 2 => 2. (7-1) / 2 => (3-1) / 2 => 1. (11-1) / 5 => (2-1) / 2 => 1. Но конецбыло бы правильно обрезать корень (0) и рассматривать 2 как новый:

          2
         / \
        /   \
       /     \
     5        6
    / \      / \
   /   \    /   \ 
  11   12  13   14

         to

          0
         / \
        /   \
       /     \
     1        2
    / \      / \
   /   \    /   \ 
  3     4  5     6

Решение:

int climb(int ID, Tree<int> t)
{

    int time = 0;
    if (tree.exists()) {
        time += t.value();
        tree t1, t2;
        t.branches(t1, t2);
        int branch = ID;
        while (branch > 2) branch = (branch - 1)/2;
        int offset = 1;
        while (offset*2 < ID - 1) offset *= 2;
        if (aux == 1) time += climb(ID - offset2/, a1);
        if (aux == 2) time += climb(ID - offset, a2);
    }
    return time;
}

Вы можете получить доступ к ЛЮБОМУ (1, 5, 13,и т. д.) элемент полного двоичного дерева.

Answer 1

Если вы хотите пропустить прохождение всех промежуточных узлов, используйте контейнер хеша (например, std::map или std::set) и поиск по хешу. Двоичные деревья предназначены для рекурсивного обхода. Обратите внимание, что set не является ассоциативным, поэтому вам придется немного обойти его.

Если вы слишком усердно пытаетесь добавить настраиваемый код / ​​переменные-члены к узлам дерева / дерева, у вас может получиться дерево, которое сильно загружает память (ответ Дэвида является очень ярким примером этого).

- редактировать -

Если ваши идентификаторы всегда представляют собой последовательность без слишком большого количества дырок (например, 0, 1, 2,..., 50 ИЛИ 68, 69,...,230,231), я рекомендую простой старый массив! Дайте мне знать, если хотите узнать больше.

В общем, мое сообщение состоит в том, чтобы сначала выбрать правильный контейнер / структуру, а затем только при необходимости внести «незначительные» изменения в саму структуру.

Answer 2

Другим способом было сделать стек:

void solve(int n)
{
  stack<direction> path;
 //Calculate the way 
  while (n > 0)
  {
    if (n & 1) // if n is odd;
      path.push_back(left);
    else
      path.push_back(right);

    n = (n - 1) / 2;
  }

  //Do actual "climbing"

  while (!path.empty())
  {
    if (path.top() == left)
    {
      go left
    }
    else
    {
      go right
    }

    path.pop();
  }
}

Спасибо Raving_Zealot от linux.org.ru

Answer 3

Я хотел «подняться» на любую ветку или лист, не имея доступа к веткам, которые не мешают (если я поднимаюсь до «4», то я иду прямо 0 -> 2 -> 4). И единственный путь, который я пропустил, был смещен, чтобы «превратить» ветку в дерево (см. Вопрос)

Я получаю смещение следующим образом:

int offset = 1;
while (offset*2 < ID - 1) offset *= 2;

Это работает для ветви '2', а смещение / 2 будет работать для ветви '1'.

int climb(int ID, Tree<int> t)
{

    int time = 0;
    if (tree.exists()) {
        time += t.value();
        tree t1, t2;
        t.branches(t1, t2);
        int branch = ID;
        while (branch > 2) branch = (branch - 1)/2;
        int offset = 1;
        while (offset*2 < ID - 1) offset *= 2;
        if (aux == 1) time += climb(ID - offset2/, a1);
        if (aux == 2) time += climb(ID - offset, a2);
    }
    return time;
}

Answer 4

Я предполагаю, что у вас есть идеальное двоичное дерево (все листья имеют одинаковую глубину, и у каждого родителя есть два дочерних элемента), а значения всех узлов такие же, как в приведенном вами примере.

В этом случае обратите внимание на следующее:

• Узел n имеет в качестве дочерних узлов узлы со значениями 2 * n + 1, 2 * n + 2
• Если вы хотите перейти к узлу с нечетным значением K, то его родителем является узел (K-1) / 2
• Если вы хотите посетить узел с четным значением K, его родителем является узел (K-2) / 2

Вы повторяете ту же процедуру, поскольку достигаете узла 0 и у вас есть все узлы, которые вам нужно посетить.

Итак, для вашего примера вы хотите посетить узел 11.

11 is odd so its parent is (11-1)/2 = 5
5 is odd so its parent is (5-1)/2 = 2
2 is even so its parent is (2-2)/0 = 0

we have reached the root node, so you have to follow the path 0->2->5->11