es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

¿Cómo comparar dos árboles generales independientemente del orden de los nodos hijos?

29 May, 2023 Programación

Tengo dos árboles generales. La identidad de cada árbol es su nodo raíz. La estructura de datos para representar el árbol es TreeNode.

struct TreeNode{
int data;
vector<treenode> subNodes; // lista de punteros a todos los nodos secundarios de un nodo particular
TreeNode parent; // puntero al nodo padre de este nodo
}

Cada árbol se identifica por su puntero a Nodo raíz.
Quiero comparar dos árboles de tal manera que, aunque el orden de los nodos secundarios de dos nodos correspondientes sea diferente, la función bool compareDeep(TreeNode *root1, TreeNode *root2) debe devolver true.

Para ilustrar, aquí hay algunos ejemplos:
1)
enter image description here

En este caso, bool compareDeep(root1, root2) debería devolver true, ya que el orden de los nodos secundarios difiere pero el contenido es el mismo.

Puedo comparar el caso de igualdad exacta, donde se puede hacer una traversía de orden de nivel de ambos árboles al mismo tiempo, y comparar los nodos nivel por nivel.

En realidad, estoy intentando resolver este problema con respecto a árboles XML, devueltos por el analizador XML, donde quiero comparar dos árboles DOM XML independientemente del orden de los elementos.</treenode*>

Tags:  , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Para comparar dos árboles generales, de modo que aunque el orden de los nodos secundarios de los nodos correspondientes sea diferente, se puede implementar la función bool compareDeep(TreeNode *root1, TreeNode *root2) siguiendo estos pasos:

    1. Verificar si ambos nodos raíz son NULL, en cuyo caso los árboles son iguales, y devolver true.

    2. Verificar si los datos de ambos nodos no son iguales, en cuyo caso los árboles no son iguales, y devolver false.

    3. Verificar si el número de nodos secundarios en ambos nodos no es igual, en cuyo caso los árboles no son iguales, y devolver false.

    4. Iterar sobre los nodos secundarios del primer nodo, y para cada nodo secundario, buscar recursivamente un nodo secundario correspondiente en el segundo nodo. Si se encuentra un nodo secundario correspondiente, llamar recursivamente a compareDeep con esos nodos secundarios.

    5. Si todos los nodos secundarios del primer nodo tienen nodos secundarios correspondientes en el segundo nodo, los árboles son iguales, y devolver true.

    La implementación de la función compareDeep para la estructura de datos de TreeNode en C++ podría ser algo como esto:

    bool compareDeep(TreeNode *root1, TreeNode *root2) {
    if (root1 == NULL && root2 == NULL) {
        return true;
    }
    if (root1 == NULL || root2 == NULL) {
        return false;
    }
    if (root1->data != root2->data || root1->subNodes.size() != root2->subNodes.size()) {
        return false;
    }
    for (int i = 0; i < root1->subNodes.size(); i++) {
        bool foundMatch = false;
        for (int j = 0; j < root2->subNodes.size(); j++) {
            if (compareDeep(root1->subNodes[i], root2->subNodes[j])) {
                foundMatch = true;
                break;
            }
        }
        if (!foundMatch) {
            return false;
        }
    }
    return true;
}

    Esta función se puede llamar con los nodos raíz de dos árboles para comprobar si son iguales, incluso si el orden de los nodos secundarios es diferente. Por ejemplo:

    bool treesEqual = compareDeep(root1, root2);

Comments are closed.