gpt4 book ai didi

haskell - 如何检查 BST 是否有效?

转载 作者:行者123 更新时间:2023-12-02 08:25:19 24 4
gpt4 key购买 nike

根据 BST 的定义并使用 BST 的通用折叠版本,如何检查 BST 是否有效?

data(Ord a, Show a, Read  a) => BST a = Void | Node {
val :: a,
left, right :: BST a
} deriving (Eq, Ord, Read, Show)


fold :: (Read a, Show a, Ord a) => (a -> b -> b -> b) -> b -> BST a -> b
fold _ z Void = z
fold f z (Node x l r) = f x (fold f z l) (fold f z r)

想法是检查节点值是否大于左子树中的所有值并且小于其右子树中的所有值。这必须是True对于树中的所有节点。一个函数bstList只需输出 BST 中的(有序)值列表即可。

当然,这样的事情是行不通的:

--isBST :: (Read a, Show a, Ord a) => BST a -> Bool
isBST t = fold (\x l r -> all (<x) (bstList l) && all (>x) (bstList r)) (True) t

因为,例如,将折叠函数应用于节点 19最终all (<19) (bstList True) && all (>19) (bstList True) .

a BST

最佳答案

您的问题似乎是您丢失了信息,因为您的函数在检查左右子树时仅返回 bool 值。因此将其更改为还返回子树的最小值和最大值。(这可能也更有效,因为您不需要使用bslist来检查所有元素不再)

当然,创建一个包装函数以在完成后忽略这些“辅助”值。

关于haskell - 如何检查 BST 是否有效?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4981016/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com