haskell - 在 Haskell 中构建一棵树

Question

我是 Haskell 的新手，我正在尝试构建一个包含整数的树，左子树中的每个元素都是 <= 节点值。这是我到目前为止编写的代码，但我不知道如何在其中进行递归。如果您能给我一些指导，我将不胜感激。

data Tree = Leaf | Node Int Tree Tree
    deriving (Eq, Show, Read, Ord)

insert :: Int -> Tree -> Tree
insert x (Tree n i t1 t2) = 

据我了解，我必须检查树的每个节点，看看是否有一个 int，然后递归搜索子树。请帮忙

谢谢

编辑:

我设法做了一些事情，但似乎无法创建新节点或者我检查错了，这是新代码:

data Tree = Leaf | Node Int Tree Tree
    deriving (Eq, Show, Read, Ord)

insert :: Int -> Tree -> Tree
insert x Leaf = Node x Leaf Leaf
insert x (Node i t1 t2)  
              | x <= i    = insert x t1
              | otherwise = insert x t2

为了检查它，我写了:

let tree = insert 5 (insert 10 ( insert 11 ( insert 12 (insert 15 tree))))

但是当我在 ghci 中写入时:

tree

我得到:

Node 5 Leaf Leaf

Answer 1

当您插入一个节点时，您返回的是插入到节点一侧的内容，而不是一个新的 Node 数据 insert 到它的一侧。仅在 Leaf 级别创建新节点。

insert :: Int -> Tree -> Tree
insert x Leaf = Node x Leaf Leaf
insert x (Node i t1 t2)  
          | x <= i    = Node i (insert x t1)  t2
          | otherwise = Node i  t1           (insert x t2)