任何类型 ('a) 二叉树遍历 + 打印

Question

我一直在尝试编写代码来遍历和打印任何二进制树。

然而，静态键入会让它变得非常困难。

这是我的尝试。然而，它告诉我Error: This expression has type char but an expression was expected of type printable

在example_tree定义中。

我完全理解，例如"a"是一个字符，而不是可打印的，即使可打印的接受字符。

如果不使用Node(Char('a')...)明确初始化节点，我该如何使其工作？

这是我的代码：

(* Traverse a Binary Tree  *)
exception Error of string
type printable =
| Char of char
| Int of int
| Float of float
| String of string
| Other
type tree = Leaf | Node of printable * tree * tree
(* Makes it easy to print any type *)
let formatter (arg : printable) : string =
match arg with
| Char c -> String.make 1 c
| Int i -> string_of_int i
| Float f -> string_of_float f
| String s -> s
| _ -> raise (Error "Error - Unknown Type")
let rec pre_order (node : tree) : unit =
match node with
| Leaf -> ()
| Node (value, left, right) ->
print_string (formatter value ^ ", ");
pre_order left;
pre_order right
let example_tree =
Node
( 'a',
Node ('b', Node ('d', Leaf, Leaf), Node ('e', Leaf, Leaf)),
Node ('c', Leaf, Node ('f', Node ('g', Leaf, Leaf), Leaf)) )
let () = pre_order example_tree

Answer 1

您不能拥有Node ('c', ...)。您当前对tree的类型定义不允许这样做。

如果去掉printable并切换到由format函数参数化的遍历，则可以在节点中拥有任何您喜欢的类型。(正如我在上面的评论。(

如果你想坚持使用printable，你可以编写一个函数，通过对其中字符的简单描述来构建一个树