.net - 检查树是否是堆
问题描述
我正在尝试创建一个函数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
推荐阅读
- html - 使用 flexbox 的网格布局
- php - 抽象 foreach 函数
- c# - 在 asp.net 中更改 smtp 主机时出错
- python - 通过 ssh 运行 Pytest 测试时,尽管安装了模块,但我得到“没有名为 pandas 的模块”
- java - Angular2 与 JSP 或 javaEE 的集成
- cassandra - 如何在 openshift 中访问 Cassandra 数据库
- verification - Dafny,调用可能违反上下文的修改子句
- javascript - 使用 Mongoose 软删除不起作用
- ruby-on-rails - JSON 数据在开发中正确显示,但在生产中未正确显示
- ios - 不允许在文本字段中使用 AZ 和 0-9 数字