测试两个二叉树是否相等的最有效方法

Question

你如何在Java中实现二叉树节点类和二叉树类以支持最有效（从运行时间的角度）的等式检查方法（也必须实现）：

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

或者

    boolean equal(Tree t1, Tree t2) {}

首先，我创建了以下Node类：

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

        // standard getters and setters
    }

然后是接收两个根节点作为参数并运行标准递归比较的equals方法：

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

我的第二次尝试是使用数组和索引来实现树的遍历。然后，可以使用按位操作（AND）在两个数组上进行比较 - 从2个数组中读取块，并使用逻辑AND将一个掩码到另一个数组上。我未能使代码正常工作，因此我不会在这里发布它（如果您能实现第二个想法并进行改进，我将不胜感激）。

有什么想法可以最有效地进行二叉树的相等测试吗？

编辑

该问题假定结构相等。（而非语义相等）

然而，测试语义相等的代码，例如“如果两个树的内容相同，即使它们的结构不同，我们是否应该认为这两个树相等？”只需按顺序迭代树，这应该很简单。

- aviad

---

“我们是否应该考虑…” 表示主观意见，这使得在SO上提出此类问题不是很理想（可能会被关闭为“不具建设性”）。你应该明确你所追求的是结构相等还是语义相等。【至少在我看来】 - amit

Answer 1

如果你发现根节点不相等，你仍然要检查所有的分支，这样做是不必要的。在我看来，你的代码可以更简单、更高效，只需一旦发现不相等就立即返回false。

另一个简化的选项是允许你的equals方法接受null值，并将两个null视为相等。这样你就可以避免在不同分支中进行所有的null检查。虽然这样做不会提高效率，但会更简单：

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()返回null，则目前此方法将失败。（使用添加节点的方式可能或可能不会出现此情况。）编辑：如评论中所讨论的那样，您可以使用哈希码来进行快速“提前退出”，但这会增加复杂性。你需要使你的树是不可变的（这是另一个讨论），或者你需要每个节点都知道它的父节点，这样当更改节点时（例如添加叶子或更改值），它需要更新其哈希码并要求其父节点也进行更新。

- Jon Skeet

---

另外，在使用equals之前，您可以使用hashcode。但是您仍然面临O(n)的运行时间。 - stryba

@JonSkeet，您认为Hounshell的评论怎么样（请查看答案的第一句话）？ - aviad

@stryba：hashCode()怎样帮助呢？它必须迭代整个树，这将成为O(n)操作...即使两个哈希码相等，你仍然需要迭代整个树。 - Jon Skeet

@aviad：我原以为你想要结构相等，否则你会写不同的代码:) 我们无法确定你的需求是什么。 - Jon Skeet

@stryba：对于增量哈希，您需要向节点添加另一个字段，以便它知道其父项 - 每个更改都需要向上整个树传播。是的，有简化它的方法（尽管只有哈希代码部分是O（1）-如果哈希匹配，仍然需要以O（n）方式检查实际相等性）。但是，您的评论“在使用equals之前可以使用hashCode”没有提到任何这些内容。我将编辑答案以将其作为选项添加进去。 - Jon Skeet

Answer 2

出于好奇，如果两棵树的内容相同但结构不同，您是否认为它们是相等的？例如，以下这两个是否相等？

  B         C        C      A
 / \       / \      / \      \
A   D     B   D    A   D      B
   /     /          \          \
  C     A            B          C
                                 \
                                  D

这些树具有相同的内容和顺序，但由于结构不同，因此根据您的测试结果将不相等。

如果您想要测试这个相等性，我个人会建议使用中序遍历构建一个用于遍历树的迭代器，并逐个比较树上的元素。

- Hounshell

---

好观点！我点了个赞。我猜结构很重要，但是这一点需要澄清......我会把这个加到问题里。让我们看看别人怎么说。 - aviad

最终，树是否相同的决定取决于问题陈述以及您对假阴性的容忍程度。如果这是一个教科书问题，他们可能意味着结构是相同的。在现实世界中，这通常是无用的，因为通常以非确定性顺序构建树。然后，您基本上正在检查它们是否是相同的对象；引用检查就足够了。此外，请记住，一些树在读取时会改变其结构，而不仅仅是写入，例如Treaps和Splay Trees。 - Hounshell

Answer 3

首先，我做出一些常规假设。这些假设适用于大多数基于树的集合类，但值得检查：

1. 仅当两棵树在树结构和每个节点上的数据值（由data.equals(...)定义）方面均相等时，您才认为它们相等。
2. 树节点允许空数据值（这可能是因为您明确允许空或者因为您的数据结构仅将非空值存储在叶节点中）。
3. 您不知道有任何关于数据值分布的特殊事实可以利用（例如，如果您知道唯一可能的数据值是null或字符串"foo"，则您不需要比较两个非null字符串值）。
4. 树通常会有适度的大小并且合理平衡。特别是，这确保了树永远不会太深，导致深层递归引起的StackOverflowExceptions。

在假设这些假设正确的情况下，我建议的方法是：

• 首先进行根引用相等性检查。这将快速排除要么是两个null，要么是将同一棵树与自身进行比较的情况。这两种情况都非常普遍，而且引用相等性检查非常便宜。
• 接下来检查null。非null显然不等于null，这使您可以尽早退出并确立后续代码的非null保证！非常聪明的编译器理论上也可以利用此保证优化以后的空指针检查（不确定JVM当前是否实现了此功能）。
• 接下来检查数据引用相等性和null。这避免了在首先沿着树分支下降时进行所有树分支的下降，即使在数据不相等的情况下，也会进行这样做。
• 接下来检查data.equals()。再次，您希望在树分支之前检查数据相等性。在检查null之后执行此操作，因为data.equals()可能更加昂贵，并且您希望保证您不会获得NullPointerException。
• 最后一步递归地检查分支的相等性。左或右先检查都无所谓除非一个方向的不平等性更大，在这种情况下，您应该首先检查那一侧。如果例如大多数更改被附加到树的右侧，则可能是这种情况...
• 将比较设为静态方法。这是因为您希望以递归方式使用它，以便将null作为两个参数之一（因此不适合作为实例方法，因为this不能为null）。此外，JVM非常擅长优化静态方法。

因此，我的实现可能是这样的：

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

- mikera

Answer 4

任何树形结构最有效的表示方式是使用父节点列表——维护一个数组，在其中为每个顶点记住其父节点的索引（实际上维护一对数据——父节点的索引和数据值）。然后，您只需要比较两个连续的内存块即可轻松检查它们是否相等。

这种方法仅适用于静态树形结构（即随时间不变）。此外，仅当两个树形结构中的顶点索引相同时，才会认为它们相等。

我相信在常见情况下，如果以上两个条件不成立，则您的实现应该尽可能快。

编辑：实际上，如果您遵循Jon Skeet答案中的建议（至少在确定树形结构不相等时立即返回false），则可以改进您的实现。

- Ivaylo Strandjev

---

谢谢，这个想法在问题中（部分）提到了。我点赞你的回答，并且很希望看到实现这个想法的代码。 - aviad

Answer 5

上面给出的代码会对具有相同根值但不相等的两个树返回 true。我认为这不是你想要的。应该是这样的：

if (!a==b) return false;

这样方法就会执行其余的检查。

（无法从此处登录，原因不明。）

- Gerry Howser