Предварительный заказ после прохождения заказа - PullRequest
20 голосов
/ 27 декабря 2010

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

Ответы [ 10 ]

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

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

Поскольку прохождение после заказа происходит из 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. Как добраться, осталось в качестве упражнения .

9 голосов
/ 27 декабря 2010

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

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

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

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

4 голосов
/ 05 апреля 2011

Основано на ответе Ондрея Туки.Допустимо только для 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;
 }

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

3 голосов
/ 29 июля 2018

Это код предварительного заказа на обход заказа в 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)
3 голосов
/ 18 октября 2011

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

1 голос
/ 03 февраля 2018

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

Чтобы построить дерево, нам нужно выполнить несколько основных шагов:

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

баллов -:

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

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

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

3.Там же, как и в случае с базовым правилом BST, т.е. слева, root, right

серия почтовых заказов будет L, R, N, т.е. 1,3,4,2,9,11,10,7,6

1 голос
/ 30 декабря 2017

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

#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;
} 
1 голос
/ 19 октября 2017

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

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

порядок: 1, 2, 3, 4, 6, 7, 9, 10, 11

и его порядковый номер: 1 3 4 2 9 11 10 7 6

1 голос
/ 22 января 2015

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

Нам не нужно восстанавливать 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.И мы знаем, что следующие элементы, следующие за корнем:

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

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

0 голосов
/ 27 мая 2019

Вот полный код)

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())
...