haskell - 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

结果Node 4 Empty Empty不是Node 2 Empty (Node 4 Empty Empty)我所期望的结果。

谁能告诉我，我做错了什么？谢谢 ：）

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