F# 如何镜像二叉树

Question

F# 新手我正在尝试翻转树枝上的子树。

我们必须使用以下数据类型

 type btree = Empty | Node of btree * int * btree
 type finding = NotFound | Found of int

示例树

 let s = Node (Node(Empty, 5, Node(Empty, 2, Empty)), 3, Node (Empty, 6, Empty))
 (*
      (3)
     /    \
    (5)   (6)
    / \   |  \
   () (2) () ()
      / \
     () ()
 *)

到目前为止，这是我的代码：

 let rec mirror t = function
     | Node(Empty, t, Empty) -> t 
     | Node (t1, t, t2) ->  
     | _ -> failwith "Empty"

示例输入和输出：

 mirror (Node (Node (Empty, 1, Empty), 3, Node (Empty, 4, Node (Empty, 7, Empty)))

会return

 Node (Node (Node (Empty, 7, Empty), 4, Empty), 3, Node (Empty, 1, Empty))

现在代码没有完成任何事情，我需要有关如何移动节点以获得我想要的镜像树的帮助。

我想知道我是否必须为 deleting/inserting 个节点实现另一个功能？非常感谢任何帮助！

Answer 1

镜像就是把左分支变成右分支，把右分支变成左分支。所以在你的递归函数中这样做。例如，如果您从一个基本的 3 节点树开始：

   1
2     3

然后镜像就是

    1
  3   2

所以在代码中这意味着：

let rec mirror t = function
     | Node(Empty, t, Empty) -> t 
     | Node (left, value, right) -> Node (right, value, left)

除了这不适用于较大的树，但这是一个开始。您真正想要的是左右节点的镜像。您应该能够通过在 match 子句的最后一行的正确位置添加 2 个对 mirror 的调用来完成上述功能。

Answer 2

这似乎是作业，所以在我 'hand over' 解决方案之前，我将添加一些学习要点。让我们看看您已经编写的代码，这不是一个糟糕的开始。我已将其粘贴在下面以供参考。

let rec mirror t = function
    | Node(Empty, t, Empty) -> t 
    | Node (t1, t, t2) ->  
    | _ -> failwith "Empty"

您首先通过添加 rec 关键字允许您的函数递归调用自身。你这样做是对的，这实际上是一个非常重要的认识，即完成这项任务的方法是创建一个递归函数。因为，真的，'mirror' 一棵树意味着什么？镜像的意思是，在每个节点，翻转子树的顺序，对每个子树进行镜像。

这是一个递归定义，因为要镜像一个节点，你需要镜像子树。所以您添加 rec 关键字是正确的。但是，在您的代码中，您没有正确处理终端状态 Empty。使用您的 btree 定义，您将最终看到一个 Empty 树，这意味着您将最终抛出异常（使用 failwith)。这显然不是期望的行为。空树的镜子是什么样子的？空的！处理这种情况的方法是将 | _ -> failwith "Empty" 替换为 | Empty -> Empty.

现在，在 F# 中，let foo = function | ... 只是 let foo <arg> = match <arg> with | ... 的语法糖，这意味着您的函数实际上需要两个参数：t还有一个被 function 糖隐藏了。我想这不是您想要的，因此您应该删除当前未使用的参数 t，或者将 function 替换为 match t with。

参数 t 当前未使用的原因是 t 在匹配案例 | Node(..., t, ...) 中重新绑定到整数节点值。这也意味着编译器当前的最佳猜测可能是 mirror 的 return 类型应该是 int，而不是 btree，因为你 return 一个int第一种情况。

最后一点是没有理由直接处理空子树的情况，因为这些也只是 btrees。

牢记以上所有内容，我希望我对问题的解决方案是有意义的

let rec mirror = function
    | Empty -> Empty
    | Node(t1, i, t2) -> Node(mirror t2, i, mirror t1)

F# 如何镜像二叉树

F# how to mirror a binary tree

f#

binary-tree

flip