如何检查BST是否有效？

Question

如何确定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).

Answer 1

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

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