比较Scala中的树

Question

假设我需要比较Scala中的树状数据结构(例如文件系统目录或XML文档)。这很容易，如果我扁平化树来创建序列，但它看起来浪费内存。因此，我想将树平铺以创建迭代器/流。这有意义吗?你的建议是:迭代器还是流?

Answer 1

如果你担心内存消耗，你应该避免流。它们最终会分配和你要遍历的节点一样多的内存。使用流类似于将序列扁平化，只是它是惰性完成的。

使用迭代器可能会更好。然而，树迭代器的实现可能很棘手。一种更简单、也可能更有效的解决方案是，对要比较的两棵树都使用递归。例如:

def compare(a: Tree, b: Tree): Boolean = {
  if (/* trees a and be are not equal */) false
  else if (a.children.length != b.children.length) false
  else {
    for ((c1, c2) <- a.children zip b.children) {
      if (!compare(c1, c2)) return false
    }
    true
  }
}

如果您担心性能问题，您可能希望去掉上面的for-comprehension，并使用while循环遍历子节点。