合并两棵树的算法

如果要合并的两棵树具有相等的根 GUID，则算法如下：递归合并函数接受两棵具有相等根的树，返回具有该根的合并树。返回的树根的子项恰好在其中一个输入树中是根的子项，而在两个输入树中作为根的子项的子项以递归方式合并。

如果要合并的两棵树具有不同的根 GUID，则首先其中一个根必须位于另一棵树中，然后在该点执行相同的 GUID 合并。如果 GUID 具有可比性，并且增加了根到叶的次数（如所有三个示例中的情况），则在另一个树中搜索更大的根 GUID 就足够了，否则需要搜索两个根。在树中查找 GUID 的算法也是一个类似于 DFS 的递归函数。如果两个根都不存在在另一棵树中，则这些树是不相交的，不会合并。

F# 中的示例实现演示了 4 个有效的合并请求和 3 个无效的合并请求，在 sharplab.io 上运行：

type Tree<'a> =
  struct
    val rootObject : 'a
    val children : Map<int, Tree<'a>>
    new(r, c) = { rootObject = r; children = c }
  end

type Obj =
  struct
    val guid : int
    new(g) = { guid = g }
  end

let rec mergeSameRoot (tree1 : Tree<Obj>) (tree2 : Tree<Obj>) : Tree<Obj> =
  let children : Map<int, Tree<Obj>> =
    Map.fold (fun (acc : Map<int, Tree<Obj>>) (guid : int) (subtree2 : Tree<Obj>) ->
      match Map.tryFind guid acc with
      | Some (subtree1 : Tree<Obj>) ->
          Map.add guid (mergeSameRoot subtree1 subtree2) acc
      | None -> Map.add guid subtree2 acc
    ) tree1.children tree2.children
  Tree (tree1.rootObject, children)

let rec tryMergeIntoFirst (tree1 : Tree<Obj>) (tree2 : Tree<Obj>) : Tree<Obj> option =
  if tree1.rootObject.guid = tree2.rootObject.guid then
    Some <| mergeSameRoot tree1 tree2
  elif Map.isEmpty tree1.children then
    None
  else
    let update : Option<int * Tree<Obj>> =
      Map.fold (fun (acc : Option<int * Tree<Obj>>) (guid : int) (subtree : Tree<Obj>) ->
        match tryMergeIntoFirst subtree tree2 with
        | Some (result : Tree<Obj>) -> Some (guid, result)
        | None -> acc
      ) None tree1.children
    match update with
      | Some (guid : int, subtree: Tree<Obj>) ->
          Some <| Tree (tree1.rootObject, Map.add guid subtree tree1.children)
      | None -> None

let tryMergeEither (tree1 : Tree<Obj>) (tree2 : Tree<Obj>) : Tree<Obj> option =
  match tryMergeIntoFirst tree1 tree2 with
  | Some (result : Tree<Obj>) -> Some result
  | None -> tryMergeIntoFirst tree2 tree1

let tryMergeReturnList (tree1 : Tree<Obj>) (tree2 : Tree<Obj>) : Tree<Obj> list =
  match tryMergeEither tree1 tree2 with
  | Some (result : Tree<Obj>) -> [result]
  | None -> [tree1; tree2]

