OCaml如何编写函数生成高度为n、取值模3、运算符为Add/Mult的所有语法树

你定义的二叉语法树类型如下：

type op = Add | Mult ;;

type tree =
  | Value of int
  | Node of tree * op * tree
;;

需求规则：

• 叶子节点数值仅可取0,1,2三个值
• 实现函数generate_height : int -> tree list，返回所有高度为n的合法树
  • 高度定义：n=1时为叶子节点；n=2时根为运算符，子节点为叶子

你的原有实现存在两个核心问题：

1. 生成空结构的函数仅固定了全Add或全Mult的运算符，没有覆盖所有节点的独立运算符组合
2. 叶子替换函数没有生成所有取值的笛卡尔积，仅返回了固定值的单棵树

第一步：生成所有运算符组合的树结构 #

先不考虑叶子取值，生成所有指定高度、运算符任意组合的树结构（叶子用占位值即可）：

let generate_structures n =
  let rec aux h =
    if h = 1 then 
      [Value 0] (* 高度1只有叶子占位符 *)
    else
      let sub = aux (h-1) in
      (* 遍历所有左子树、右子树、运算符的组合 *)
      List.fold_left (fun acc left ->
        List.fold_left (fun acc right ->
          List.fold_left (fun acc op ->
            Node(left, op, right) :: acc
          ) acc [Add; Mult]
        ) acc sub
      ) [] sub
  in
  aux n
;;

注：上述代码默认生成满二叉树结构，如果你需要支持非满结构（只要最大高度为n即可），只需修改递归部分的子树生成逻辑，允许子树高度小于h-1即可。

第二步：为单棵结构生成所有叶子取值组合 #

对于给定的树结构，递归生成所有叶子取值为0/1/2的组合：

let generate_all_leaf_variants tree =
  let rec aux = function
    | Value _ -> (* 叶子占位符替换为所有可能取值 *)
        [Value 0; Value 1; Value 2]
    | Node(left, op, right) ->
        (* 左子树所有变体 叉乘 右子树所有变体 组合成新节点 *)
        let left_variants = aux left in
        let right_variants = aux right in
        List.fold_left (fun acc l ->
          List.fold_left (fun acc r ->
            Node(l, op, r) :: acc
          ) acc right_variants
        ) [] left_variants
  in
  aux tree
;;

第三步：合并得到最终函数 #

把上面两个步骤结合，得到最终的generate_height函数：

let generate_height n =
  let structures = generate_structures n in
  List.fold_left (fun acc struct_tree ->
    (generate_all_leaf_variants struct_tree) @ acc
  ) [] structures
;;

• 当n=1时，返回[Value 0; Value 1; Value 2]，符合预期
• 当n=2时，结构有2种运算符，每个结构有3*3=9种叶子组合，总共有18棵树，符合要求

内容的提问来源于stack exchange，提问作者Théo Exagon