ocaml - 大小为 7 且高度为 3 的二叉搜索树

Question

我正在构建一个大小为 7、高度为 3 的二叉搜索树。我只需要对其进行硬编码，而不是通过函数生成它。

这是我硬编码的树

Node (Node (Node (Empty, 0, Empty), 1, 
Node (Empty, 3, Empty)), 5
Node (Empty, 7, Node (8, 9, Empty))))

我想要的是节点 9 有两个孩子（8 和空）。但是，我在 8 上不断收到错误消息，提示“此表达式的类型为 int，但预期的表达式为 int 树类型”。我该如何纠正？

谢谢！

Answer 1

你不能8为叶子写作。你必须写Node (Empty, 8, Empty)。

type tree = Empty | Node of tree * int * tree

(* the tree

           5
         /  \
        /    \
       1      7         
     /  \      \
    0    3      9
               /
              8
*)
let t =
  Node (
    Node (Node (Empty, 0, Empty),
          1, 
          Node (Empty, 3, Empty)),
    5,
    Node (
      Empty,
      7,
      Node (Node (Empty, 8, Empty),
            9,
            Empty)
    )
  )

(* With an auxliary function we can do this to get the same tree: *)

let leaf k = Node (Empty, k, Empty)

let t' =
  Node (
    Node (leaf 0, 1, leaf 3),
    5,
    Node (Empty, 7, Node (leaf 8, 9, Empty)))

Answer 2

Node 的第一个元素必须是树，而不是像int.

因此，您不能将 8 放在预期有一棵树的地方。可能，您的意思是拥有Node (Empty, 8 Empty)而不是8.