一、定义
树，实际上是图的一种。
树是由节点构成的数据结构：
- 每棵树都有一个根节点。
- 根节点有0个或多个子节点。
- 每个子节点有0个或多个子节点，以此类推。
树不应包括环路。节点可以有序或无序排序，可以包含任何类型的值，同时也可以包括或不包括指向父节点的指针。
二、二叉树
1、定义
二叉树是指每个节点至多只有两个子节点的树。
2、二叉搜索树 Binary Search Tree
二叉查找树（又：二叉搜索树，二叉排序树）是二叉树的一种，该树的所有节点满足如下属性：全部左子孙节点<=n<全部右子孙节点。
3、二叉堆（小顶堆与大顶堆）
二叉堆有小顶堆与大顶堆，这里只介绍小顶堆，因为大顶堆原理也一样，只是把排序反过来了。
一个小顶堆是一棵完整二叉树（也就是说，除了底层最右边的封元素，树的每一层都被填满了），其中每个节点都小于其子节点。因此，根是树中的最小元素。
4、红黑树
红黑树是一种自平衡二叉搜索树，不能保证非常严格的平衡，但其平衡性仍然足以确保以O(log N)的时间复杂度进行插入、删除和检索操作。
它们需要较少的内存，并且可以更快地进行再平衡（这意味着可以更快地进行插入和移除操作），所以它们常在树需要被频繁修改的情况下使用。
三、单词查找树
单词查找树（有时被称为前序树），是n叉树的一种变体。
有如下特点：
- 根结点不包含字母，除根结点外每一个结点都仅包含一个大写英文字母；
- 从根结点到某一结点，路径上经过的字母依次连起来所构成的字母序列，称为该结点对应的单词。单词列表中的每个单词，都是该单词查找树某个结点所对应的单词；
四、B树
B树是一种平衡的多路搜索树，多用于文件系统，数据库的实现。也称(B-tree或B-树)
参考
1、《数据结构-树的相关概念》https://www.zybuluo.com/defias/note/280032
网友评论