生成所有只有 3 个值和 2 个运算符的高度为 n 的树

Question

我有这种树：

type op = Add | Mult ;;

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

它是一个语法二叉树。这意味着每个节点都是一个运算符，每个叶子代表一个数字。在这里，我需要对 3 取模，所以我的值为 [0;1;2].

例如表达式 let e1 = Node(Node(Value 1,Add,Value 2),Add,Value 2) in 表示以下表达式：((1+2)+2).

现在我需要创建一个函数 generate_height : int n -> tree list，其中 return 是所有可能的高度为 n 的树。

一张小图可以提供帮助：

我最初的想法是生成所有空树（我们不关心叶子中的值我们只是将它们设置为 0 但我们需要节点的所有组合）


let generate_empty n =

  let rec gen_rec n op =
    match n with 
    | 0 -> Value 0
    | _ -> Node(gen_rec (n-1) op,op, gen_rec (n-1) op)
  in

 
  (gen_rec n Add)::[gen_rec n Mult]

;;

但它只有 return 两棵树：一棵只有一个添加操作，另一棵有多个。我不知道如何组合运算符。

其次，如果此函数成功，我想遍历所有“空树”并使用 [0;1;2].

的所有组合更改叶子

我有一个开始

let modify_trees_empty list =

  let rec modify_leaf empty_tree = 

    match empty_tree with 
    | Value x -> Value x
    | Node(Value x, op, Value y) -> Node(Val 1, op, Val 1);(*here I want Node(0,op,0),(0,1)..(2,2)*)
    | Node (g, op, d) -> Node(modify_leaf g, op, modify_leaf d)  
  
  in

  let rec iterate_list_and_apply list =
    match list with 
    | [] -> []
    | el :: tl -> [modify_leaf el] @ iterate_list_and_apply tl
  in

  iterate_list_and_apply list
;;

但是它只是把叶子变成了一个，这不是我想要的^^

Answer 1

问题：

您想要所有大小为 n

的树

解决方案：

if n = 0 那么它是所有 Value i 的列表（在你的例子中，i 是 0、1 或 2)
如果n > 0 那么：
- 例如，在名为 sub_trees 的列表中列出所有长度为 n-1 的树。
- 然后创建一个函数 cartesian_product，给定一个列表，returns 所有可能的列表元素。例如，cartesian_product [1,2,3] returns [(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)]
- 然后对于每个可能的运算符（这里是 Mult 和 Add），returns 所有用这个运算符制作的树和一对来自 cartesian_product sub_trees

关于您当前代码的备注

以下是关于您的代码的一些注释，可以帮助您发现新事物。

对于

let rec iterate_list_and_apply list =
    match list with 
    | [] -> []
    | el :: tl -> [modify_leaf el] @ iterate_list_and_apply tl
  in

您不应使用 @ 运算符将唯一元素添加到列表中，而应使用 :: 运算符

| el :: tl -> modify_leaf el :: iterate_list_and_apply tl

另请注意，如果您想让程序更短（但编写这些简单的函数也是一个很好的练习），您也可以使用 List.iter modify_leaf list，它与 iterate_list_and_apply list 的作用相同34=]

此外，这里还有一个你可能不知道的语法糖：
而不是

let rec modify_leaf empty_tree = 
   match empty_tree with 
    | ... -> ...
    | ... -> ...

你可以做到

let rec modify_leaf = function
    | ... -> ...
    | ... -> ...

生成所有只有 3 个值和 2 个运算符的高度为 n 的树

Generate all trees of height n with only 3 values and 2 operators

functional-programming

ocaml

binary-tree

combinations

abstract-syntax-tree

问题：

解决方案：

关于您当前代码的备注