如何在BST中返回包含给定密钥的两个节点的最小子树？

2024-06-01 • 问答

我在Haskell中定义了一个BST：

data BST a = BST a (BST a) (BST a) | BSTNil deriving Show

以及一些类似的操作：

findElem :: (Ord a,Eq a) => BST a -> a -> Maybe a
findElem BSTNil _ = Nothing
findElem (BST a left right) x
        | x == a = Just x
        | x < a = findElem left x
        | x > a = findElem right x

inorder :: BST a -> [a]
inorder BSTNil = []
inorder (BST a left right) = inorder left ++ [a] ++ inorder right

我应该如何返回包含BST的两个节点的最小子树？

这就是我到目前为止得到的：

subTree :: (Ord a,Eq a) => BST a -> a -> a -> Maybe (BST a)
subTree BSTNil _ _ = Nothing
subTree (BST a left right) x y 
     | findElem (BST a left right) x == Nothing = Nothing
     | findElem (BST a left right) y == Nothing = Nothing
     | findElem left x /= Nothing && findElem left y /= Nothing = subTree 
                                                                  left x y
     | findElem right x /= Nothing && findElem right y /= Nothing = subTree 
                                                                    right x y

仅列举案例，并不多：

两个值都必须在左侧子树中找到，然后从中返回递归结果
一个（或两个）值与当前值匹配，然后尝试查找另一个，如果找到，则返回当前节点
必须在左侧子树中找到较小的值，而必须在右侧子树中找到较大的值，然后尝试找到它们，如果都找到，则返回当前节点
必须在正确的子树中找到两个值，然后从中返回递归结果

要区分这些情况，您应该只比较a，x和y，而不要使用findElem，就像您在{中区分三个情况一样{1}}功能。（但是，如果需要在子树中查找单个元素，则可以调用findElem）。所以我会

findElem

（如@Will Ness所述，如果您知道-或强行使用subTree :: (Ord a,Eq a) => BST a -> a -> a -> Maybe (BST a) subTree BSTNil _ _ = Nothing subTree t@(BST a left right) x y | x < a && y < a = subTree left x y | x == a = findElem t y *> Just t | y == a = findElem t x *> Just t | x > a && y > a = subTree right x y | otherwise = findElem t y *> findElem t x *> Just t -- x < a < y or y < a < x，则可以简化操作

如何在BST中返回包含给定密钥的两个节点的最小子树？

lms886 回答：如何在BST中返回包含给定密钥的两个节点的最小子树？

大家都在问