Prepedido de recorrido posterior al pedido

Question

Si el recorrido de pedido previo de un árbol de búsqueda binaria es 6, 2, 1, 4, 3, 7, 10, 9, 11, ¿cómo obtener el recorrido posterior al pedido?

Answer 1

Se le ha dado el recorrido de pre-pedido del árbol, que se construye haciendo: salida, recorrido a la izquierda, recorrido a la derecha.

Como el recorrido posterior a la orden proviene de una BST, puede deducir el recorrido en orden (transversal izquierda, salida, poligonal derecha) del recorrido posterior al pedido ordenando los números. En su ejemplo, el recorrido en orden es 1, 2, 3, 4, 6, 7, 9, 10, 11.

Desde dos cruces podemos construir el árbol original. Vamos a usar un ejemplo más simple para esto:

• Pre-orden: 2, 1, 4, 3
• En orden: 1, 2, 3, 4

El pre-orden de recorrido nos da la raíz del árbol como 2. El recorrido en orden nos dice que 1 cae en el subárbol izquierdo y 3, 4 cae en el subárbol derecho. La estructura del subárbol izquierdo es trivial ya que contiene un solo elemento. El recorrido de preorden del subárbol correcto se deduce tomando el orden de los elementos en este subárbol desde el recorrido de preordenamiento original: 4, 3. De esto sabemos que la raíz del subárbol correcto es 4 y del cruce en orden (3, 4) sabemos que 3 cae en el subárbol izquierdo. Nuestro árbol final es el siguiente:

2 
/\ 
1 4 
/
    3 

Con la estructura de árbol, podemos obtener el recorrido posterior a fin de recorrer el árbol: Traverse izquierda, la derecha de desplazamiento, de salida. Para este ejemplo, el recorrido post-orden es 1, 3, 4, 2.

para generalizar el algoritmo:

1. El primer elemento en el recorrido pre-orden es la raíz del árbol. Los elementos menores que la raíz forman el subárbol izquierdo. Los elementos mayores que la raíz forman el subárbol correcto.
2. Encuentra la estructura de los subárboles izquierdo y derecho usando el paso 1 con un recorrido de preorden que consiste en los elementos que trabajamos para estar en ese subárbol colocado en el orden en que aparecen en el pedido original. atravesar
3. Atraviese el árbol resultante en el pedido posterior para obtener el recorrido posterior al pedido asociado con el recorrido de preorden determinado.

Usando el algoritmo anterior, el recorrido posterior al pedido asociado con el recorrido de preorden en la pregunta es: 1, 3, 4, 2, 9, 11, 10, 7, 6. Llegar allí es dejado como un ejercicio.

Answer 2

Prepedido = obteniendo los valores de un árbol binario en el orden del nodo actual, luego el subárbol izquierdo, luego el subárbol derecho.

Post-order = obteniendo los valores de un árbol binario en el orden del subárbol izquierdo, luego el subárbol derecho, el nodo actual.

En un árbol binario búsqueda, los valores de todos los nodos en el subárbol izquierdo son menores que el valor del nodo actual; y por igual para el subárbol correcto. Por lo tanto, si conoce el inicio de un volcado de pre-pedido de un árbol de búsqueda binario (es decir, el valor de su nodo raíz), puede descomponer fácilmente todo el volcado en el valor del nodo raíz, los valores de los nodos del subárbol izquierdo y los valores de los nodos del subárbol derecho.

Para generar el árbol en el orden posterior, se aplica la recursión y la reordenación de salida. Esta tarea queda en el lector.

Answer 3

Según la respuesta de Ondrej Tucny. Válido para BST solamente
ejemplo:

 20 
    /\ 
    10 30 
    /\ \ 
    6 15 35 

Preorder = 20 10 6 15 30 35
post = 6 15 10 35 30 20

Para una BST, en preorden traversal; El primer elemento de la matriz es 20. Esta es la raíz de nuestro árbol. Todos los números en la matriz que son menores que 20 forman su subárbol izquierdo y números mayores forman el subárbol derecho.

//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; 
} 

Corrija esta información si hay algún error.

Answer 4

se le dan los resultados del recorrido de pre-pedido. a continuación, coloque los valores en un árbol de búsqueda binario adecuado y simplemente siga el algoritmo de recorrido posterior a la orden para el BST obtenido.

Answer 5

Sé que esto es viejo, pero hay una solución mejor.

No tenemos que reconstruir un BST para obtener el pedido posterior del pedido por adelantado.

Aquí es un simple código Python que lo hace de forma recursiva:

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

Salida:

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

Explicación:

Sabemos que estamos en pre-orden . Esto significa que la raíz está en el índice 0 de la lista de valores en BST. Y sabemos que los elementos siguientes de la raíz son:

• primera: los elementos menor que el root, que pertenecen al subárbol izquierdo de la raíz
• en segundo lugar: los elementos mayores que el root, que pertenecen a el subárbol derecho de la raíz

a continuación, simplemente llamamos recursivamente la función en ambos subárboles (que aún se encuentran en pre-orden) y luego se encadenan left + right + root (que es el post-orden).

Answer 6

Si se le ha dado un preorden y desea convertirlo en postorder. Entonces deberías recordar que en una BST siempre debes dar números en orden ascendente. Por lo tanto, tienes tanto Inorder como la preorden para construir un árbol.

preorden: 6, 2, 1, 4, 3, 7, 10, 9, 11

finde: 1, 2, 3, 4, 6, 7, 9, 10, 11

Y su orden posterior: 1 3 4 2 9 11 10 7 6

Answer 7

Aquí pre-ordenar el recorrido de un árbol binario de búsqueda se da en la matriz. Por lo tanto, el primer elemento de la matriz preordenar será la raíz de BST. Encontraremos la parte izquierda de BST y la parte derecha de BST.Todo el elemento en la matriz de preordenar es menor que la raíz se dejará nodo y All the element in la matriz preordenar es mayor que la raíz será el nodo derecho.

#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

Como sabemos preOrder siga las series principal, izquierda, derecha.

Para construir el árbol tenemos que seguir unos pocos pasos- básica:

su pregunta consistirá en la serie 6, 2,1,4,3,7,10,9,11

puntos- :

1. primer número de serie habrá raíz (padre), es decir, 6

2.Find el número que es mayor que 6 por lo que en esta serie 7 es primero mayor número en esta serie Así que el nodo derecho comenzará a partir de aquí y a la izquierda de este número (7) están los subárboles de la izquierda.

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

3.same manera sigue la regla básica de decir BST izquierda, raíz, derecho

la serie de orden post será L, R, N es decir 1,3,4,2,9, 11,10,7,6