¿Demuestra que los árboles binarios con los mismos cruces de orden y preorden son idénticos?

Question

¿Alguien sabe cómo probar que si dos árboles binarios tienen los mismos traslados inorder y preorden, entonces son idénticos? (Tal vez al mostrar que no puede tener dos árboles binarios diferentes con cruces preordenados e inorden idénticos)

¿Alternativamente, muestre un caso que lo desaprobaría, o mostrar por qué no se puede hacer?

(Voy a admitir, esto es puramente académico, pero no es tarea ni nada. Mi instinto me dice que es verdad, pero no creo que lo que he hecho ninguna prueba en los gráficos.)

Answer 1

El básico La idea es cómo reconstruir un árbol binario por el inorder dado y los cruces preordenados.

Es posible reconstruir solo un árbol binario desde el inorder y atravesar preordenar.

Ver:

• Nonrecursive algorithms for reconstructing a binary tree from its traversals (papel)
• reconstructing a tree from its preorder and postorder lists (SO pregunta)