Предварительный заказ на постобработку
Если предварительный обход двоичного дерева поиска равен 6, 2, 1, 4, 3, 7, 10, 9, 11, как получить обход после обхода?
Ответы
Ответ 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 с предварительным обходом, состоящим из элементов, которые мы разработали, чтобы быть в этом поддереве, помещенном в том порядке, в котором они появляются в исходном предзаказе ВТП.
- Поверните полученное дерево в пост-порядке, чтобы получить обход после заказа, связанный с данным обходом предварительного порядка.
Используя вышеприведенный алгоритм, обход послепорядка, связанный с обходным порядком в вопросе, равен: 1, 3, 4, 2, 9, 11, 10, 7, 6. Как только вы пройдете упражнение.
Ответ 2
Предзаказ= вывод значений двоичного дерева в порядке текущего node, затем левого поддерева, затем правого поддерева.
Post-order= вывод значений двоичного дерева в порядке левого поддерева, затем правое поддерево, текущий node.
В двоичном дереве поиска значения всех узлов в левом поддереве меньше значения текущего node; и одинаково для правильного поддерева. Следовательно, если вы знаете начало дампа предзадачного двоичного дерева поиска (т.е. Его корневое значение node), вы можете легко разложить весь дамп в корневом значении node, значениях левых узлов поддерева, и значения узлов правого поддерева.
Для вывода дерева в пост-порядке применяется реорганизация рекурсии и вывода. Эта задача оставлена читателю.
Ответ 3
На основе ответа Ondrej Tucny. Действует только для BST
Пример:
20
/ \
10 30
/\ \
6 15 35
Предзаказ = 20 10 6 15 30 35
Post = 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;
}
Пожалуйста, исправьте меня, если есть какая-либо ошибка.
Ответ 4
вам будут предоставлены результаты обхода порядка. затем поместите значения в подходящее дерево двоичного поиска и просто следуйте алгоритму обхода после заказа для полученного BST.
Ответ 5
Это код предварительного заказа на обход заказа в Python. Я строю дерево, чтобы вы могли найти любой тип обхода
def postorder(root):
if root==None:
return
postorder(root.left)
print(root.data,end=" ")
postorder(root.right)
def preordertoposorder(a,n):
root=Node(a[0])
top=Node(0)
temp=Node(0)
temp=None
stack=[]
stack.append(root)
for i in range(1,len(a)):
while len(stack)!=0 and a[i]>stack[-1].data:
temp=stack.pop()
if temp!=None:
temp.right=Node(a[i])
stack.append(temp.right)
else:
stack[-1].left=Node(a[i])
stack.append(stack[-1].left)
return root
class Node:
def __init__(self,data):
self.data=data
self.left=None
self.right=None
a=[40,30,35,80,100]
n=5
root=preordertoposorder(a,n)
postorder(root)
# print(root.data)
# print(root.left.data)
# print(root.right.data)
# print(root.left.right.data)
# print(root.right.right.data)
Ответ 6
Я знаю, что это старо, но есть лучшее решение.
Нам не нужно восстанавливать BST, чтобы получить пост-порядок из предварительного заказа.
Вот простой код python, который делает это рекурсивно:
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, которые принадлежат левому поддереву корня
- second: элементы, превышающие
root, которые принадлежат правому поддереву корня
Затем мы просто вызываем рекурсивно функцию на обоих поддеревах (которые все еще находятся в предварительном порядке), а затем цепочка left + right + root (которая является пост-порядком).
Ответ 7
Если вам задан предварительный заказ, и вы хотите преобразовать его в постобработку. Тогда вы должны помнить, что в BST для того, чтобы всегда давать числа в порядке возрастания. Таким образом, у вас есть как Inorder, так и preorder для построения дерева.
preorder: 6, 2, 1, 4, 3, 7, 10, 9, 11
inorder: 1, 2, 3, 4, 6, 7, 9, 10, 11
И его postorder: 1 3 4 2 9 11 10 7 6
Ответ 8
Здесь предваряется обход дерева двоичного поиска в массиве.
Таким образом, первый элемент массива предзаказов будет корневым из BST. Мы найдем левую часть BST и правую часть BST. Все элементы в массиве предзаказов меньше, чем root, будут оставлены node и весь элемент в массиве pre-order больше корня будет правильным node.
#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;
}
Ответ 9
Как мы знаем, preOrder следует за родительскими, левыми, правыми рядами.
Чтобы построить дерево, нужно выполнить несколько простых шагов:
ваш вопрос состоит из серии 6, 2,1,4,3,7,10,9,11
Точки -:
- Первое число серий будет root (parent) i.e 6
2. Найдите число, большее 6, поэтому в этой серии 7 первое большее число в этой серии, поэтому справа node будет начинаться отсюда, а слева до этого числа (7) - ваши левые поддеревья.
6
/ \
2 7
/ \ \
1 4 10
/ / \
3 9 11
3.Затем следовать основному правилу BST i.e left, root, right
серия почтовых заказов будет L, R, N, т.е. 1,3,4,2,9,11,10,7,6
Ответ 10
Вот полный код)
class Tree:
def __init__(self, data = None):
self.left = None
self.right = None
self.data = data
def add(self, data):
if self.data is None:
self.data = data
else:
if data < self.data:
if self.left is None:
self.left = Tree(data)
else:
self.left.add(data)
elif data > self.data:
if self.right is None:
self.right = Tree(data)
else:
self.right.add(data)
def inOrder(self):
if self.data:
if self.left is not None:
self.left.inOrder()
print(self.data)
if self.right is not None:
self.right.inOrder()
def postOrder(self):
if self.data:
if self.left is not None:
self.left.postOrder()
if self.right is not None:
self.right.postOrder()
print(self.data)
def preOrder(self):
if self.data:
print(self.data)
if self.left is not None:
self.left.preOrder()
if self.right is not None:
self.right.preOrder()
arr = [6, 2, 1, 4, 3, 7, 10, 9, 11]
root = Tree()
for i in range(len(arr)):
root.add(arr[i])
print(root.inOrder())
Ответ 11
Поскольку это бинарное дерево поиска, обход по порядку всегда будет отсортированными элементами. (левый & lt; корень & lt; правый)
Таким образом, вы можете легко записать результаты его обхода в порядке: 1,2,3,4,6,7,9,10,11
Предзаказ: 6, 2, 1, 4, 3, 7, 10, 9, 11
По порядку: слева, корень, право
Предварительный заказ: root, left, right
Пост-заказ: слева, справа, корень
Теперь мы получили предварительный заказ, корень равен 6.
Теперь, используя результаты по порядку и предзаказу:
Шаг 1:
6
/ \
/ \
/ \
/ \
{1,2,3,4} {7,9,10,11}
Шаг 2: следующий корень, используя обратный порядок, 2:
6
/ \
/ \
/ \
/ \
2 {7,9,10,11}
/ \
/ \
/ \
1 {3,4}
Шаг 3. Аналогично, следующий корень - 4:
6
/ \
/ \
/ \
/ \
2 {7,9,10,11}
/ \
/ \
/ \
1 4
/
3
Шаг 4: следующий корень равен 3, но нет другого элемента, который можно было бы разместить в дочернем дереве для "3". Учитывая следующий корень как 7 сейчас,
6
/ \
/ \
/ \
/ \
2 7
/ \ \
/ \ {9,10,11}
/ \
1 4
/
3
Шаг 5. Следующий корень - 10:
6
/ \
/ \
/ \
/ \
2 7
/ \ \
/ \ 10
/ \ / \
1 4 9 11
/
3
Таким образом, вы можете построить дерево и, наконец, найти его обход после заказа, а именно: 1, 3, 4, 2, 9, 11, 10, 7, 6
