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

Question

我在 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);;

Answer 1

使用模式匹配可以使您的函数变得更加简单:

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 is simply a string_of_* function.

模式描述了以下情况:

1. 树是空的
   • ()
2. 树不为空，但两个子树都是
   • (值)
3. 树不为空，情况 2 未检查
   • (值 left_subtree right_subtree)