Предварительный заказ для последующего обхода

Question

Если запрос обхода порядка двоичного дерева поиска равен 6, 2, 1, 4, 3, 7, 10, 9, 11, как получить обход после обхода?

Answer 1

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

Поскольку послепорядок проходит от BST, вы можете вывести обход в порядке (перемещение влево, выход, перемещение вправо) из постоперационного обхода путем сортировки чисел. В вашем примере обход в порядке 1, 2, 3, 4, 6, 7, 9, 10, 11.

Из двух обходов мы можем затем построить исходное дерево. Давайте использовать простой пример для этого:

• Предзаказ: 2, 1, 4, 3
• В-порядку: 1, 2, 3, 4

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

2 
/\ 
1 4 
/
    3 

С древовидной структурой, мы можем получить обход после заказа, идя по дереву: траверс влево, траверсы вправо, выход. Для этого примера, обход после заказа составляет 1, 3, 4, 2.

Для обобщения алгоритма:

1. Первый элемент в обход предварительного заказа является корнем дерева. Элементы меньше корня образуют левое поддерево. Элементы, большие, чем корень, образуют правое поддерево.
2. Найдите структуру левого и правого поддеревьев с помощью шага 1 с предварительным обходом, состоящим из элементов, которые мы разработали, чтобы быть в этом поддереве, размещенном в том порядке, в котором они отображаются в исходном предзаказе ВТП.
3. Пройдите по полученному дереву в пост-порядке, чтобы получить обход после заказа, связанный с данным обходом предварительного заказа.

Используя вышеприведенный алгоритм, обход послепорядка, связанный с обходным порядком в задаче: 1, 3, 4, 2, 9, 11, 10, 7, 6. Как добраться как упражнение.

Answer 2

Предварительный заказ = вывод значений двоичного дерева в порядке текущего узла, затем левого поддерева, а затем правого поддерева.

Post-order = вывод значений двоичного дерева в порядке левого поддерева, а затем правое поддерево, текущий узел.

В двоичном формате поиск дерево, значения всех узлов в левом поддереве меньше, чем значение текущего узла; и одинаково для правильного поддерева. Следовательно, если вы знаете начало дампа предварительного заказа двоичного дерева поиска (то есть его значение корневого узла), вы можете легко разложить весь дамп на значение корневого узла, значения узлов левого поддерева и значения узлы правого поддерева.

Для вывода дерева в пост-порядке применяется рекурсивное и выходное переупорядочение. Эта задача оставлена ​​читателю.

Answer 3

Основано на ответе Ondrej Tucny. Действительно для BST только
пример:

 20 
    /\ 
    10 30 
    /\ \ 
    6 15 35 

Предзаказ = 20 10 6 15 30 35
сообщение = 6 15 10 35 30 20

Для BST, В обходе; первый элемент массива равен 20. Это корень нашего дерева. Все числа в массиве, которые меньше 20, образуют левое поддерево и большее число образуют правое поддерево.

//N = number of nodes in BST (size of traversal array) 
int post[N] = {0}; 
int i =0; 

void PretoPost(int pre[],int l,int r){ 
    if(l==r){post[i++] = pre[l]; return;} 
    //pre[l] is root 
    //Divide array in lesser numbers and greater numbers and then call this function on them recursively 
    for(int j=l+1;j<=r;j++) 
     if(pre[j]>pre[l]) 
      break; 
    PretoPost(a,l+1,j-1); // add left node 
    PretoPost(a,j,r); //add right node 
    //root should go in the end 
    post[i++] = pre[l]; 
    return; 
} 

Пожалуйста, исправьте меня, если есть какая-либо ошибка.

Answer 4

Вам даны результаты обхода по порядку. затем поместите значения в подходящее дерево двоичного поиска и просто следуйте алгоритму последующего обхода для полученного BST.

Answer 5

Я знаю, что это старый, но есть лучшее решение.

Нам не нужно восстанавливать BST, чтобы получить пост-порядок из предварительного заказа.

Вот простой питон код, который делает это рекурсивно:

import itertools 

def postorder(preorder): 
    if not preorder: 
     return [] 
    else: 
     root = preorder[0] 
     left = list(itertools.takewhile(lambda x: x < root, preorder[1:])) 
     right = preorder[len(left) + 1:] 
     return postorder(left) + postorder(right) + [root] 

