algorithm - breadth - Pre-order para post-order recorrido

preorder tree c++

Question

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

Answer 1

Basado en la respuesta de Ondrej Tucny. Válido solo para BST
ejemplo:

     20  
    /  /  
   10  30  
   //    /  
  6  15   35  

Preorden = 20 10 6 15 30 35
Mensaje = 6 15 10 35 30 20

Para un BST, In Preorder 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 los números mayores forman un 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;
 }

Por favor corrígeme si hay algún error.

Answer 2

Como ya sabemos, siga las series de padres, izquierda, derecha.

Para construir un árbol necesitamos seguir algunos pasos básicos:

tu pregunta consiste en la serie 6, 2,1,4,3,7,10,9,11

puntos-:

1. El primer número de la serie será root (padre), es decir, 6

2. Encuentre el número que es mayor que 6, por lo que en esta serie 7 es el primer número mayor en esta serie, por lo que el nodo derecho comenzará a partir de aquí y, a la izquierda, a este número (7) se encuentra su subárbol izquierdo.

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

3. De la misma manera, siga la regla básica de BST, es decir, izquierda, raíz, derecha

La serie de pedidos posteriores será L, R, N, es decir, 1,3,4,2,9,11,10,7,6.

Answer 3

En este caso, el recorrido previo a la orden de un árbol de búsqueda binario se da en una matriz. Por lo tanto, el primer elemento de la matriz de pedidos anticipados 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 pedidos anticipados es menor que la raíz será el nodo izquierdo y Todo el elemento en pre -la matriz de orden 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 4

Este es el código de preorder para postorder recorrido en python. Estoy construyendo un árbol para que puedas encontrar cualquier tipo de recorrido.

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)

Answer 5

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

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

Aquí hay un código de Python simple que lo hace recursivamente:

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 los valores en el BST. Y sabemos que los elementos que siguen a la raíz son:

• Primero: los elementos menos que la root , que pertenecen al subárbol izquierdo de la raíz.
• segundo: los elementos mayores que la root , que pertenecen al subárbol derecho de la raíz

Luego simplemente llamamos recursivamente a la función en ambos subárboles (que todavía están en pre-orden) y luego encadenamos left + right + root (que es el post-order).

Answer 6

Se le da el recorrido previo al pedido del árbol, que se construye haciendo: salida, recorrido a la izquierda, recorrido a la derecha.

Como el recorrido posterior al pedido proviene de una BST, puede deducir el recorrido en el orden (recorrido izquierdo, salida, recorrido derecho) 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.

A partir de dos recorridos podemos construir el árbol original. Vamos a usar un ejemplo más simple para esto:

• Previo pedido: 2, 1, 4, 3
• En orden: 1, 2, 3, 4

El recorrido de orden anticipado 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 en el subárbol derecho. La estructura del subárbol izquierdo es trivial ya que contiene un solo elemento. El recorrido previo al pedido del subárbol derecho se deduce al tomar el orden de los elementos en este subárbol del recorrido previo al pedido original: 4, 3. De esto sabemos que la raíz del subárbol derecho es 4 y del recorrido en orden (3, 4) sabemos que 3 caen en el subárbol izquierdo. Nuestro árbol final se ve así:

  2
 / /
1   4
   /
  3

Con la estructura del árbol, podemos obtener el recorrido posterior al pedido al caminar por el árbol: recorrido a la izquierda, recorrido a la derecha, salida. Para este ejemplo, el recorrido posterior al pedido es 1, 3, 4, 2.

Para generalizar el algoritmo:

1. El primer elemento en el recorrido previo al pedido 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 derecho.
2. Encuentre la estructura de los subárboles izquierdo y derecho usando el paso 1 con un recorrido de pedido anticipado que consiste en los elementos que trabajamos en ese subárbol colocado en el orden en que aparecen en el recorrido de pedido anticipado original.
3. Recorra el árbol resultante en orden posterior para obtener el recorrido posterior al pedido asociado con el recorrido anterior al pedido dado.

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

Answer 7

Se le dan los resultados del recorrido pre-orden. luego coloque los valores en un árbol de búsqueda binario adecuado y simplemente siga el algoritmo de recorrido posterior al pedido para el BST obtenido.

Answer 8

Si se le ha dado un pedido anticipado y desea convertirlo en un pedido posterior. Entonces debes recordar que en una BST en orden, siempre da los números en orden ascendente. Por lo tanto, tienes Inorder y el Preorder para construir un árbol.

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

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

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

Answer 9

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

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

En un árbol de búsqueda binario, 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 derecho. Por lo tanto, si conoce el inicio de un volcado de pedidos anticipados de un árbol de búsqueda binario (es decir, el valor de su nodo raíz), puede descomponer fácilmente el volcado completo 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 orden posterior, se aplica la recursión y la ordenación de la salida. Esta tarea se deja en el lector.