Si estamos hablando de árboles de expresión válidos, el recorrido previo al pedido define un árbol único.
Voy a arriesgarme aquí porque mis habilidades de prueba de CS son extremadamente oxidadas.
Creo que el hecho de que sea un árbol de expresión es la clave de la prueba. Suponiendo expresiones binarias simples, el árbol de expresiones es un árbol binario con dos tipos de nodos, operadores y valores. Los operadores deben tener dos hijos; los nodos de valor no deben tener hijos.
- ¿Qué tan bien funcionan los algoritmos predictivos que analizan los guiones de películas?
- ¿Cuál es el uso práctico de los árboles de búsqueda binarios?
- ¿Cómo implemento un árbol N-ary en C?
- ¿Cuál es el algoritmo más complicado por el que has pasado?
- ¿Cómo entender el algoritmo SHA-1? ¿Cuáles son los mejores ejemplos para ello?
Para reformular la pregunta, dado un recorrido de preorden de un árbol de expresión válido, t1, ¿hay otro árbol de expresión válido, t2, que tenga el mismo recorrido de preorden? Creo que lo siguiente es una prueba válida de que no puede haber otro t2. La idea básica es que cualquier intento de crear una segunda estructura de árbol diferente en un recorrido de preorden existente dará como resultado un árbol de expresión no válido.
Para comenzar, etiquetemos los nodos de operador O y los nodos de valor V. Luego, cualquier nodo, y en particular, todo el árbol, tiene una de las siguientes formas para su recorrido previo al pedido:
1 – V // un valor simple
do
2 – OVV // una operación y sus dos operandos de valor
CLR
3 – OO x… xn VVV // El hijo izquierdo es una operación, el hijo derecho es un valor
CLLLLLR
4 – OVO y … ym VV // El elemento secundario izquierdo es un valor, el elemento secundario derecho es una operación
CLRRRRR
5 – OO x … xn VVO y … ym VV // Ambos hijos son operaciones.
CLLLLLRRRRR
Debajo de cada tipo de nodo, hay una letra para indicar si el nodo es el Centro (C) o en el Hijo Izquierdo (L) o el Hijo Derecho (R). La notación C, L, R muestra la estructura de árbol. Tenga en cuenta que un subárbol es un solo nodo V o comienza con un nodo O en el recorrido de preorden. Tenga en cuenta también que cualquier subárbol que comienza con un nodo O termina con al menos dos nodos V. Si hay una segunda estructura de árbol, tendrá una división L, R diferente en algún nivel del árbol. Entonces, la cuestión de la existencia de un segundo árbol se transforma en lo siguiente: ¿Es posible cambiar el límite L, R, es decir, extender el niño derecho hacia la izquierda o el niño izquierdo hacia la derecha, y aún expresar un árbol de expresión válido. Recuerde que los nodos O deben tener dos hijos y los nodos V no tienen hijos. Argumentaré que no es posible cambiar la división L, R sin crear un árbol de expresión no válido.
Para los casos 1 y 2, es obvio que solo es posible un árbol.
Para el caso 3, intente extender el niño derecho hacia la izquierda. Al atraer los nodos uno por uno, obtenemos la secuencia VV, que no es válida. Continuando, obtenemos la secuencia VVV que tampoco es válida. Seguiremos tirando de los nodos V hasta que veamos los nodos O. Dependiendo de cuántos nodos V agreguemos, es posible que tengamos que extraer varios nodos O. Como el árbol original era válido, eventualmente obtendremos una secuencia válida de nuevos nodos. Tenga en cuenta que el primer nodo en esta secuencia válida debe ser un nodo O. Ahora hay dos posibilidades. Primero, es posible que hayamos retrocedido hasta el nodo O que es el hijo izquierdo inmediato del nodo raíz, C,. Si ese es el caso, el nodo raíz ya no tiene un hijo izquierdo y, por lo tanto, el árbol no es válido. La forma simple de esto es si no hay nodos intermedios, es decir, n == 0. Entonces xn es el nodo O que es el hijo izquierdo inmediato de la raíz. La segunda situación es que hemos extraído todo el subárbol derecho de algún nodo O intermedio. Si ese es el caso, no podemos detenernos aquí ya que el nodo O intermedio ya no tendría un subárbol correcto. Necesitamos continuar moviéndonos hacia la izquierda, arrastrando más nodos al (nuevo) subárbol derecho que estamos tratando de crear. Debemos extraer el subárbol izquierdo del nodo O intermedio y el propio nodo O intermedio. Ahora volvemos a nuestras dos situaciones. O hemos realizado una copia de seguridad en el elemento secundario izquierdo inmediato de la raíz, lo que nuevamente crea un árbol no válido, o hemos extraído todo el subárbol derecho de algún otro nodo O intermedio y necesitamos repetir el proceso. Esta eliminación sucesiva de los subárboles correctos nos obliga a continuar hasta que lleguemos a la raíz, lo que da como resultado un árbol no válido.
Para el caso 4, tenga en cuenta que no podemos extender el hijo izquierdo hacia la derecha ya que es un nodo Value y los nodos Value no pueden tener hijos. En este caso, no podemos extender porque el nodo extendido sería inválido.
El caso 5 es el caso más general. Según el razonamiento del caso 3, vemos que no podemos extender el árbol derecho hacia la izquierda sin crear un árbol no válido.
Ahora intentemos extender el niño izquierdo hacia la derecha. No podemos simplemente tomar el siguiente nodo O ya que no es un subárbol válido. No tendría hijos. Debemos tomar el nodo O y sus dos hijos. Veamos las posibilidades para los subárboles izquierdo y derecho.
L R
– –
Caso 1 V V
Caso 2 O V
Caso 3 V O
Caso 4 O O
En el caso 1, no hay nodos intermedios. Extender el árbol izquierdo tira de los dos últimos nodos V y elimina completamente el hijo derecho del nodo C. Esta es una expresión no válida, por lo que no es posible extender el nodo izquierdo en esta situación.
En el caso 2, sacamos el nodo O pero estamos de vuelta donde comenzamos. No podemos extraer solo el nodo O, por lo que debemos continuar y volver a los casos que acabamos de enumerar. Si llegamos al caso 1, eliminamos por completo el elemento secundario derecho del nodo y creamos un árbol no válido, por lo que nuevamente, no es posible extender el nodo izquierdo en esta situación. Si volvemos al caso 2, volveremos a repetir. El caso 3 se cubrirá a continuación. El caso 4 también se cubrirá más adelante. Podemos ver que si seguimos encontrando el caso 2, eventualmente alcanzaremos un nodo O de nivel más bajo, es decir, el caso 1. Como hemos visto, cuando tocamos el caso 1, no podemos continuar ya que crea un árbol de expresión no válido.
En el caso 3, podemos extraer el primer nodo V pero luego nos encontramos con el nodo O del niño derecho. Cuando esto sucede, estamos de vuelta donde comenzamos. Encontraremos el caso 1 que crea un árbol no válido o continuaremos recurriendo a través del caso 2 y el caso 3 hasta que encontremos el caso 1 y creemos un árbol no válido.
El caso 4 falla por la misma razón que el caso 2.
El resultado de todo esto es que no podemos extender el nodo izquierdo hacia la derecha sin crear un árbol de expresión no válido. Intentar extender hacia la derecha nos lleva al caso en el que creamos un árbol de expresión no válido.
Volviendo a la pregunta original, vemos que para un recorrido de preorden dado, no podemos crear un segundo árbol válido que tenga el mismo recorrido de preorden. No hay forma de cambiar la división izquierda-derecha en ningún nivel del árbol sin crear un árbol de expresión no válido.
Este es un argumento bastante abstracto, por lo que podría ser totalmente delirante. Si tienes un contraejemplo, me encantaría verlo.
