我正在尝试创建一个函数chkHeapProperty,该函数将检查给定的堆是否满足堆要求:">存储在节点中的值必须小于或等于其子节点">堆示例:
1
/
2 3
let rec chkHeapProperty heap =
match heap with
| EmptyHP -> true
| HP(root, leftHeap, rightHeap) when root < leftHeap && root < rightHeap -> true
这就是我得到的方式。我的第一个想法是遍历所有节点并将它们放入一个列表中,然后遍历该列表,但我觉得必须有一种更有效的方法和更实用的方法。有什么想法吗?
如果此树的根小于其两个子树的根,并且子树也是堆,则此根也必须小于子树的所有元素。
(花点时间说服自己这是真的。
因此,您不需要遍历所有子项和孙项(等等(,只需检查每个子树的根,然后递归检查子树的"堆"。
如果先定义帮助程序函数,这会更容易,
let lesser x heap = match heap with
| EmptyHP -> true
| HP(root, _, _) -> x <= root
然后
let rec isHeap heap =
match heap with
| EmptyHP -> true
| HP(r, h1, h2) -> lesser r h1 && lesser r h2 && isHeap h1 && isHeap h2