二叉搜索树是二进制最大值的特例

2018-06-29 16:10:24

据我了解，在最大堆中，每个节点的值大于或等于它的所有子节点。这同样适用于二叉搜索树，但在此数据结构中，同一级别（同级）上的节点结构正确也很重要。

这让我觉得二叉搜索树基本上是一个具有额外属性的最大堆。所以每个BST也是一个最大的堆。我对吗？

没有; 在BST中，根不会大于左子树中的任何东西，但不会比右边的任何东西都小。正如你所说，最大堆中的根大于子树中的任何内容。所以你可以说BST有一个额外的财产，但是这个财产使得它不是最大的堆。

没有。

结构性差异

基本上，树和堆的结构不同。二叉搜索树仍然是一棵树，所以任何节点的子节点少于2个。但是最大堆仍然是堆，所以只有倒数第二层的节点可以少于2个孩子。

获取排序的元素列表

BST→O（N）=通过遍历以递归方式。

最大堆 - > O（N日志N）=通过删除根中的最大值N次，每次操作需要O（日志N）时间

亲子关系

BST是一个树形数据结构，它具有父母与子女之间以及子女之间的关系。但是，堆只拥有父母和孩子之间的关系，而不是孩子之间的关系。

如果您需要比较，您可以将Binary max Heap视为 “Complete”二叉树 （ 不是完整BST！ ）的扩展， 每个节点的所有子节点都小于它自己 （如此处所述）

二进制堆是二叉树的特例（但不是二叉搜索树！），但不是相反。二进制堆是一个具有形状和堆属性的二叉树：它是一棵完整的树，除了最后一棵树以外，所有的级别都被完全填充，并且所有节点都大于（小于）每个子级。

链接地址: http://www.djcxy.com/p/82825.html