if __name__ == '__main__': 
    preorder = [20, 10, 6, 15, 30, 35] 
    print(postorder(preorder)) 

Выход:

[6, 15, 10, 35, 30, 20] 

Объяснение:

Мы знаем, что мы находимся в предзаказа , Это означает, что корень находится в индексе 0 из списка значений в BST. И мы знаем, что следующие элементы корня являются:

• первый: элементы меньше root, которые принадлежат левого поддерева корня
• второй: элементы больше, чем root, которые принадлежат правое поддерево корня

затем мы просто называем рекурсивно функцию на обоих поддеревьев (которые до сих пор находятся в предварительном порядке), а затем цепь left + right + root (которая является пост-заказ).

Answer 6

Если вы получили предварительный заказ и хотите преобразовать его в постобработку. Тогда вы должны помнить, что в BST для того, чтобы всегда давать числа в порядке возрастания. Таким образом, у вас есть как Inorder, так и preorder для построения дерева.

предзаказ: 6, 2, 1, 4, 3, 7, 10, 9, 11

Симметричного: 1, 2, 3, 4, 6, 7, 9, 10, 11

И его postorder: 1 3 4 2 9 11 10 7 6

Answer 7

Здесь обходе бинарного дерева поиска задается в массиве. Итак, первый элемент массива предварительного заказа будет иметь корень из BST. Мы найдем левую часть BST и правую часть BST. Все элементы в массиве предзаказов меньше, чем root, будут левым узлом и всем элементом в массив предзаказов больше, чем root, будет правильным узлом.

#include <bits/stdc++.h> 
using namespace std; 
int arr[1002]; 
int no_ans = 0; 
int n = 1000; 
int ans[1002] ; 
int k = 0; 

int find_ind(int l,int r,int x){ 
    int index = -1; 
    for(int i = l;i<=r;i++){ 
     if(x<arr[i]){ 
      index = i; 
      break; 
     } 
    } 
    if(index == -1)return index; 
    for(int i =l+1;i<index;i++){ 
     if(arr[i] > x){ 
      no_ans = 1; 
      return index; 
     } 
    } 
    for(int i = index;i<=r;i++){ 
     if(arr[i]<x){ 
      no_ans = 1; 
      return index; 
     } 
    } 
    return index; 

} 

void postorder(int l ,int r){ 

    if(l < 0 || r >= n || l >r) return; 
    ans[k++] = arr[l]; 
    if(l==r) return; 
    int index = find_ind(l+1,r,arr[l]); 
    if(no_ans){ 
     return; 
    } 
    if(index!=-1){ 
     postorder(index,r); 
     postorder(l+1,index-1); 
    } 
    else{ 
     postorder(l+1,r); 
    } 
} 

int main(void){ 

    int t; 
    scanf("%d",&t); 
    while(t--){ 
     no_ans = 0; 
     int n ; 
     scanf("%d",&n); 

     for(int i = 0;i<n;i++){ 
      cin>>arr[i]; 
     } 
     postorder(0,n-1); 
     if(no_ans){ 
      cout<<"NO"<<endl; 
     } 
     else{ 

      for(int i =n-1;i>=0;i--){ 
       cout<<ans[i]<<" "; 
      } 
      cout<<endl; 
     } 
    } 

    return 0; 
} 

Answer 8

Как мы знаем, preOrder следует за родителями, слева, справа.

Для построения дерева мы должны следовать несколько основных steps-:

Ваш вопрос состоит из серии 6, 2,1,4,3,7,10,9,11

процентного пункта :

1. Первый номер серии будет корень (родительский), т.е. 6

2.Find число, которое больше, чем 6 так что в этой серии 7 является первым большее число в этой серии s, так что правый узел будет начинаться отсюда и оставлен до этого числа (7) - это ваши левые поддеревья.

     6 
        / \ 
        2  7 
       /\  \ 
       1 4  10 
        / /\ 
        3  9 11 

3.same путь следовать основному правилу BST, т.е. слева, корень, правый

серия после того, будет L, R, N т.е. 1,3,4,2,9, 11,10,7,6