12．堆肯定是一棵平衡二叉树的建立。这句话哪里错了

来源：蜘蛛抓取(WebSpider) 时间：2011-07-01 02:57 标签： 平衡二叉树的建立
您的位置： &
大学是人类—概文明的“反应堆”
优质期刊推荐不知道，堆是完全二叉树，完全二叉树一定是平衡二叉树（是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
）。为什么是错了？
堆是二叉树，但不保证是平
堆不是平衡二叉树。
首先，我们应该有这样的一个约定：二叉平衡树肯定是一颗二叉排序树。
因为只有这样，二叉平衡树才有存在的意义。我们引入二叉平衡树，就是
为了解决二叉排序树的查找效率问题。
这样的话，堆肯定就不是一颗平衡二叉树了，
二叉排序树：或是一颗空树，或者是结点的左子树上的结点关键字都比该结点关键字值小
，该结点的右子树上的结点关键字之都比该结点的关键字值大，并且是递归定义的。
堆：对于一个数组中的关键字，如果按照完全二叉树的结点来造树，则
完全二叉树中的非终端结点关键字值不大于（不小于）其左右孩子的值。
所以综上所述可知，堆不是一颗二叉平衡树。
堆是一颗完全二叉树，但是完全二叉树不一定是平衡二叉树，因为平衡二叉树是一种特殊的二叉查找树，完全二叉树不满足二叉查找树的特点
平衡二叉树是根节点的左右子树高度差小于等于1的二叉排序树，二叉排序树要求根节点的左子树上的值都要比它小，右子树上的值都要比它大。所以堆是完全二叉树但不是平衡二叉树
记住平衡二叉树又称平衡二叉排序树
平衡二叉树是为了防止二叉排序树的单枝极端情况而提出的--又叫平衡二叉排序树！
堆：从任意结点到根节点的路径序列有序。（如图，小根堆对应从大到小的次序）。
平衡二叉树：满足左右子树高度差条件的二叉排序树，既然是二叉排序树，就要满足二叉排序树的编号要求。但明显不满足。
所以堆不是二叉排序树---就算虽然满足左右子树高度差条件（构造堆排序的时候，是按照层次遍历构造的）-----他也不是平衡二叉树
平衡二叉树
首先是一棵二叉搜索树。带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。也就是说，
平衡二叉树
，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。
二叉查找树
1、若左子树不空，则左子树上所有结点的值均小于它的根结
2、若右子树不空，则右子树上所有结点的值均大于它的根结点的值
。而堆并不满足这种条件。所以
堆不是一棵平衡二叉树。
平衡二叉树（Self-balancing binary search tree）又被称为AVL树。
自平衡的 二叉排序树
二叉排序树（Binary Sort Tree），又称（Binary Search Tree）。
都是 Binary Search Tree
我觉得完全二叉树是平衡二叉树
“平衡二叉树（Self-balancing binary search tree ）又被称为AVL树”，堆是平衡树，但不是二叉 搜索树。
堆不一定是二叉排序树，比如小根堆最小值作为根结点此时不是二叉排序树，而平衡二叉树必是二叉排序树。但是高度差是可以保证的，因为堆建树的时候保证必为完全二叉树，完全二叉树高度差绝对值小于等于一
答案必然是错的，你们连平衡二叉树的定义都没搞懂做个屁
平衡二叉树首先一定是二叉排序树。
平衡是在二叉搜索树的基础上增加结点的子树高度差限制。二叉搜索树嘛，对一个结点，左右子结点一大一小，而对堆的一个结点而言，左右都比它大或比它小。
平衡二叉树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉搜索树，反之则不一定。平衡二叉树的常用实现方法有、、、、等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的，可以参考Fibonacci(斐波那契)数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。
对于堆而言，只是要求左右子树的值小于该节点的值；但对于二叉排序树，它要求左子树上的值均小于该节点的值，而右子树上的值均大于该节点的值。
要是平衡二叉树，首先得是二叉搜索树，要成为二叉搜索树，要满足左子树中所有的值小于根节点值，右子树中所有节点值大于根节点的值。
而（大根）堆，只要保证根节点比子节点值都大就可以了。
所以两者根本没有什么必然的联系。
平衡二叉树一定是二叉排序树，二叉排序树右子树节点一定大于左子树节点
平衡二叉树
二叉排序树？？？
AVL树到底是不是一个概念？
AVL是自平衡的二叉排序树。
这道题你会答吗？花几分钟告诉大家答案吧！
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
京ICP备号-4
扫一扫，把题目装进口袋

我要回帖

更多关于 平衡二叉树的建立 的文章

 

随机推荐