最有效的方法来测试两个二叉树是否相等 [英] The most efficient way to test two binary trees for equality

问题描述

您如何在Java中实现二进制树节点类和二叉树类，以支持最有效（从运行时间上来看）等于检查方法（也必须实现）：

How would you implement in Java the binary tree node class and the binary tree class to support the most efficient (from run-time perspective) equal check method (also has to be implemented):

    boolean equal(Node<T> root1, Node<T> root2) {}

或

    boolean equal(Tree t1, Tree t2) {}

首先，我创建了Node类，如下所示：

First, I created the Node class as follows:

    public class Node<T> {
        private Node<T> left;
        private Node<T> right;
        private T data;

        // standard getters and setters
    }

，然后equals方法是采用2根节点作为参数和运行标准递归比较：

and then the equals method that takes 2 root nodes as an arguments and runs the standard recursive comparison:

    public boolean equals(Node<T> root1, Node<T> root2) {
        boolean rootEqual = false;
        boolean lEqual = false;
        boolean rEqual = false;    

        if (root1 != null && root2 != null) {
            rootEqual = root1.getData().equals(root2.getData());

            if (root1.getLeft()!=null && root2.getLeft() != null) {
                // compare the left
                lEqual = equals(root1.getLeft(), root2.getLeft());
            }
            else if (root1.getLeft() == null && root2.getLeft() == null) {
                lEqual = true;
            }
            if (root1.getRight() != null && root2.getRight() != null) {
                // compare the right
                rEqual = equals(root1.getRight(), root2.getRight());
            }
            else if (root1.getRight() == null && root2.getRight() == null) {
                rEqual = true;
            }

            return (rootEqual && lEqual && rEqual);
        }
        return false;
    } 

我的第二次​​尝试，以实现使用数组和索引遍历树。从2阵列读取数据块，并用另一逻辑和屏蔽一 - 那么可以使用位操作（AND）对两个数组进行比较。我没有得到我的code的工作，所以我不张贴在这里（我AP preciate您实现第二个想法，以及你的改进）。

My second attempt was to implement the trees using arrays and indexes for traversing. Then the comparison could be done using the bitwise operations (AND) on two arrays - read chunk from 2 arrays and mask one by another using logical AND. I failed to get my code working so I do not post it here (I'd appreciate your implementation of the second idea as well as your improvements).

任何思考如何做到平等测试二叉树最有效？

Any thoughts how to do equality test for binary trees most efficiently?

修改

问题假定结构相等。 （不是语义相等）

The question assumes structural equality. (Not the semantic equality)

不过，code，测试语义平等例如我们应该考虑的两棵树相等，如果它们的内容是相同的，即使它们的结构是不是？将只是遍历有序的树，它应该是简单的。

However, code that tests the semantic equality e.g. "Should we consider the two trees to be equal if their contents are identical, even if their structure is not?" Would be just iterating over the tree in-order and it should be straightforward.

推荐答案

好了一件事你的总是的检查分支，即使你发现的根源是不平等的。您的code会更简单（IMO）和更有效的，如果你只是返回假只要你发现了一个不平等。

Well for one thing you're always checking the branches, even if you spot that the roots are unequal. Your code would be simpler (IMO) and more efficient if you just returned false as soon as you spotted an inequality.

另一种选择，以简化的东西是让你的等于办法接受空值和比较两个空值作为等于。这样就可以避免在不同的分支所有无效的检查。这不会使之更有效率，但它会更简单：

Another option to simplify things is to allow your equals method to accept null values and compare two nulls as being equal. That way you can avoid all those nullity checks in the different branches. This won't make it more efficient, but it'll be simpler:

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());
} 

请注意，目前，这会出现失败root1.getData（）返回空。 （这可能或可能无法与要添加的节点的方式。）

Note that currently this will fail if root1.getData() returns null. (That may or may not be possible with the way you're adding nodes.)

编辑：正如评论所讨论的，你可以使用哈希codeS做出非常快速的早出 - 但它会增加复杂性。

As discussed in comments, you could use hash codes to make a very quick "early out" - but it would add complexity.

为的，你需要做不可变的（这是一个整体的其他讨论）的或的需要每个节点知道其父，这样，当节点是你的树改（加叶或更改值，例如）需要更新其散列code的，并要求其父更新过的。

Either you need to make your trees immutable (which is a whole other discussion) or you need each node to know about its parent, so that when the node is changed (e.g. by adding a leaf or changing the value) it needs to update its hash code and ask its parent to update too.

这篇关于最有效的方法来测试两个二叉树是否相等的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！