Solución:
Es un problema menor, pero adaptaría la solución anterior de la siguiente manera …
eq(t1, t2) =
t1.data=t2.data && eq(t1.left, t2.left) && eq(t1.right, t2.right)
La razón es que es probable que los desajustes sean comunes, y es mejor detectarlos (y dejar de comparar) temprano, antes de recurrir más. Por supuesto, estoy asumiendo un operador && de cortocircuito aquí.
También señalaré que esto pasa por alto algunos problemas con el manejo correcto de árboles estructuralmente diferentes y con el final de la recursividad. Básicamente, es necesario que haya algunas comprobaciones nulas para t1.left, etc. Si un árbol tiene un .left nulo pero el otro no, ha encontrado una diferencia estructural. Si ambos tienen nulo .left, no hay diferencia, pero ha llegado a una hoja, no repita más. Solo si ambos valores .left no son nulos, recurre para verificar el subárbol. Lo mismo se aplica, por supuesto, a .right.
Puede incluir comprobaciones para, por ejemplo, (t1.left == t2.left), pero esto solo tiene sentido si los subárboles se pueden compartir físicamente (los mismos nodos de estructura de datos) para los dos árboles. Esta verificación sería otra forma de evitar recurrir cuando sea innecesario: si t1.left y t2.left son el mismo nodo físico, ya sabe que todos esos subárboles son idénticos.
La implementación de CA podría ser …
bool tree_compare (const node* t1, const node* t2)
{
// Same node check - also handles both NULL case
if (t1 == t2) return true;
// Gone past leaf on one side check
if ((t1 == NULL) || (t2 == NULL)) return false;
// Do data checks and recursion of tree
return ((t1->data == t2->data) && tree_compare (t1->left, t2->left )
&& tree_compare (t1->right, t2->right));
}
EDITAR En respuesta a un comentario …
El tiempo de ejecución para una comparación completa de árboles usando esto se indica más simplemente como O (n) donde n es un poco el tamaño de un árbol. Si está dispuesto a aceptar un límite más complejo, puede obtener uno más pequeño como O (mínimo (n1, n2)) donde n1 y n2 son los tamaños de los árboles.
La explicación es básicamente que la llamada recursiva solo se realiza (como máximo) una vez para cada nodo en el árbol de la izquierda, y solo se realiza (como máximo) una vez para cada nodo en el árbol de la derecha. Como la función en sí (excluyendo las recursiones) solo especifica como máximo una cantidad constante de trabajo (no hay bucles), el trabajo que incluye todas las llamadas recursivas solo puede ser tanto como el tamaño del árbol más pequeño multiplicado por esa constante.
Podría analizar más para obtener un límite más complejo pero más pequeño utilizando la idea de la intersección de los árboles, pero la O grande solo da un límite superior, no necesariamente el límite superior más bajo posible. Probablemente no valga la pena hacer ese análisis a menos que esté tratando de construir un algoritmo / estructura de datos más grande con esto como un componente y, como resultado, sepa que alguna propiedad siempre se aplicará a esos árboles, lo que puede permitirle un límite más estricto para el algoritmo más grande.
Una forma de formar un límite más estrecho es considerar los conjuntos de rutas a los nodos en ambos árboles. Cada paso es una L (subárbol izquierdo) o una R (subárbol derecho). Entonces, la raíz se especifica con una ruta vacía. El hijo derecho del hijo izquierdo de la raíz es “LR”. Defina una función “rutas (T)” (matemáticamente, no es parte del programa) para representar el conjunto de rutas válidas en un árbol, una ruta para cada nodo.
Entonces podríamos tener …
paths(t1) = { "", "L", "LR", "R", "RL" }
paths(t2) = { "", "L", "LL", "R", "RR" }
Las mismas especificaciones de ruta se aplican a ambos árboles. Y cada recursión siempre sigue el mismo enlace izquierdo / derecho para ambos árboles. Entonces, la recursividad visita los caminos en la itersección de estos conjuntos, y el límite más estrecho que podemos especificar usando esto es la cardinalidad de esa intersección (aún con el límite constante en el trabajo por llamada recursiva).
Para las estructuras de árbol anteriores, hacemos recursiones para las siguientes rutas …
paths(t1) intersection paths(t2) = { "", "L", "R" }
Entonces, nuestro trabajo en este caso está limitado a un máximo de tres veces el costo máximo del trabajo no recursivo en la función tree_compare.
Normalmente se trata de una cantidad de detalle innecesaria, pero es evidente que la intersección de los conjuntos de rutas es como mucho tan grande como el número de nodos en el árbol original más pequeño. Y si la n en O (n) se refiere al número de nodos en un árbol original o a la suma de los nodos en ambos, esto claramente no es menor que el mínimo o nuestra intersección. Por lo tanto, O (n) no es un límite tan estrecho, pero sigue siendo un límite superior válido, incluso si somos un poco vagos de qué tamaño estamos hablando.
Desbordamiento de pila de módulo, algo así como
eq(t1, t2) =
eq(t1.left, t2.left) && t1.data=t2.data && eq(t1.right, t2.right)
(Esto se generaliza a un predicado de igualdad para todos los tipos de datos algebraicos estructurados en árbol; para cualquier pieza de datos estructurados, verifique si cada una de sus subpartes es igual a cada una de las subpartes del otro).
También podemos hacer cualquiera de los dos recorridos (pre-orden, post-orden o en orden) y luego comparar los resultados de ambos árboles. Si son iguales, podemos estar seguros de su equivalencia.