java - 测试两个二叉搜索树是否具有相同的元素集？

Question

我刚刚开始使用 java 和递归方法，我需要一些帮助: 我需要确定两个二叉搜索树是否具有完全相同的元素集，无论树的结构如何。

我编写了一个方法来检查树是否包含一个元素，并调用 contains()

这是我到目前为止得到的:

    public boolean sameContents(Node n2) {

    if (contains(n2, n2.key) && n2.left == null && n2.right == null) { return true; }
    if (contains(n2, n2.key) && n2.left != null) { sameContents(n2.left); }
    if (contains(n2, n2.key) && n2.right != null) { sameContents(n2.right); }
     return false; 
   }

基本上我的想法是，只要节点仍然有子节点并且树匹配，该方法就会运行。 我用例如 testTree1.sameContents(testTree2); 调用该方法但该方法总是返回 false... 有人可以指出这应该如何完成吗？

Answer 1

最好的方法是使用 Iterator object - 如果两个二叉搜索树包含相同的元素，那么它们的迭代器的 next 方法应该返回相同的值(即使它们的结构不同)。

// returns true if the trees are equivalent, else false
Iterator itr1 = tree1.getIterator();
Iterator itr2 = tree2.getIterator();
while(itr1.hasNext() && itr2.hasNext()) {
    if(!itr1.next().equals(itr2.next())) {
        return false;
    }
}
return !itr1.hasNext() && !itr2.hasNext(); // returns true if trees were the same size, else false

你应该已经有了一个中序二叉树遍历方法，所以你已经有了一个迭代器 - 只需添加一个 ArrayList/Stack 来代替调用堆栈，这样你就可以暂停遍历(无论何时)进行递归方法调用，将当前节点存储到堆栈中)