Le moyen le plus efficace de tester les deux arbres binaires pour l'égalité

Bien pour une chose que vous êtes toujours vérifier les branches, même si vous l'apercevez que les racines sont inégales. Votre code sera plus simple (OMI) et plus efficace si vous venez de rentrer false dès que vous avez repéré une inégalité.

Une autre option pour simplifier les choses, c'est pour permettre à votre equals méthode d'accepter null valeurs et de comparer les deux valeurs null comme étant égales par ailleurs. De cette façon, vous pouvez éviter tous ces nullité des contrôles dans les différentes branches. Ce ne sera pas le rendre plus efficace, mais ça va être plus simple:

public boolean equals(Node<T> root1, Node<T> root2) {
    //Shortcut for reference equality; also handles equals(null, null)
    if (root1 == root2) {
        return true;
    }
    if (root1 == null || root2 == null) {
        return false;
    }
    return root1.getData().equals(root2.getData()) &&
           equals(root1.getLeft(), root2.getLeft()) &&
           equals(root1.getRight(), root2.getRight());
} 

Il faut noter que ceci ne fonctionnera pas si root1.getData() retourne null. (Qui peut ou peut ne pas être possible avec la façon dont vous êtes l'ajout de nœuds.)

EDIT: Comme discuté dans les commentaires, vous pouvez utiliser des codes de hachage pour faire un très rapide "début" - mais il serait ajouter de la complexité.

Soit vous avez besoin pour faire vos arbres immuable (ce qui est une autre discussion) ou vous avez besoin chaque nœud de connaître ses parents, de sorte que lorsque le nœud est modifiée (par exemple, par l'ajout d'une feuille ou de la modification de la valeur), il doit mettre à jour son code de hachage et de demander à ses parents de mettre à jour trop.

Tout d'abord, je suis en train de faire quelques hypothèses générales. Ce sont des hypothèses qui sont valables pour la plupart des arbres, des classes de collection, mais c'est toujours la peine de vérifier:

1. Vous pensez à deux arbres à égalité si et seulement si elles sont égales à la fois en termes de structure de l'arbre et en termes de valeurs de données à chaque nœud (tel que défini par les données.est égal à(...))
2. null valeurs de données sont autorisés à les nœuds de l'arborescence (ce pourrait être parce que vous permettez à null explicitement ou parce que votre structure de données stocke uniquement les valeurs non null dans les nœuds feuilles)
3. Il n'y a pas toute particulière de faits inhabituels que vous savez à propos de la distribution des valeurs de données que vous pouvez prendre avantage de (par exemple, si l'on savait que la seule possible, les données des vallées ont été nulles ou la Chaîne "toto", alors vous n'avez pas besoin de comparer deux non-nulle de la Chaîne de valeurs)
4. Les arbres seront généralement de taille moyenne et assez bien équilibré. En particulier, ce qui assure que les arbres ne seront jamais aussi profond que vous courez le risque de StackOverflowExceptions causée par la profondeur de récursivité.

En supposant que ces hypothèses sont correctes, puis l'approche que je suggère, c'est d':

• N'racine de la référence à l'égalité vérifier d'abord. ce qui élimine rapidement le cas où l'une des deux valeurs null ou le même arbre qui est passée pour la comparaison avec lui-même. Les deux sont des cas très fréquents, et la référence à l'égalité case est extrêmement bon marché.
• Vérifier les valeurs null suivant. Non-nul n'est évidemment pas égal à null, ce qui vous permet de renflouer début plus il établit une valeur non nulle garantie pour plus tard code! Très intelligent de compilateur pourrait théoriquement utiliser cette garantie pour optimiser loin de pointeur null vérifie par la suite (pas sûr si la JVM n'est actuellement ce)
• Vérifier les données de référence de l'égalité et les valeurs null suivant. Cela évite descendant tout le chemin vers le bas les branches de l'arbre qui vous ferait, même dans le cas de l'inégalité de données si vous êtes allé vers le bas les branches de l'arbre en premier.
• Vérifier les données.equals() à côté. Encore une fois, vous voulez vérifier les données de l'égalité devant les branches des arbres. Vous faites cela après avoir vérifié les valeurs null puisque les données.equals() est potentiellement plus coûteux et vous voulez vous assurer que vous n'obtenez pas une exception NullPointerException
• Vérifier l'égalité des branches de manière récursive comme la dernière étape. Il n'a pas d'importance si vous ne la gauche ou la droite première sauf il y a une plus grande probabilité d'un côté étant inégale, dans ce cas, vous devriez vérifier ce côté en premier. Ce pourrait être le cas si par exemple, la plupart des modifications ont été ajoutés à la branche droite de l'arbre....
• Faire la comparaison d'une méthode statique. C'est parce que vous voulez l'utiliser de façon récursive dans une manière qui permettra d'accepter les valeurs null en tant que l'un des deux paramètres (par conséquent, il n'est pas approprié pour une méthode d'instance comme this ne peut pas être null). En outre, la JVM est très bon à l'optimisation des méthodes statiques.

Ma mise en œuvre serait donc quelque chose comme:

public static boolean treeEquals(Node a, Node b) {
    //check for reference equality and nulls
    if (a == b) return true; //note this picks up case of two nulls
    if (a == null) return false;
    if (b == null) return false;

    //check for data inequality
    if (a.data != b.data) {
        if ((a.data == null) || (b.data == null)) return false;
        if (!(a.data.equals(b.data))) return false;
    }

    //recursively check branches
    if (!treeEquals(a.left, b.left)) return false;
    if (!treeEquals(a.right, b.right)) return false;

    //we've eliminated all possibilities for non-equality, so trees must be equal
    return true;
}

Le code donné ci-dessus serait de retour vrai pour les deux inégale des arbres avec la même racine valeurs. Je ne pense pas que ce est ce que vous voulez. Ne devrait-elle pas être:

if (!a==b) return false;

De cette façon, la méthode devait effectuer le reste de la vérifie.

(Ne pourrez pas vous connecter à partir d'ici pour une raison.)