haskell - 插入二叉搜索树(仅存储在叶节点的数据)

Question

我在这个类中使用 Haskell，并且必须使用递归在二叉搜索树中插入。这是我的树定义:

data Tree = Leaf Int | Branch Tree Tree

一个例子是:

tree1 = Branch ((Branch (Leaf 2) (Leaf 4)) (Branch (Leaf 6) (Leaf 10)))

我的插入函数应该获取一个 Tree 和一个 Int 并返回一个 Tree:

insert :: Tree -> Int -> Tree

我只是不明白如何解决这个问题。

编辑: 我知道模式匹配。这是我的想法。

insert :: Tree -> Int -> Tree
insert (Leaf i) j = if (i > j) than Branch (Leaf j) (Leaf i)
                    else Leaf i
insert (Branch l r) j = Branch (insert l j) (insert r j)

我知道这是错误的。如果有两个或多个大于 j 的数字，它会多次插入该值。

编辑2: 所以我按照@Willem Van Onsem的建议得到了这个:

infimum :: Tree -> Int

infimum (Leaf i) = i;
infimum (Branch l r) = infimum r

insert :: Tree -> Int -> Tree
insert (Leaf i) j = if (j > i) then Branch (Leaf i) (Leaf j)
                    else Branch (Leaf j) (Leaf i)
insert (Branch l r) j = if (j > (infimum l)) then Branch l (insert r j)
                        else Branch (insert l j) r

它有效。我想仅用一个函数是不可能完成的。

Answer 1

鉴于您当前的类型，您没有基础来决定将新值插入到哪个子树中；在到达叶子之前，您没有任何可比较的值。

从正确的搜索树开始:

data BST = Node Int BST BST | Empty

每个节点都包含一个值，并且您的 insert函数必须维护搜索属性，该属性声明对于给定节点 Node x left right ， left 中的所有值小于x ，以及 right 中的所有值大于 x 。 (如果您在 x 已经存在时尝试插入它，则无需执行任何操作:键是唯一的。)

insert :: BST -> Int -> BST
insert Empty x = Node x Empty Empty  -- replace the empty tree with a single leaf
insert t@(Node y left right) | x == y = t  -- do nothing
                             | x < y = ...
                             | otherwise = ...

我将其作为练习，以确定在 x /= y 的情况下该怎么做.