優雅的解決方案來比較2個二叉樹，並在最早的時間返回false

我想比較2個二叉樹（按順序），並且我想盡早返回，如果它們不相同。優雅的解決方案來比較2個二叉樹，並在最早的時間返回false

我知道你可以遍歷兩棵樹，然後比較輸出，但我想要一個更聰明的解決方案以某種方式在最早的時間返回。

你會如何以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)))) )) ) 
}

來源

2013-03-29 Blankman

在Java中有新的Fork/Join框架，它允許您執行併發的DFS，當它發現第一個區別時可以保釋。也許你可以將它用於Scala？ –

只是一個建議：你可以壓縮tuple-2中的樹，並使用遍歷函數以同樣的方式訪問樹，直到元組的元素髮散。或者，您可以並行運行BFT和DFT，並在第一次失敗時停止。 –

如果你想無論是比較還是遍歷中的短路，都可以將遍歷作爲Stream生成器，zip來自每個遍歷的流，並使用forall或exists來檢測不匹配（forall和exists短路，一旦知道結果就停止）。

我沒有時間寫代碼，所以如果有人更勤奮的話，給他們檢查！

來源

2013-03-29 16:36:54

我不是一個scala專家，但以任何合理的功能語言，我希望這是正確的答案。你已經有工具來完成所有這些事情，而範式背後的動機就是把已知好的部分簡單地組合成一個已知好的整體。滾動你自己的比較器，這是一個蹩腳的版本flatten/zip /摺疊一次都沒有重點。你不妨回到java。 –

只需使用遞歸。除了幾乎相同的巨大樹木的情況外，使用並行性不會獲得任何收益，所以不要打擾。喜歡的東西：

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-29 17:16:42

是的，我想處理非常大的樹木的情況。 – Blankman

表示這是一棵非常巨大的樹，另一棵也是如此，但它稍小一些。如果他們有不同的深度，我們可以弄清楚他們是不同的，除非這是一個昂貴的操作 - 明智嗎？ – Blankman

@Blankman - 樹可以有相同的深度，但是不相同，不是？如果你通過共同的祖先得到這些樹並修改它們，你可以添加一個特殊的哈希碼字段，你用你所添加的哈希碼來更新（例如通過xoring）;那麼如果兩個散列碼匹配，則只需要遍歷樹。如果它們真的很大，那麼應該先做寬度，並在第一次寬度足夠寬時使用並行操作（例如16個元素）。 –

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-29 17:19:27

思考類似的問題最近。雖然Randall Schulz概述的算法非常好（運行時間和門檻明智度），但只有兩棵樹具有相同的形狀時，它纔有用。

「在最早的時間」必須更清楚地定義。通常，這樣的算法具有O（min（n1，n2））的最壞情況運行時間，其中n1和n2是兩棵樹的節點數。鑑於具體問題，遍歷順序可能會影響運行時間。

如果沒有進一步指定問題，可以按照您喜歡的順序遍歷樹。有序自然，不需要進一步預訂。這就是說，這一切歸結爲雷克斯克爾的方法。我剛剛添加了模式匹配的代碼，可能會更容易理解。

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-15 10:51:01 leo

優雅的解決方案來比較2個二叉樹，並在最早的時間返回false

回答

相關問題