Преобразовать индекс обхода двоичного дерева после заказа в индекс уровня порядка (в ширину) - PullRequest
Новая
       23

Преобразовать индекс обхода двоичного дерева после заказа в индекс уровня порядка (в ширину)

4 голосов
/ 21 декабря 2010

Предполагая полное двоичное дерево, каждый узел может быть адресован той позицией, в которой он находится в данном алгоритме обхода дерева.

Например, индексы узла простого полного дерева с высотой 3 будут выглядеть следующим образом:

ширина вначале (иначе уровень порядка): 

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

постпорядок сначала: 

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

Высота дерева и индекса впредоставляется обратный порядок заказа.

Как я могу рассчитать первый индекс ширины на основе этой информации?

Ответы [ 2 ]

2 голосов
/ 21 декабря 2010

Я думаю, что это должно быть вычислено итеративно / рекурсивно.Сказав это, кто-то придет через 37 секунд с простым однострочным вычислением и понизит меня.Тем не менее, это может быть решено путем рекурсивного мышления.Рассмотрим простое дерево (основанное на 1) прохождения первого порядка в глубину: 

   3
  / \
 1   2

С рекурсивной точки зрения это все, о чем вы должны думать.Вы находитесь либо в корне поддерева (3), либо в левой части поддерева (1), либо в правой части (2).Если вы находитесь в корне, то все готово.В противном случае левое и правое поддеревья идентичны, а индекс обхода после заказа в правом поддереве равен соответствующему индексу левого поддерева + числу узлов в поддереве.

Следующий код выполняет это вычисление вO(log n).Для дерева с глубиной 10 (1023 узла) оно вычисляет значение индекса максимум за 10 итераций (рекурсии).

Отслеживает глубину заданного узла и вычисляет позицию строки в ширину в зависимости от того, имеет ли он дело с левым или правым поддеревом.Обратите внимание, что здесь используются значения индекса на основе 1.Мне было проще думать об этом в этих терминах (дерево глубины 2 содержит 3 узла, а самый верхний узел в обходе после заказа равен 3).Также обратите внимание, что он считает, что глубина дерева 1 имеет один узел (я не уверен, является ли это типичным соглашением или нет). 

// Recursively compute the given post-order traversal index's position
// in the tree:  Its position in the given level and its depth in the tree.
void ComputePos( int treedepth, int poindex, int *levelposition, int *nodedepth )
{
    int nodes;
    int half;

    // compute number of nodes for this depth.
    assert( treedepth > 0 );
    nodes = ( 1 << ( treedepth )) - 1;
    half = nodes / 2;   // e.g., 7 / 2 = 3

    //printf( "poindex = %3d, Depth = %3d, node count = %3d", poindex, treedepth, nodes );

    (*nodedepth)++;

    if ( poindex == nodes ) {
        // This post-order index value is the root of this subtree
        //printf( "  Root\n" );
        return;
    }
    else if ( poindex > half ) {
        // This index is in the right subtree
        //printf( "  Right\n" );
        poindex -= half;
        *levelposition = 2 * *levelposition + 1;
    }
    else {
        // Otherwise it must be in the left subtree
        //printf( "  Left\n" );
        *levelposition = 2 * *levelposition;
    }

    treedepth -= 1;
    ComputePos( treedepth, poindex, levelposition, nodedepth );
}

int main( int argc, char* argv[] )
{
    int levelposition = 0;   // the 0-based index from the left in a given level
    int nodedepth = 0;  // the depth of the node in the tree
    int bfindex;
    int treedepth = atoi( argv[1] );   // full depth of the tree (depth=1 means 1 node)
    int poindex = atoi( argv[2] ); // 1-based post-order traversal index

    ComputePos( treedepth, poindex, &levelposition, &nodedepth );

    //printf( "ComputePos( %d, %d ) = %d, %d\n", treedepth, poindex, levelposition, nodedepth );

    // Compute the breadth-first index as its position in its current
    // level plus the count of nodex in all the levels above it.
    bfindex = levelposition + ( 1 << ( nodedepth - 1 ));
    printf( "Post-Order index %3d = breadth-first index %3d\n", poindex, bfindex );

    return 0;
}

Вот значения, вычисленные для следующего дерева (глубина4), который показывает значения индекса прохождения после заказа (на основе 1).

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


[C:\tmp]for /l %i in (1,1,15) do po2bf 4 %i
Post-Order index   1 = breadth-first index   8
Post-Order index   2 = breadth-first index   9
Post-Order index   3 = breadth-first index   4
Post-Order index   4 = breadth-first index  10
Post-Order index   5 = breadth-first index  11
Post-Order index   6 = breadth-first index   5
Post-Order index   7 = breadth-first index   2
Post-Order index   8 = breadth-first index  12
Post-Order index   9 = breadth-first index  13
Post-Order index  10 = breadth-first index   6
Post-Order index  11 = breadth-first index  14
Post-Order index  12 = breadth-first index  15
Post-Order index  13 = breadth-first index   7
Post-Order index  14 = breadth-first index   3
Post-Order index  15 = breadth-first index   1
0 голосов
/ 21 декабря 2010

Перебор, пока не найдете лучший ответ:

  1. Построить дерево из массива / индекса после заказа, сделав значение каждого узла текущим индексом массива.

Поглощение индекса: первая половина индекса - это ваше левое поддерево, вторая половина - ваше правое поддерево, средний узел - корень. Рекурс для каждого поддерева.

  1. Пройдите по дереву в ширину, поместив рассчитанный индекс в ширину в карту в качестве значения сопоставленной пары с ключом значения узла. map.put( node.value, tree_visitor.current_index)

  2. Опросить карту, передавая требуемый ключ (который является индексом узла после заказа), чтобы получить индекс соответствующего узла ширины в первом.

...