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

algorithm data-structures java binary-tree

2022-09-02 11:07:39

如何在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
    }

然后是将 2 个根节点作为参数并运行标准递归比较的 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逐个掩码。我未能让我的代码正常工作，所以我不在这里发布（我很感激你对第二个想法的实现以及你的改进）。

有什么想法如何最有效地对二叉树进行相等性测试？

编辑

这个问题假设了结构性的平等。（不是语义相等）

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

答案 1

首先，你总是在检查树枝，即使你发现根部不相等。如果你发现不等式就返回，你的代码会更简单（IMO）和更有效。false

简化操作的另一个选项是允许方法接受值并将两个 null 进行比较为相等。这样，您就可以避免在不同的分支中进行所有这些空检查。这不会使它更有效率，但它会更简单：equalsnull

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

编辑：正如评论中所讨论的，您可以使用哈希代码来快速“提前”-但这会增加复杂性。

要么你需要让你的树不可变（这是一个完全不同的讨论），要么你需要每个节点都知道它的父节点，这样当节点被改变时（例如，通过添加一个叶子或改变值），它需要更新它的哈希代码，并要求它的父节点也更新。

答案 2

出于好奇，如果两棵树的内容相同，即使它们的结构不相同，你认为它们是否相等？例如，它们是否相等？

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

这些树以相同的顺序具有相同的内容，但由于结构不同，因此通过您的测试将不相等。

如果你想测试这种相等性，就我个人而言，我只是使用按顺序遍历为树构建一个迭代器，并逐个元素地迭代树。