let examplesDemo () =
  let rec printTree (tree1 : Tree<Obj>) =
    printf "%d: {" tree1.rootObject.guid
    Map.iter (fun k v -> printTree v) tree1.children
    printf "}, "

  let printMerge tree1 tree2 =
    printTree tree1
    printf "\n+\n"
    printTree tree2
    printf "\n=\n"
    match tryMergeReturnList tree1 tree2 with
    | [a] -> printTree a
    | [a; b] -> printf "Disjoint"
    | _ -> failwith "Unreachable code"
    printf "\n\n"

  let keyValue obj value = (obj, Tree (Obj obj, value))
  let leaf obj = keyValue obj Map.empty

  let example1Tree1 = Tree (Obj 1, Map.ofList [leaf 2; leaf 3])
  let example1Tree2 = Tree (Obj 1, Map.ofList [leaf 4])

  let example2Tree1 = Tree (Obj 1, Map.ofList [leaf 5;
    keyValue 2 <| Map.ofList [leaf 3; leaf 4]
  ])
  let example2Tree2 = Tree (Obj 1, Map.ofList [leaf 8;
    keyValue 2 <| Map.ofList [leaf 6; leaf 7]
  ])

  let example3Tree1 = Tree (Obj 1, Map.ofList [leaf 7;
    keyValue 2 <| Map.ofList [leaf 3;
      keyValue 4 <| Map.ofList [leaf 5; leaf 6]
    ]
  ])
  let example3Tree2 = Tree (Obj 2, Map.ofList [
    keyValue 4 <| Map.ofList [leaf 8; leaf 9]
  ])

  let disjointTree1 = Tree (Obj 1, Map.ofList [leaf 2])
  let disjointTree2 = Tree (Obj 3, Map.ofList [leaf 4])

  printMerge example1Tree1 example1Tree2
  printMerge example2Tree1 example2Tree2
  printMerge example3Tree1 example3Tree2
  printMerge disjointTree1 disjointTree2

  printfn "\nInvalid requests:"

  let silentError1Tree1 = Tree (Obj 1, Map.ofList [leaf 2])
  let silentError1Tree2 = Tree (Obj 2, Map.ofList [leaf 1])

  let silentError2Tree1 = Tree (Obj 1, Map.ofList [
    keyValue 2 <| Map.ofList [leaf 3]
  ])
  let silentError2Tree2 = Tree (Obj 1, Map.ofList [leaf 3])

  let silentError3Tree1 = Tree (Obj 1, Map.ofList [leaf 2; leaf 3])
  let silentError3Tree2 = Tree (Obj 2, Map.ofList [leaf 3])

  printMerge silentError1Tree1 silentError1Tree2
  printMerge silentError2Tree1 silentError2Tree2
  printMerge silentError3Tree1 silentError3Tree2

examplesDemo ()

鼓励解释和详细说明问题的一个好处是，它可以帮助你更好地理解问题。多亏了所有的问题，我认为我现在有一个算法。至少，我有一个似乎有效的概念证明。

简而言之，算法是这样的：找到两棵树边并集的跨森林。

详细说明：将每棵树转换为一组边，取这两组边的并集，然后找到并集的跨森林。如果两棵树只有一个共同的节点，则该生成林将是一个生成树（我认为）。

为了说明这一点，我创建了一个 Haskell 概念验证。函数本身几乎是微不足道的，而我不得不编写一些相当复杂的代码来适应 Data.Graph 笨拙的 API。

一、所需进口：

import Data.Set (Set, (\\))
import qualified Data.Set as Set
import Data.Map.Strict (Map)
import qualified Data.Map.Strict as Map
import Data.Foldable (toList)
import Data.Graph
import Data.Tree

我将展示一些代码以及如何在 GHCi 中与它进行交互，因此，首先，这里是 OP 中的树：

t1 = Node 1 [Node 2 [], Node 3 []]
t2 = Node 1 [Node 4 []]
t3 = Node 1 [Node 2 [Node 3 [], Node 4 []], Node 5 []]
t4 = Node 1 [Node 2 [Node 6 [], Node 7 []], Node 8 []]
t5 = Node 1 [Node 2 [Node 3 [], Node 4 [Node 5 [], Node 6 []]], Node 7 []]
t6 = Node 2 [Node 4 [Node 8 [], Node 9 []]]

将树转换为边列表是单行的（如果忽略类型声明，这是可选的，但惯用）：

edgesOfTree :: Tree a -> [(a, a)]
edgesOfTree (Node x xs) = xs >>= \t -> (x, rootLabel t) : edgesOfTree t

使用它会得到如下结果：

ghci> edgesOfTree t1
[(1,2),(1,3)]
ghci> edgesOfTree t6
[(2,4),(4,8),(4,9)]

