树
「树」这种数据结构很像我们现实生活中的「树」，这里面每个元素我们叫做「节点」；用来连接相邻节点之间的关系，我们叫做「父子关系」。
关于「树」，还有三个比较相似的概念：高度（Height）、深度（Depth）、层（Level）。它们的定义是这样的：
节点的高度：节点到子节点最长路径。节点的深度：根节点到子节点所经历的边的个数。节点的层数：节点的深度加一。树的高度：根节点的高度。
「高度」这个概念，其实就是从下往上度量，比如我们要度量第10层楼的高度、第13层楼的高度，起点都是地面。所以，树这种数据结构的高度也是一样，从最底层开始计数，并且计数的起点是0。
「深度」这个概念在生活中是从上往下度量的，比如水中鱼的深度，是从水平面开始度量的。所以，树这种数据结构的深度也是类似的，从根结点开始度量，并且计数起点也是0。
「层数」跟深度的计算类似，不过，计数起点是1，也就是说根节点位于第1层。
二叉树，又称为二叉搜索树，二叉有序树。指一棵空树或左子树所有节点均小于根节点的值，或右子树所有节点均大于根节点的值。叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。每个节点都有左右两个子节点，这种二叉树就叫做满二叉树。
树的遍历方式
前序遍历：根左右。中序遍历：左根右。后序遍历：左右根。
链表是特殊化的树，树是特殊化的图
图图和树的区别是有环图的属性有点和边。图的分类：无向无权图、有向无权图、无向有权图常见算法：最小生成树、最短路径、连通图个数、拓扑排序堆什么是堆：可以快速找到一堆数中最大值或最小值的数据结构堆是一个完全二叉树堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值常见堆有：二叉堆、斐波那契堆根节点最大堆称为大根堆或大尖堆根节点最小堆称为小根堆或小尖堆
应用场景：TopK问题，即查找最大值或最小值
哈希表什么是哈希表：哈希表又称为散列表，是根据keyvalue进行访问的数据结构。
应用场景：安全加密，唯一标识，数据校验，散列函数，负载均衡，数据分片，分布式存储
散列表与二叉查找树的对比
第一，散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在O(n)的时间复杂度内，输出有序的数据序列。
第二，散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在O(logn)。
第三，笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比logn小，所以实际的查找速度可能不一定比O(logn)快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。
第四，散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。
最后，为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。
综合这几点，平衡二叉查找树在某些方面还是优于散列表的，所以，这两者的存在并不冲突。我们在实际的开发过程中，需要结合具体的需求来选择使用哪一个。
liyinchong
null
