测试两个二叉搜索树是否具有相同的一组元素？

我刚开始使用java和递归方法，我需要一些帮助：我需要确定两个二元搜索树是否具有完全相同的一组元素，而不管树的结构如何。测试两个二叉搜索树是否具有相同的一组元素？

我写了检查，如果树中包含的元素，其所谓的包含方法（）

这是我走到这一步：

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

Basicly我的想法是，该方法只要一个节点还有一个孩子，并且树匹配，就会一直运行。我用例如testTree1.sameContents（testTree2）调用方法;但该方法总是返回false ... 有人可以指出这应该怎么做？

来源

2013-04-24 lsund

执行此操作的最佳方法是使用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 /堆栈采取调用堆栈的地方，这样就可以暂停遍历（每当你进行递归方法调用时，将当前节点存储到你的堆栈中）

来源

2013-04-24 12:59:58

也许提供一些提示，说明如何去编写这个迭代器。 – Dukeling 2013-04-24 13:01:20

好主意，我已经添加了一个实现提示 – 2013-04-24 13:10:12

这只有在迭代器以相同顺序返回元素时才有效。如果你的迭代器包含Objects，使用'equals'代替原始比较器可能会更好。 – Eric 2013-04-24 13:12:36

你可以在两棵树上进行一次遍历并检查两次遍历的结果是否相同。如果相同，我们可以假设两棵树都有相同的元素集合。

来源

2013-04-24 13:29:07 GJ13

还有另一种方法可以做到这一点。您可以使用预先遍历或按顺序遍历将树转换为字符串表示形式。这将需要O(n)时间。比你可以检查这些字符串是否相等。它也可以在O(n)时间完成。所以总的运行时间是O(n)。

这种方法类似于迭代器的解决方案，但这个人是比较通用的，因为可用于“是子树”任务（chechs羯羊树t1是t2子树）。在这种情况下，使用可以使用isSubstring()方法而不是equals()。如果树t1是t2的子树，则比t1的字符串表示是t2的子串。可以在O(log n)时间完成。

来源

2013-04-26 05:24:15

测试两个二叉搜索树是否具有相同的一组元素？

回答

相关问题