Determine la equivalencia estructural de las BST con un recorrido estándar: algoritmo, búsqueda, estructura de datos, árbol, catalán

¿Es posible decidir el estructural?equivalencia de dos árboles de búsqueda binarios solo con los resultados de recorridos, pre orden, en orden y post orden. Supongamos que solo tengo las matrices de resultados de todos los recorridos. Sé que solo en orden transversal, no puedo ayudar. Pero, no pude visualizar otros resultados transversales. Entiendo que BFS ayuda. Quiero saber para los recorridos pre y post orden. Y si es posible, por favor publica cualquier enlace sobre esto.

Respuestas

La respuesta es : Puede recuperar un árbol de búsqueda binario de su recorrido previo al pedido..

No estoy seguro de cuál es su formación matemática, así que pregunte si necesita más explicación.

Para simplificar, asumo que el nodo está etiquetado por el entero 1,2 ... n donde n es el número de nodo. Luego, el recorrido de pre-orden del árbol t le da una permutación de [n] = {1,2,...,n} que tienen una propiedad particular: cada vez que tenga una letra b en su permutación, no puede encontrar dos letras consecutivas ca después de la b en la permutación tal que a<b<c. Se dice que tal permutación evitar el patrón b-ac (el - representa un número arbitrario de letras).

Por ejemplo, 4 2 1 3 evita b-ac mientras que 3 1 4 2 no lo hace porque 3 - 4 2.

Esto es en realidad una equivalencia: una permutación es la lectura previa al pedido de un árbol si es evitar b-ac.

Se sabe que hay tantos árboles de tamaño ncomo permutación evitando b-ac así que esto es una bijección. Su número se conoce como número catalán. Probablemente pueda encontrar esto como un ejercicio del libro "combinatoria enumerativa" de Stanley.

Aquí hay una explicación más algorítmica.:

RecTree: Recovering a tree from is Pre-order traversal:

input: list l
output: tree t

b <- l[0]
find an index i such that
- for 1<=j<=i then l[j] < b and
- for i<j<=n  then l[j] > b
if there isn"t exists such an index return Failure
else return Node(key=b, RecTree(l[1..i]), RecTree(l[i+1..n]))

Como consecuencia

Dos árboles de búsqueda binarios son iguales si y solo si tienen el mismo recorrido previo al pedido

¿Tiene sentido para ti?

Algunas referencias mas

• Número catalán en la Enciclopedia On-Line de Secuencias Enteras.
• Anders Claesson Generalized Pattern Avoidance, European Journal of Combinatorics 22 (2001) 961–971

En una BST puedes ir a la izquierda (L), a la derecha(R) o arriba (U). Un recorrido puede ser descrito por una cadena sobre {L, R, U}, por ejemplo. "LLURUURLURUU". Para BST con estructuras equivalentes, estas cadenas serán idénticas.