haskell - 如何检查二叉树是否具有堆属性？

Question

给定一棵二叉树，我想检查它是否具有堆属性，例如，如果 B 是 A 的子节点，则 key(A)>=key(B)：

data Tree a = Leaf|Node a (Tree a)(Tree a)

我已经开始了我的功能如下：

isHeap :: Tree a -> Bool

isHeap Leaf = True

isHeap (Node a left right) = if (Node a)>= isHeap(left) && (Node a)>= isHeap(right) then True else False

这是错误的，因为 GHCI 告诉它无法将预期类型 Tree a->Tree a->Tree a 与实际类型 Bool 匹配？

我知道我错了，但我认为它在正确的轨道上。有任何想法吗？

Answer 1

你有几个问题。首先，要使用>=你需要添加Ord约束，所以类型isHeap应该是

isHeap :: Ord a => Tree a -> Bool

其次，除了知道子节点是否满足堆属性之外，您还需要子节点的值。您可以匹配子节点类型，例如

isHeap :: Ord a => Tree a -> Bool
isHeap Leaf = True

isHeap (Node a Leaf Leaf) = True
isHeap (Node a c1@(Node b _ _) Leaf) = ...
isHeap (Node a Leaf c2@(Node b _ _)) = ...
isHeap (Node a c1@(Node b _ _) c2@(Node c _ _)) = ...

在最后一个模式中，b和c是子节点的值，您需要将其与父节点 ( a) 的值进行比较，而c1和c2是节点本身。

要回答有关您的错误的问题，Node构造函数是类型的函数

Node :: a -> Tree a -> Tree a -> Tree a

所以表达式(Node a)是 type 的函数Tree a -> Tree a -> Tree a。当你有

if (Node a) >= isHeap(left)

由于isHeap left具有 type Bool，编译器还期望 的左侧>=具有相同的类型。但是，您在编写该子句时遇到问题的原因是您没有子节点的值可以与父节点的值进行比较。