Convierta la lista de preorden de un árbol binario en postorder y viceversa

Question

¿Cómo puedo encontrar el listado de preorden de un árbol si solo se da el listado de postorder y viceversa? Además, en el árbol, cada nodo no hoja tiene dos hijos (es decir, cada nodo tiene dos o cero hijos).

EDITAR: Otra suposición dada es que la etiqueta de cada nodo es única y tiene un campo que la identificará como un nodo interno o una hoja. Creo que eso debería eliminar la ambigüedad de un solo preordenador o postorder capaz de identificar de forma única un árbol.

Answer 1

Sin suponer que los nodos en el árbol tienen un campo que se identifica como interno u hoja, no puede encontrar una respuesta única para su pregunta. Esa suposición o lista de pedidos debe estar disponible para encontrar un árbol único. En este caso, para encontrar una respuesta posible, puede construir un árbol del formulario que se muestra a continuación para que coincida con cualquier listado de postorder dado: (suponga que el listado de postorder es: 1 2 3 4 5 6 7 8 9)

9[7[5[3[1,2],4],6],8]

Ahora puede hacer una lista de pedidos anticipados utilizando este árbol.

Suponiendo que los nodos en el árbol tengan un campo que se identifique como interno u hoja, podemos hacer un árbol único a partir de una lista de postores para este tipo de árboles con este algoritmo:

1. Barra desde el principio de la lista de postores y encuentre el primer nodo interno. Este nodo tendrá exactamente dos hijos hoja que preceden a este nodo en la lista de postorder.
2. En su estructura de árbol, agregue ese nodo interno y haga dos nodos anteriores en la lista de sus hijos.
3. Elimine a esos dos hijos de la lista y convierta ese nodo interno en una hoja.
4. Vaya al paso 1 y repita hasta que la lista quede vacía.

Answer 2

Considere la estructura recursiva de un recorrido previo al pedido:

T(r) = [r, T(r->left), T(r->right)]
where T(r) is the preorder traversal of tree rooted at node r

Entonces sabemos que la raíz de un árbol descrito por T (r) es siempre el primer nodo en el recorrido.

Sabiendo esto, y sabiendo que una raíz siempre es más alta en un árbol que sus subárboles, piense en cómo usaría esta información para reconstruir el árbol. Piensa recursivamente.

Advertencia: esto solo se puede hacer si se trata de un árbol de búsqueda binario , que restringe nodos tales como left-child < root < right-child. En general, los árboles no se pueden reconstruir a partir de un solo recorrido. Consulte este excelente recurso para obtener una explicación más detallada .

La ambigüedad todavía existe independientemente de la regla sobre 0 o 2 hijos:

    4
   / \
  2   5
 / \ / \
 1 3 6 7

    4
   / \
  2   7
 / \
1   3
   / \
  5   6

Ambos tienen el recorrido previo al pedido [4 2 1 3 5 6 7]

Answer 3

Por ejemplo: debe convertir el formulario de postorder en formulario de preorden. Esto se puede hacer de la siguiente manera. orden postal: DEBFCA preorden: ABDECF vemos que A es la raíz. y desde preorden podemos determinar que el nodo B se deja a A. por lo tanto, creamos dos subclases que son (BED) (CF). Ahora cuando atravesamos B lo tomamos como una raíz y vemos que después de B, D ESTÁ PRESENTE , significa que D se deja a B y E a la derecha a B. ahora atravesamos C. tómalo como una raíz. Entonces F está presente después de C, por lo que se toma como izquierda.