¿Cuál sería el algoritmo para encontrar subárboles duplicados en un árbol binario?

Supongo que al duplicar subárboles en un árbol binario solo se tiene en cuenta la estructura (ignorando pesos, colores, etc.) y también diferenciando los subárboles simétricos (aunque el método que presentaré es fácilmente adaptable para tales casos.

En primer lugar, necesita algún tipo de estructura de datos de valor clave (es decir, tabla hash o conjunto). Luego comienza a procesar el árbol de abajo hacia arriba y mantiene una representación de la corriente que luego agrega a la estructura de datos que mencioné antes de usar la representación actual del subárbol como la clave. Solo queda un detalle: ¿qué representación usar?

Una posible sugerencia:

• Si un nodo es una hoja, represente por [math] F [/ math].
• Si un nodo solo tiene un hijo izquierdo, lo representa por [math] L_i [/ ​​math] donde [math] i [/ math] es la altura del subárbol actual, precedido por la representación de su subárbol izquierdo.
• Si un nodo solo tiene un hijo derecho, se representa con [math] R_i [/ ​​math] donde [math] i [/ math] es la altura del subárbol actual, con el sufijo de la representación de su subárbol izquierdo.
• Si un nodo tiene elementos secundarios izquierdo y derecho, representalo por [math] T_i [/ ​​math] donde [math] i [/ math] es la altura del subárbol actual, precedido por la representación de su subárbol izquierdo y sufijado por la representación de su subárbol izquierdo.

También puede probar algo más sofisticado, como usar G-tries, pero creo que el enfoque anterior será muy adecuado para su problema. Es posible que haya algunos errores tipográficos / errores en mi explicación, ya que no lo he “probado”, fue solo una idea que se me ocurrió.

Crear una matriz 2d [math] flag [] [] [/ math], donde [math] flag [i] [j] [/ math] significa si sub-tree [math] i [/ math] y sub-tree [ matemáticas] j [/ matemáticas] es lo mismo. (subárbol [matemática] i [/ matemática] se refiere al subárbol cuya raíz es nodo [matemática] i [/ matemática])

Si [math] i [/ math], [math] j [/ math] son ​​hojas, obviamente [math] flag [i] [j] = True [/ math].

Si [math] i [/ math] es una hoja y [math] j [/ math] no lo es, obviamente [math] flag [i] [j] = False [/ math].

Obviamente, [math] flag [i] [j] = flag [j] [i] [/ math].

De lo contrario, si [matemática] i [/ matemática], [matemática] j [/ matemática] no son hojas, deje que los hijos izquierdo y derecho del nodo [matemática] i [/ matemática] y [matemática] j [/ matemática] ser respectivamente [matemáticas] a [/ matemáticas], [matemáticas] b [/ matemáticas] y [matemáticas] m [/ matemáticas], [matemáticas] n [/ matemáticas]. En este caso, [math] flag [i] [j] = flag [a] [m] && flag [b] [n] [/ math]. (extraño sistema de sintaxis de quora … ¿cómo puedo deshacerme de la caja aquí?)

Entonces, al iterar y calcular el arreglo por este método, tenemos un algoritmo [matemático] O (n ^ 2) [/ matemático]. Aunque creo que debería haber una [matemática] O (nlogn) [/ matemática] en alguna parte.

Por cierto, puede ampliar fácilmente este algoritmo para tener en cuenta información adicional sobre los nodos (color, peso, etc.).

Prueba esto.

Ir desde los nodos finales. Cree una entrada de datos que sean los datos concatenados de ese en el nodo hoja (llame a ese nivel N) y su padre (nivel N-1). Clasifícalos. Luego, para cualquier coincidencia, reemplace los datos en el nivel N-1 con los datos concatenados. Repetir. Cuando no se produzcan más coincidencias, compruebe los nodos finales para ver si hay varios niveles de datos concatenados.