到目前为止，我们已经知道了树的基本概念，树的存储方式，以及树的前、中、后序遍历。接下来我们一起分享常见的一些树，主要从定义及用途上来分享，算是科普。
如果你对树已经有很深入的研究，那么可以考虑略过；反过来还是值得你看一看。那么都有哪些常见的树呢？我们先列举一下：
满二叉树
完全二叉树
二叉查找（搜索）树
红黑树
堆树
#考考你：1.你知道常见的树都有哪些吗2.你知道每一种树的特点吗2.案例2.1.满二叉树
#满二叉树定义：1.叶子节点都在最底层2.除了叶子节点，每个节点都有左、由两个子节点#特点：1.满二叉树，是一棵特殊的完全二叉树2.关于完全二叉树，参考：2.22.2.完全二叉树
#完全二叉树定义：1.叶子节点都在最底下两层2.最后一层的子节点，都靠左排列3.除了最后一层，其它层的节点个数，都要达到最大#特点：1.可以通过数组实现顺序存储2.从下标1存储根节点开始：i存储父节点2*i存储左子节点2*i+1存储右子节点3.每个节点省去链表存储法中的左、右两个子节点指针，有效节省了存储空间2.3.二叉查找树
#二叉查找树定义：1.树中的每一个节点的值2.都要大于左子树中每个节点的值3.都要小于右子树中每个节点的值#特点：1.二叉查找树是最常用的一种二叉树，原因：1.1.通过中序遍历二叉查找树，可以实现顺序访问二叉树每一个节点1.2.支持快速插入、删除、查找操作，理想情况下时间复杂度是：O(logn)2.与散列表对比：2.1.二叉查找树，支持动态数据集合的快速插入、删除、查找操作，时间复杂度：O(logn)2.2.你还记得散列表吗？散列表也支持动态数据集合的快速插入、删除、查找操作，时间复杂度：O(1)2.3.疑问：既生瑜(常量级的散列表)、何生亮(对数级的二叉查找树)2.4.可能的原因：a.散列表中存储的数据是无序的，不能实现顺序访问b.二叉查找树，通过中序遍历即可实现顺序访问c.散列表构造实现复杂，需要考虑：散列函数设计、散列冲突解决、扩容、缩容d.二叉查找数构造实现相对简单2.5.在实际应用中，我们需要根据业务需求选择：散列表、或者二叉查找树。它们的同时存在并不冲突，不是非瑜即亮的问题2.4.红黑树
#红黑树定义：1.红黑树是一棵二叉查找树2.红黑树是一棵的二叉查找树3.的意思是指：任意一个节点，它的左、右子树的高度相差，不能大于14.疑问：为什么需要平衡二叉查找树呢5.可能的原因：a.二叉查找树支持快速的插入、删除、查找操作，时间复杂度：O(logn)b.但是二叉查找树在动态插入、删除操作中，可能会退化，极端情况下会退化成链表c.这个时候时间复杂度是：O(n)d.为了避免二叉查找树退化，需要维护它的平衡性，保证操作效率#特点：1.如何构造一棵红黑树呢？2.红黑树满足：a.根节点是黑色的节点b.叶子节点不存储数据，都是黑色的空节点c.红色的节点不能相邻，必须被黑色节点隔开d.每个节点，从该节点到达可达叶子节点的所有路径上，黑色节点数目相同c.jdk8中HashMap、ConcurrentHashMap在解决散列冲突的时候，使用了红黑树与链表结合。推荐你可以看一下源码2.5.堆树
#堆的定义1.堆居然也是一棵树，没错，它叫做堆树，通常用于堆排序2.注意这里的堆，可不是jvm的堆内存，要区分开来。它们是两个不同的种族3.堆的具体描述：a.堆是一棵完全二叉树b.堆中每一个节点的值，都必须大于等于（或者小于等于）左、右子树中的每个节点值c.如果大于等于左、右子树节点值，叫做大顶堆d.如果小于等于左、右子树节点值，叫做小顶堆#特点1.基于堆的定义描述2.在实际软件开发中，堆可应用于：a.实现优先级队列（事实上堆本身就是优先级队列）b.求解TopN问题c.求解中位数问题预览时标签不可点收录于话题#个上一篇下一篇