0

我刚开始使用 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 ...有人可以指出应该如何做吗？

4

3 回答 3

1

还有另一种方法可以做到这一点。您可以使用前序遍历或中序遍历将树转换为字符串表示形式。这需要O(n)时间。你可以检查这些字符串是否相等。也可以及时完成O(n)。因此，总运行时间为O(n)。

这种方法看起来类似于带有迭代器的解决方案，但这个方法更通用，因为可以用于“is-subtree”任务（检查树是否t1是 的子树t2）。在这种情况下，可以使用isSubstring()method 而不是equals(). 如果树t1是's 的子树，则字符串表示是t2' s 的子字符串。可以及时完成。t1t2isSubstring()O(log n)

于 2013-04-26T05:24:15.623 回答
1

最好的方法是使用Iterator对象——如果两个二叉搜索树包含相同的元素，那么它们的迭代器的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 来代替调用堆栈，这样你就可以暂停遍历（只要你要进行递归方法调用，将当前节点存储到您的堆栈中）

于 2013-04-24T12:59:58.910 回答
0

你能在两棵树上做一个中序遍历并检查两个遍历的结果是否相同。如果相同，我们是否可以假设两棵树具有相同的元素集。

于 2013-04-24T13:29:07.397 回答