一、树的结构

二、二叉树

二叉树在满足树的结构条件下，还增加了限制条件：
每个节点最多有两个孩子，这两个子树有左右之分次序不可颠倒

三、完全二叉树

完全二叉树是特殊的二叉树，除了最后一层，每一层都是填满的，最后一层会从第一个节点开始，依次向后增加节点

例如abc是完全二叉树def不是：

四、二叉堆

二叉堆在完全二叉树的基础上，增加了节点取值的限制条件

有两种堆， 最大堆和最小堆，最大堆各个父节点的值总是大于或者等于任何一个子节点的值，最小堆则各个父节点的值总是小于或者等于任何一个子节点的值；最大堆中最大的元素刚好存储在堆顶，最小堆中最小的元素刚好存储在堆顶

五、二叉查找树

二叉查找树是一种查找结构，它是一颗特殊的二叉树具有下面这3个性质：

1. 如果左子树不空则左子树上所有结点的值均小于或等于该结点的值
2. 如果右子树不空则右子树上所有结点的值均大于或等于该结点的值
3. 左右子树也分别为二叉查找树

另外，等于的情况一般只出现在左子树或右子树中的某一侧，二叉查找树中没有重复的节点，中序遍历二叉查找树，就会得到一个从小到大的序列，所以它也被称为二叉排序树

六、字典树

tire树又称字典树或前缀树，是一种有序的，用于统计排序和存储字符串的数据结构，它与二叉查找树不同，关键字不是直接保存在节点中，而是由节点在树中的位置决定

每个节点都代表了一个字符，从第一层孩子节点到中间的，某个标记的节点代表了存储的字符串，一般情况下不是所有的节点都有对应的字符串，只有叶子节点和部分内部节点进行了特殊的标记，才存储字符串

例如将这些字符串存储到字典树中，被标记为红色的节点代表存储了，从根到该节点之间字符组成的字符串

例如abcd这条路径中，c和d被标记说明存储abc和abcd

一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，例如abc、abcd、abd都有相同的前缀ab，在字典树中它们有相同的祖先节点a和b

trie树的最大优点就是利用字符串的公共前缀，来减少存储空间与查询时间，从而最大限度地减少无谓的字符串比较，是非常高效的字符串查找数据结构，查我和插入字符串都可达到 O（1） 算法复杂度

七、红黑树

在红黑树当中，节点被标记为红色和黑色两种颜色，并且它还具有下面这3点性质：

其他：