Блог

Есть ли какой-нибудь способ подняться по дереву непосредственно к номеру, не посещая другие ветви? Например, если у меня есть номер 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 и т.д.) элементу полного двоичного дерева.

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

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

— править —

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

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

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

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

• Узел 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
  

Я хотел «взобраться» на любую ветку или лист без доступа к ветвям, которые не мешают (если я поднимаюсь до ‘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;
}
  

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

 void solve(int n)
{
  stack<direction> path;
 //Calculate the way 
  while (n > 0)
  {
    if (n amp; 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