从二叉搜索树中删除节点，haskell

我正在制作一个 Haskell 函数来从二叉搜索树中删除一个节点。 我知道根据儿童数量需要采取的行动的规则 目标家长有。

没有孩子 - 删除， 1 个孩子 - 替换为孩子， 2 个子节点 - 找到右子树中的最小值并用该值替换该节点， - 然后，递归删除右子树中的最小值

data BST = MakeNode BST String BST
              |  Empty

deleteNode :: String -> BST



treeBuilder :: [String] -> BST
treeBuilder = foldr add Empty

add :: String -> BST -> BST
add new Empty = (MakeNode Empty new Empty)
add string tree@(MakeNode left value right)
    | string > value = MakeNode left value (add string right)
    | string < value = MakeNode (add string left) value right
    | otherwise = tree

也无法弄清楚为什么 treeBuilder 无法正常工作。它只是按对角线向右打印字符串。

在这些情况下，最好不要考虑从树中删除节点；最好考虑如何将您拥有的树转变为一棵没有您想要的节点的树。

我们来进行一些案例分析：

如果树是空的，那么无论键是什么，结果都是空的：

delete _ Empty = Empty

如果树非空，我们必须查看键是否与节点匹配。如果不匹配，那么我们需要根据键是否大于或小于节点来转换左子树或右子树：

delete key (MakeNode l key' r) | key < key' = MakeNode (delete key l) key' r
delete key (MakeNode l key' r) | key > key' = MakeNode l key' (delete key r)

如果它确实匹配（它必须匹配，因为所有不匹配的情况都已处理），那么我们必须弄清楚如何在没有根节点的情况下创建一棵新树。根据您的描述，如果该节点没有子节点，则将其删除：

delete _ (MakeNode Empty _ Empty) = Empty

如果该节点有一个子节点，请使用：

delete _ (MakeNode l _ Empty) = l
delete _ (MakeNode Empty _ r) = r

否则，找到并删除右子树中的最小键，并将其用作新根的键：

delete _ (MakeNode l _ r) = MakeNode l key r' -- make a new root with min key and new r
  where key = minKey r    -- find the minimum key in the right subtree
        r' = delete key r -- new right subtree with min key removed

        -- a helper function to find the minimum key in a tree
        -- !! does not work on Empty tree !!
        minKey (MakeNode Empty key _) = key
        minKey (MakeNode l _ _) = minKey l