algorithm - recorrido - reconstruir un árbol desde sus listas de preorden y postorder
recorrido de arboles binarios en c++ (7)
Como ya se ha señalado por otros, un árbol binario no se puede reconstruir utilizando solo el recorrido previo y posterior a la orden. Un nodo hijo único tiene recorridos ambiguos que no pueden identificar si es un hijo izquierdo o derecho, por ejemplo, considere seguir recorridos preordenados y postorder: preordenar: a, b postorder b, a
Puede producir los dos árboles siguientes
aa / / bb Simplemente no es posible saber si b es el hijo izquierdo o derecho de un a, sin ninguna información adicional como inorder transversal.
Considere la situación en la que tiene dos listas de nodos de las cuales todo lo que sabe es que una es una representación de un recorrido de preorden de un árbol y la otra una representación de un recorrido de postorder del mismo árbol.
Creo que es posible reconstruir el árbol exactamente a partir de estas dos listas, y creo que tengo un algoritmo para hacerlo, pero no lo he probado. Como esto será parte de un proyecto de máster, necesito estar absolutamente seguro de que es posible y correcto (probado matemáticamente). Sin embargo, no será el objetivo del proyecto, por lo que me pregunto si existe una fuente (es decir, papel o libro) que pueda citar para la prueba. (¿Tal vez en TAOCP? ¿Alguien conoce la sección posiblemente?)
En resumen, necesito un algoritmo comprobado en un recurso citable que reconstruya un árbol a partir de sus recorridos pre y post orden.
Nota: El árbol en cuestión probablemente no será binario, ni equilibrado, ni nada que lo haga demasiado fácil.
Nota 2: Utilizar solo la lista de pedidos anticipados o de postorden sería aún mejor, pero no creo que sea posible.
Nota 3: Un nodo puede tener cualquier cantidad de hijos.
Nota4: Solo me importa el orden de los hermanos. Izquierda o derecha no importa cuando solo hay un niño.
Considere un árbol arbitrario T como cuádruple (A, B, C , D ), donde A es el nodo raíz, B es el nodo raíz del primer hijo, C es un vector de cualquier hijo no vacío de B y D es un vector de hermanos no vacíos de B. Los elementos de C y D son en sí mismos árboles.
Cualquiera de A, B, C y D puede estar vacío. Si B está vacío, también debe ser C y D ; si A, entonces todo.
Como los nodos son únicos, los conjuntos de nodos contenidos en cualquier lugar dentro de C y D son disjuntos, y ninguno contiene A o B.
Las funciones pre () y post () generan secuencias ordenadas de la forma:
pre (T) = [A, B, pre ( C ) , pre ( D ) ]
publicación (T) = [ publicación ( C ) , B, publicación ( D ) , A]
donde la función aplicada a un vector se define como la concatenación de las secuencias resultantes de aplicar la función a cada elemento por turno.
Ahora considera los casos:
- si A está vacío, el resultado de ambas funciones es la secuencia vacía []
- si B está vacío, el resultado de ambas funciones es solo [A]
- si C y D están vacíos, pre (T) = [A, B] y publicación (T) = [B, A]
- si solo C está vacío, pre (T) = [A, B, D '' ] y poste (T) = [B, D'' '' , A] (donde los números primos indican alguna permutación de los nodos contenidos en D )
- si solo D está vacío, pre (T) = [A, B, C '' ] y publicación (T) = [ C'' '' , B, A]
- si ninguno está vacío, pre (T) = [A, B, C '' , D'' ] y publicación (T) = [ C '''' , B, D '''' , A]
En todos los casos podemos dividir sin ambigüedad los miembros de las dos secuencias de salida en las subsecuencias apropiadas, usando A y B (si están presentes) como delimitadores.
La pregunta es, ¿podemos también dividir las secuencias vectoriales? Si podemos, entonces cada uno puede ser procesado recursivamente y hemos terminado.
Como el resultado de pre () siempre será una cadena de secuencias que comienza con los nodos A, y el resultado de post () siempre será una cadena de secuencias que termina con los nodos A, podemos dividirlos, siempre que los nodos A nunca están vacíos
Aquí es donde el proceso cae en el caso de árboles binarios (o de hecho cualquier) con niños fijos que pueden estar vacíos de forma independiente. En nuestro caso, sin embargo, hemos definido C y D para contener únicamente nodos no vacíos, por lo que se garantiza que la reconstrucción funcionará.
Um, eso creo, de todos modos. Obviamente, esto es solo un argumento, ¡no una prueba formal!
Cree un árbol binario con esta restricción que tenga al menos un nodo que este nodo tenga solo un hijo (derecha o izquierda, no hay diferencia).
Ahora, escribe sus listas Preorder y Postorder. luego intente reconstruir el árbol a partir de estas listas. y te das cuenta de que en ese nodo no puedes decidir si su hijo está a la derecha o a la izquierda.
Los cruces de preorden y postorder son suficientes para reconstruir el árbol, suponiendo que los nodos tienen un nombre único. La clave para crear los algoritmos para hacerlo es comprender que
X es un ancestro de Y si f X precede a Y en el preorden y está después de Y en el postorder.
Dado esto, siempre podemos encontrar todos los descendientes de cualquier nodo. Los descendientes de X siempre siguen inmediatamente a X en el preorden y preceden a X en el postorder. Entonces, una vez que sabemos que estamos interesados en producir el subárbol enraizado en X, podemos extraer el recorrido de preorden y postorder para el subárbol enraizado en X. Esto conduce naturalmente a un algoritmo recursivo, una vez que nos damos cuenta de que el nodo inmediatamente después de X debe ser su hijo más a la izquierda, si es un descendiente en absoluto.
También hay una implementación basada en pila, que itera a través de los nodos de preorden y mantiene en la pila los nodos que son candidatos para ser el padre directo del siguiente nodo de preorden. Para cada nodo de preorden, saque repetidamente todos los nodos de la pila que no sean los padres del siguiente nodo de preorden. Haga que ese nodo sea un elemento secundario del nodo superior en la pila y empuje al niño hacia la pila.
No es posible construir un árbol binario general a partir de recorridos preordenados y postorden (Ver esto). Pero si sabes que el Árbol binario está lleno, podemos construir el árbol sin ambigüedad. Permítanos entender esto con la ayuda del siguiente ejemplo.
Consideremos las dos matrices dadas como pre [] = {1, 2, 4, 8, 9, 5, 3, 6, 7} y publicar [] = {8, 9, 4, 5, 2, 6, 7 , 3, 1}; En pre [], el elemento más a la izquierda es la raíz del árbol. Como el árbol está lleno y el tamaño de la matriz es mayor que 1. El valor al lado de 1 en pre [], se debe dejar como hijo de la raíz. Entonces sabemos que 1 es root y 2 es left child. ¿Cómo encontrar todos los nodos en el subárbol izquierdo? Sabemos que 2 es la raíz de todos los nodos en el subárbol izquierdo. Todos los nodos antes de 2 en la publicación [] deben estar en el subárbol izquierdo. Ahora sabemos que 1 es raíz, los elementos {8, 9, 4, 5, 2} están en el subárbol izquierdo, y los elementos {6, 7, 3} están en el subárbol derecho.
1
/ /
/ /
{8, 9, 4, 5, 2} {6, 7, 3}
Recursivamente seguimos el enfoque anterior y obtenemos el siguiente árbol.
1
/ /
2 3
/ / / /
4 5 6 7 / /
8 9
No puede usar solo una lista, porque no tendrá sentido de la profundidad del árbol. Por lo tanto, definitivamente necesita dos o más listas.
Aquí está mi intento de una solución:
Use su recorrido de preorden como medio para conocer el orden de los datos. Esto tiene sentido porque usted sabe que el primer nodo es la parte superior, y usted sabe que los datos más a la izquierda del recorrido pertenecen a la izquierda del árbol, etc.
El recorrido de su pedido posterior puede determinar la profundidad del árbol. Por ejemplo, digamos que tengo una estructura como esta:
1
2 5 6
3 4 7
Where 2 is the parent of 3 and 4, and 5 is the parent of 7.
Preorder: 1 2 3 4 5 7 6
Postorder: 3 4 2 7 5 6 1
Sabemos que comenzamos con 1, porque es el primer nodo en el recorrido de preorden. Luego miramos el siguiente número, 2. En el orden posterior, porque el número 2 viene ANTES del nodo 1, sabemos que 2 tiene que ser un hijo de 1. Luego vemos 3. 3 viene antes de 2, y por lo tanto 3 es un niño de 2. 4 es antes de 2 pero después de 3, entonces sabemos que 4 es un niño de 2 pero NO un niño de 3. Etc.
Ahora, esto puede no funcionar si los nodos no son únicos, pero al menos es el comienzo de una solución.
Editar: El orden de los niños se conserva con esta solución, simplemente debido a conocer el orden de los nodos a través del recorrido de preorden, y luego conocer la estructura a través del recorrido del postorder.
Edit2: La prueba puede estar aquí: http://ieeexplore.ieee.org/Xplore/login.jsp?url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel2%2F215%2F626%2F00017225.pdf%3Farnumber%3D17225&authDecision=-203
Creo que debes comprar el documento, sin embargo ...
Aquí hay una prueba escrita que se presenta como una solución:
http://www14.informatik.tu-muenchen.de/lehre/2007WS/fa-cse/tutorials/tutorial09-solutions.pdf
Preorder y postorder no definen un árbol de forma exclusiva.
En general, un cruce de árbol único no define de forma única la estructura del árbol. Por ejemplo, como hemos visto, para ambos árboles siguientes, un cruce inorden produce [1,2,3,4,5,6].
4 3
/ / / /
2 5 2 5
/ / / / / /
1 3 6 1 4 6
La misma ambigüedad está presente para los cruces de preorden y postorder. El recorrido de preorden para el primer árbol de arriba es [4,2,1,3,5,6]. Aquí hay un árbol diferente con el mismo recorrido de preorden.
4
/ /
2 1
/ /
3 6
/
5
Del mismo modo, podemos construir fácilmente otro árbol cuyo recorrido del postorder [1,3,2,6,5,4] coincide con el del primer árbol de arriba.