Haskell中的二进制搜索树

Question

我开始学习Haskell，因此我尝试实现二进制搜索树。我当前的代码如下：

data SearchTree = Empty | Node Int SearchTree SearchTree
deriving Show

insert :: SearchTree -> Int -> SearchTree
insert Empty x = (Node x Empty Empty)
insert (Node n tl tr) x = if (x > n)
then insert tr x
else insert tl x

但不知何故，insert函数的第二部分工作不正常。如果我尝试这些代码行：

insert (Node 2 Empty Empty) 4

结果是CCD_ 2，而不是我期望的CCD_。

有人能告诉我，我做错了什么吗？谢谢：(

Answer 1

递归时，会丢失外部节点上的信息。你必须在一个节点中重新包装结果：

data SearchTree = Empty | Node Int SearchTree SearchTree
deriving Show

insert :: SearchTree -> Int -> SearchTree
insert Empty x = (Node x Empty Empty)
insert (Node n tl tr) x = if (x > n)
-- note the Node n tl (new_branch)
then Node n tl (insert tr x)
else Node n (insert tl x) tr