完全二叉树、二叉查找树、平衡二叉查找树、红黑树

完全二叉树是一种特殊的二叉树,满足以下要求:

1.所有叶子节点都出现在 k 或者 k-1 层,而且从 1 到 k-1 层必须达到最大节点数;

2. 第 k 层可以不是满的,但是第 k 层的所有节点必须集中在最左边。

需要注意的是不要把完全二叉树和“满二叉树”搞混了,完全二叉树不要求所有树都有左右子树,但它要求:

3. 任何一个节点不能只有右子树没有左子树

4. 叶子节点出现在最后一层或者倒数第二层,不能再往上

用一张图对比下“完全二叉树”和“满二叉树”:

左边为完全二 叉 树,右边为满二 叉 树


完全二叉树使用场景:

根据前面的学习,我们了解到完全二叉树的特点是:“叶子节点的位置比较规律”。因此在对数据进行排序或者查找时可以用到它,比如堆排序就使用了它。

二、二叉查找树、平衡二叉查找树、红黑树

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容