1

我想比较2个二叉树（按顺序），如果它们不一样，我想尽早返回。

我知道你可以遍历两棵树，然后比较输出，但我想要一个更聪明的解决方案，以便尽早返回。

您将如何在 scala 中以优雅的方式做到这一点？演员？

节点：

case class Node(
  var data: Int,
  left:Option[Node],
  right:Option[Node]
)

在我的主目录中，我有 3 个当前完全相同的树，但只需将其粘贴到此处，以便在需要时对其进行修改：

def main( args:Array[String] ) = {
  val tree = Node( (3),
                       None,
                       Some(Node( (5),
                                  Some(Node( (1),
                                       None,
                                       None )),
                               Some(Node( (9),
                                        None,
                                        Some(Node( (15),
                                                   None,
                                                   None )) ))  ))  )

  val tree2 = Node( (3),
                      None,
                      Some(Node( (5),
                                 Some(Node( (1),
                                      None,
                                      None )),
                              Some(Node( (9),
                                       None,
                                       Some(Node( (15),
                                                  None,
                                                  None )) ))  ))  )
  val tree3 = Node( (3),
                      None,
                      Some(Node( (5),
                                 Some(Node( (1),
                                      None,
                                      None )),
                              Some(Node( (9),
                                       None,
                                       Some(Node( (15),
                                                  None,
                                                  None )) ))  ))  )
}
4

4 回答 4

3

如果您想在比较和遍历中都短路，您可以将遍历转换为Stream生成器，zip来自每个遍历的流并使用forall或exists检测不匹配（forall并且exists短路，一旦停止结果已知）。

我没有时间写代码，所以如果有人更勤奋，请给他们检查！

于 2013-03-29T16:36:54.750 回答
1

最近在想一个类似的问题。虽然 Randall Schulz 概述的算法会很棒（在运行时和 stile 方面），但它只有在两棵树具有相同形状的情况下才有效。

必须更清楚地定义“最早”。一般来说，这种算法的最坏情况运行时间为 O(min(n1,n2))，其中 n1 和 n2 是两棵树的节点数。给定一个具体问题，遍历顺序可能会对运行时间产生很大影响。

如果没有进一步指定问题，您可以按照您喜欢的任何顺序遍历树。秩序井然自然而然，无需进一步记账。也就是说，这一切都归结为 Rex Kerr 的方法。我刚刚添加了带有模式匹配的代码，这可能更容易理解。

def check(tree1:Node,tree2:Node): Boolean = {
    def checkOption(tr1:Option[Node], tr2:Option[Node]) = (tr1,tr2) match {
        case (None, None)         => true
        case (Some(t1), Some(t2)) => check(t1,t2)
        case _                    => false
    }

    (tree1,tree2) match {
        case (Node(d1,l1,r1), Node(d2,l2,r2)) if(d1==d2) => 
            checkOption(l1,l2) && checkOption(r1,r2)
        case _ => false
    }
}
于 2013-05-15T10:51:01.173 回答
1

只需使用递归。除了几乎相同的巨型树的情况外，使用并行性不会获得任何好处，所以不要打扰。就像是：

def same(n: Node, m: Node): Boolean = {
  if (n.data != m.data || 
      n.left.isEmpty != m.left.isEmpty || 
      n.right.isEmpty != m.right.isEmpty) {
    false
  }
  else if (n.left.exists(a => m.left.exists(b => !same(a,b)))) false
  else !n.right.exists(a => m.right.exists(b => !same(a,b)))
}

如果您的树可能有数千层深，则应切换到广度优先尾递归策略，而不是这种适当的递归策略（通过跟踪深度 n 处每侧的每个非空节点）。

于 2013-03-29T17:16:42.117 回答
0 
object Main extends App {

  implicit val executor = ExecutionContext.global
  val branchLevel = 3

  def differentSequential(n1: Node, n2: Node) = differentOpt(Some(n1), Some(n2))

  def differentConcurrent(n1: Node, n2: Node) = differentPar(Some(n1), Some(n2), branchLevel)

  def differentOpt(n1: Option[Node], n2: Option[Node]): Boolean = {
    (n1, n2) match {
      case (Some(Node(d1, l1, r1)), Some(Node(d2, l2, r2))) =>
        d1 != d2 || differentOpt(l1, l2) || differentOpt(r1, r2)
      case _ => false
    }
  }

  def differentPar(n1: Option[Node], n2: Option[Node], level: Int): Future[Boolean] = {
    (n1, n2) match {
      case (Some(Node(d1, l1, r1)), Some(Node(d2, l2, r2))) => {
        if (d1 != d2)
          Future.successful(false)
        else if (level > 0) {
          val leftR = differentPar(l1, l2, level - 1)
          val rightR = differentPar(r1, r2, level - 1)
          combineOr(leftR, rightR)
        } else {
          Future.successful(differentOpt(l1, l2) || differentOpt(r1, r2))
        }
      }

      case _ => Future(false)
    }
  }

  private def combineOr(f1: Future[Boolean], f2: Future[Boolean]): Future[Boolean] = {
    val p = Promise[Boolean]()
    bind(p, f1, f2)
    bind(p, f2, f1)
    p.future
  }

  private def bind(p: Promise[Boolean], f: Future[Boolean], other: Future[Boolean]) {
    f.onComplete {
      case Success(x) => if (!x) p.completeWith(other) else p.trySuccess(true)
      case Failure(t) => p.tryFailure(t)
    }
  }


}

DifferentSequential 将比较尽可能少的节点并使用简单的模式匹配。我还尝试了一个版本，它开始同时检查树的几个分支。

注意：此代码未经测试

于 2013-03-29T17:19:27.537 回答