表示相同数据的另一种方法是使用邻接列表。虽然我想我可以编写一个函数来直接转换为这种格式，但显然我发现分两步完成更容易（或者更确切地说：不那么困难 - 我在开玩笑？Tree a

edgesToAdjacencyList :: (Foldable t, Ord k, Ord a) => t (k, a) -> Map k (Set a)
edgesToAdjacencyList =
  foldr (\(p, c) -> Map.insertWith Set.union p (Set.singleton c)) Map.empty

以下是这两个函数的使用方式：

ghci> edgesToAdjacencyList $ edgesOfTree t1
fromList [(1,fromList [2,3])]
ghci> edgesToAdjacencyList $ edgesOfTree t6
fromList [(2,fromList [4]),(4,fromList [8,9])]

下一步是我决定使用 Data.Graph 将这种表示形式转换回一个或多个树的直接结果。graphFromEdges 函数有一个非常特殊的 API，因此我需要一个函数来转换为其所需的输入格式。

这很容易成为概念验证中最复杂的代码，但我认为它是 Data.Graph 的产物，而不是算法本身的基本复杂性。换言之，实现细节：

toGraphEdges :: Ord a => Map a (Set a) -> [(a, a, [a])]
toGraphEdges m =
  let edges = (\(k, s) -> (k, k, toList s)) <$> Map.toList m
      leaves =
        fmap (\x -> (x, x, []))
        $ toList
        $ Set.unions (Map.elems m) \\ Set.fromList (Map.keys m)
  in edges ++ leaves

使此函数复杂化的是，该函数不会从邻接列表中推断叶子，因此必须显式列出它们。graphFromEdges

以下是 GHCi 中的样子：

ghci> toGraphEdges $ edgesToAdjacencyList $ edgesOfTree t1
[(1,1,[2,3]),(2,2,[]),(3,3,[])]
ghci> toGraphEdges $ edgesToAdjacencyList $ edgesOfTree t6
[(2,2,[4]),(4,4,[8,9]),(8,8,[]),(9,9,[])]

由于该函数采用三元组列表，因此一个小实用程序函数也被证明是有帮助的：graphFromEdges

fstOf3 :: (a, b, c) -> a
fstOf3 (x, _, _) = x

现在，所有必需的构建块都已到位，以实现所需的功能：

unite :: Ord a => Tree a -> Tree a -> [Tree a]
unite x y =
  let edges = edgesOfTree x ++ edgesOfTree y
      (graph, nodeFromVertex, _) =
        graphFromEdges $ toGraphEdges $ edgesToAdjacencyList edges
  in fmap (fstOf3 . nodeFromVertex) <$> dff graph

第一个表达式将两个树转换为边列表并将它们连接起来。此时，列表可能包含重复项，但由于将列表转换为集合，因此可以有效地处理该问题。toGraphEdges

以下是 OP 中的示例：

ghci> putStrLn $ drawForest $ fmap show <$> unite t1 t2
1
|
+- 2
|
+- 3
|
`- 4

如果你不了解 Haskell，这可能看起来很晦涩难懂，但函数调用只是 - 表达式的其余部分（在 的左侧）只是将结果打印为一棵漂亮的树。unite t1 t2unite t1 t2

ghci> putStrLn $ drawForest $ fmap show <$> unite t3 t4
1
|
+- 2
|  |
|  +- 3
|  |
|  +- 4
|  |
|  +- 6
|  |
|  `- 7
|
+- 5
|
`- 8

第三个示例也受支持：

ghci> putStrLn $ drawForest $ fmap show <$> unite t5 t6
1
|
+- 2
|  |
|  +- 3
|  |
|  `- 4
|     |
|     +- 5
|     |
|     +- 6
|     |
|     +- 8
|     |
|     `- 9
|
`- 7

到目前为止，这只是一个概念证明。我还没有将其翻译成 F# 并将其用于我的实际目的，因此我可能需要调整一些细节，但我认为这看起来很有希望。