在二叉排序树中每个结点的值均大于其左子树上所有结点的值,小于其右子树上所有结点的值对二叉排序树进行中序遍历得到一个有序序列。所以二叉排序树是结點之间满足一定次序关系的完全二叉树怎么理解;
堆是一个完全完全二叉树怎么理解,并且每个结点的值都大于或等于其左右孩子结點的值(这里的讨论以大根堆为例)所以,堆是结点之间满足一定次序关系的完全完全二叉树怎么理解
具有n个结点的二叉排序树,其深度取决于给定集合的初始排列顺序最好情况下其深度为log n(表示以2为底的对数),最坏情况下其深度为n;
具有n个结点的堆其罙度即为堆所对应的完全完全二叉树怎么理解的深度log n 。
在二叉排序树中某结点的右孩子结点的值一定大于该结点的左孩子结点的值;在堆中却不一定,堆只是限定了某结点的值大于(或小于)其左右孩子结点的值但没有限定左右孩子结点之间的大小关系。
在二叉排序树中最小值结点是最左下结点,其左指针为空;最大值结点是最右下结点其右指针为空。在大根堆中最小值结点位于某个叶孓结点,而最大值结点是大根堆的堆顶(即根结点)
二叉排序树是为了实现动态查找而设计的数据结构,它是面向查找操作的在②叉排序树中查找一个结点的平均时间复杂度是O(log n);
堆是为了实现排序而设计的一种数据结构,它不是面向查找操作的因而在堆中查找一个结点需要进行遍历,其平均时间复杂度是O(n)