Создать постзаказ из inorder и preorder

Я решал этот вопрос - Найти обход PostOrder из обходов Inorder и Preorder бинарного дерева. На GeeksForGeeks я видел следующее решение для этого:

// A utility function to search x in arr[] of size n 
static int search(int arr[], int x, int n) 
{ 
    for (int i = 0; i < n; i++) 
        if (arr[i] == x) 
            return i; 
    return -1; 
} 

// Prints postorder traversal from given inorder and preorder traversals 
static void printPostOrder(int in1[], int pre[], int n) 
{ 
    // The first element in pre[] is always root, search it in in[] to find left and right subtrees 
    int root = search(in1, pre[0], n); 

    // If left subtree is not empty, print left subtree 
    if (root != 0) 
        printPostOrder(in1, Arrays.copyOfRange(pre, 1, n), root); 

    // If right subtree is not empty, print right subtree 
    if (root != n - 1) 
        printPostOrder(Arrays.copyOfRange(in1, root+1, n), Arrays.copyOfRange(pre, 1+root, n), n - root - 1); 

    // Print root 
    System.out.print( pre[0] + " "); 
}

Теперь я знаю, что в postorder мы посещаем узел после обхода левого и правого поддеревьев, и поэтому я мог сделать вывод из комментариев в методе printPostOrder (), что сначала что-то делается с левым поддеревом, затем с правым, а затем с узлом данные печатаются. Я рисую несколько начальных рекурсивных вызовов на бумаге, и все работает нормально, но я просто не могу понять, как кто-то может придумать это решение? Меня особенно смущает утверждение, вызывающее printPostOrder для правого поддерева. Может ли кто-нибудь помочь мне понять, в чем заключается логика рекурсии и как я могу ее понять, правильно визуализировав?


recursion data-structures binary-tree tree-traversal postorder
person WarWithSelf    schedule 17.11.2019    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Пусть X будет корнем, а L и R будут левым и правым поддеревьями.

    X
  /   \
L      R

Тогда in[] будет выглядеть как

+---------+---+-------------------------+
|    L    | X |            R            |
+---------+---+-------------------------+

и pre[] будет выглядеть как

+---+---------+-------------------------+
| X |    L    |            R            |
+---+---------+-------------------------+

Чанки для L и R не будут идентичны в in и pre, они будут перемешаны, но основные наблюдения заключаются в следующем:

  1. Все элементы L занимают непрерывный блок в обоих массивах.
  2. Все элементы R занимают непрерывный блок в обоих массивах.
  3. L стоит перед R в обоих массивах.

Строка int root = search(in1, pre[0], n); находит X в позиции root в in. Как только мы это получим, мы узнаем, что:

  1. L имеет корневые элементы (все, что находится слева от X в in).
  2. L встречается в позиции 0 в in и в позиции 1 в pre.
  3. R содержит n - root - 1 элементов (все справа от X в in).
  4. R встречается в позиции root + 1 в обоих массивах.

Для ясности и согласованности код может делать копии нужной длины и смещения:

// If left subtree is not empty, print left subtree 
int lsize = root;
if (lsize != 0) 
  printPostOrder(
    Arrays.copyOfRange(in1, 0, lsize),
    Arrays.copyOfRange(pre, 1, lsize),
    lsize);

// If right subtree is not empty, print right subtree 
int rsize = n - root - 1;
if (rsize != 0) 
  printPostOrder(
    Arrays.copyOfRange(in1, root + 1, rsize),
    Arrays.copyOfRange(pre, root + 1, rsize),
    rsize);

Для повышения эффективности исходный код иногда повторно использует один и тот же массив, если начальное смещение не меняется.

Кстати, этот код выполняется за O (n ²) времени, но есть более быстрые и элегантные версии за O (n) времени .

person Cătălin Frâncu    schedule 20.11.2019