如何在Haskell中实现二叉搜索树的元素删除？附现有代码

Hey there! Let's walk through the issues in your current code and get that BST delete function working correctly.

First, let's break down the problems I spot right away:

• Parameter order mix-up: Your type signature says treeDelete takes a BSTree first, then the element to delete—but your function definition swaps these two arguments. That's going to throw off all your logic right from the start.
• Incomplete delete logic: When you find the node to delete, you just replace its value with Null if it has children. That's not how BST deletion works! For nodes with two children, you need to replace it with either the smallest element in its right subtree (or largest in the left) to maintain the BST property.
• Syntax error in recursion: The line (treeDelete a left) val (treeDelete a right) isn't valid Haskell syntax—you need to construct a Node properly with the recursively modified subtrees.
• Redundant single-node check: You don't need a separate case for nodes with no children; we can handle that in the general node logic.

Here's the fixed, working version of your code, with explanations:

data BinaryTree a = Null | Node (BinaryTree a) a (BinaryTree a) deriving Show
type BSTree a = BinaryTree a

-- Helper to find the smallest element in a BST (leftmost node)
findMin :: BSTree a -> a
findMin (Node Null val _) = val
findMin (Node left _ _) = findMin left
findMin Null = error "Can't find min of an empty tree"

-- Helper to delete the smallest element from a BST
deleteMin :: BSTree a -> BSTree a
deleteMin (Node Null _ right) = right
deleteMin (Node left val right) = Node (deleteMin left) val right
deleteMin Null = Null

-- Correct BST delete function
treeDelete :: (Ord a) => BSTree a -> a -> BSTree a
treeDelete Null _ = Null  -- Empty tree? Nothing to delete
treeDelete (Node left val right) target
    | target < val = Node (treeDelete left target) val right  -- Target is in left subtree, recurse there
    | target > val = Node left val (treeDelete right target)  -- Target is in right subtree, recurse there
    | otherwise =  -- Found the node to delete!
        case (left, right) of
            (Null, _) -> right  -- Only right child? Replace with right subtree
            (_, Null) -> left   -- Only left child? Replace with left subtree
            (_, _) ->  -- Two children: replace with min of right subtree, then delete that min
                let minRightVal = findMin right
                in Node left minRightVal (deleteMin right)

What's happening here? #

• Fixed parameter order: Now treeDelete takes the tree first, then the element to delete—matching your type signature.
• Helper functions: findMin grabs the smallest element in a subtree (we use the right subtree's min for standard BST deletion), and deleteMin removes that smallest element once we've used it to replace the deleted node.
• Proper deletion logic:
  • If the target is smaller than the current node's value, we recurse on the left subtree.
  • If it's larger, we recurse on the right.
  • When we find the node to delete:
    • If it only has one child, we just replace it with that child.
    • If it has two children, we swap its value with the smallest value in the right subtree (which maintains BST order), then remove that smallest value from the right subtree.

Let's test this with a sample tree to see it work:

-- Sample BST:
--      5
--    /   \
--   3     7
--  / \   /
-- 2   4 6
testTree :: BSTree Int
testTree = Node (Node (Node Null 2 Null) 3 (Node Null 4 Null)) 5 (Node (Node Null 6 Null) 7 Null)

-- Deleting 5 should give us:
--      6
--    /   \
--   3     7
--  / \
-- 2   4
main = print $ treeDelete testTree 5

内容的提问来源于stack exchange，提问作者Jayyyyyy