algorithm - OCaml中的二叉搜索树预排序算法

在ocaml中实现此算法时遇到问题，因为必须在函数之间打印括号。
算法如下：

BEGIN
   WRITE ( "(" )
   IF (NOT EMPTY tree) THEN
      IF (NOT EMPTY (left_leaf tree)) OR (NOT EMPTY (right_leaf tree)) THEN BEGIN
        WRITE (" ", root tree, " ")
        preorder (left_leaf tree)
        WRITE (" ")
        preorder (right_leaf tree)
      END ELSE
        WRITE (" ", root tree, " ")
   WRITE ( ")" ); {this has to be always executed}
END

这是我在OCaml中的拙劣尝试：

let rec preorderParenthesed tree =

   print_string "(" in
   if not (isEmptyTree tree) then (
      if not (isEmptyTree(leftLeaf tree)) || not (isEmptyTree(rightLeaf tree)) then begin
        print_string " ";
        print_string (string_of_root (root tree));
        print_string " ";
        preorderParenthesed (leftLeaf tree);
        print_string " ";
        preorderParenthesed (rightLeaf tree);
      end else
        print_string " ";
        print_string (string_of_root (root tree));
        print_string " ";
    )
    else if true then print_string ")\n";;

任何帮助都将不胜感激

type bst =
Empty
| Node of (key * bst * bst);;

最佳答案

使用模式匹配，您的函数可以简单得多：

type 'a bst = Empty | Node of ('a * 'a bst * 'a bst)

let rec string_of_tree ~f = function
| Empty ->
  "()"
| Node (value, Empty, Empty) ->
  Printf.sprintf "(%s)" (f value)
| Node (value, left, right) ->
  Printf.sprintf "(%s %s %s)"
    (f value)
    (string_of_tree ~f left)
    (string_of_tree ~f right)

val string_of_tree : f:('a -> string) -> 'a bst -> string = <fun>

f只是一个string_of_*函数。
这些模式描述了以下情况：
树是空的
()
树不是空的，但是两个子树都是
(value)
树不是空的，案例2没有检查
(value left_subtree right_subtree)

关于algorithm - OCaml中的二叉搜索树预排序算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46276845/