寻找更好的解决方案来比较二叉树

Question

这是一个二叉树的类型。

type tree =
  | Node of tree * int * tree
  | Null;;

我有一个问题需要解决：

编写一个名为 tree -> tree -> int 的函数，该函数返回一个数字，表示从根节点开始向下多少层树的值和形状都是相同的。以下是我编写的解决方案：

let rec identical l1 l2 =
    match (l1, l2) with
    | ([], []) -> true
    | ((tree1, s1) :: t1, (tree2, s2) :: t2) ->
         if s1 = s2 then
             match (tree1, tree2) with
             | (Null, Null) -> identical t1 t2
             | (_, Null) -> false
             | (Null, _) -> false
             | (Node (l1, x1, r1), Node (l2, x2, r2)) ->
                if x1 = x2 then identical t1 t2
                else false
         else false;;

let unfold l =
    let l = List.filter (fun (a, b) ->
      if a = Null then false else true) l in
      if List.length l = 0 then raise Nulls else
      List.fold_left (fun acc (a, b) ->
        match a with
        | Node (l, x, r) ->
            (l, "l") :: (r, "r") :: acc) [] l;;

let compare t1 t2 =
    let rec aux l1 l2 result =
        if (List.length l1 <> List.length l2)
            then result
        else
            if (identical l1 l2) then
                try
                    aux (unfold l1) (unfold l2) (result + 1)
                with
                | Nulls -> result
            else
                result
    in aux [(t1, "r")] [(t2, "r")] 0;;

问题在于，我对这段代码非常不满意——即便是对我来说，理解都非常困难。我的做法实际上是在每个层次上创建一个包含左右两边所有子树的列表（并确定子树是左儿子还是右儿子以确定形状），然后比较每个层级的列表。如果它们相同，则增加结果；否则，返回结果。

但是，使用这种“算法”时，我最终得到了这段复杂的代码。那么是否有更简单的方法可以实现呢？

- qiubit

---

在某些有成对表达式的地方，您不需要放置括号。尝试删除一些括号（除非这样更易读？） - didierc

我听说在将函数放入一对括号中时，如果不加括号，可能会导致意外的结果（例如 OCaml 会认为我想要立即计算该函数，而不是将其作为一对元素传递）。这就是为什么我总是使用括号的原因。 - qiubit

抱歉，我知道您想确保编译器不会误解您的意图。基本上，在Ocaml语法中，逗号的优先级较低，但在许多情况下它表现得相当好，避免使用它们可以使代码更轻量化（您肯定知道）。我想这是一种口味问题，或者可能是习惯问题。许多人倾向于避免不必要的括号，因此如果您经常阅读其他人的代码，您可能会习惯于这种写法。 - didierc

顺便说一下，我主要是在考虑模式匹配，当成对不是构造函数的参数时。 - didierc

Answer 1

我想提出以下代码：

let rec compare_tree t1 t2 =
        match (t1, t2) with
        | (Null, Null) | (Null, _ )   | ( _ , Null ) -> 0
        | (Node (t1_l, x, t1_r), Node (t2_l, y, t2_r)) ->
                if x=y then
                        1 + min
                                (compare_tree t1_l t2_l)
                                (compare_tree t1_r t2_r)
                else 0;;

两种测试模式：

let t1 = Node (Node (Null,1,Null),1,Node (Null, 2, Null));;
let t2 = Node (Node (Null,1,Null),1,Node (Null, 3, Null));;
let c = compare_tree t1 t2 in
        Printf.printf "compare = %d\n" c
        ;;

let t1 = Node (Node (Null,1,Null),1,Node (Null, 2, Null));;
let t2 = Node (Node (Null,1,Null),1,Node (Node (Null,1,Null), 2, Null));;
let c = compare_tree t1 t2 in
        Printf.printf "compare = %d\n" c
        ;;

第一次测试返回 1：只有第一层（int 1）在两个树中是相同的，但在第二层，右边的子树不同（2 vs 3）。 第二个测试返回 2，因为头部相同，2个子树具有相同的值，接下来不同的是额外的子树。 这是正确的预期行为吗？

- Pierre G.

---

是的，测试正确。感谢您的代码，这正是我想要的解决方案。 - qiubit

Answer 2

一个更好的算法是执行标准的深度优先搜索。当你发现差异时停止并回溯，或者当你达到之前已经在另一个分支中发现差异的深度时停止并回溯。

- stark