数据结构：树系列（一）类型与概念
自述：
初次写博客，本来呢不知到写些什么，所以创建博客以来，也凉了好几天，但最近刷题时碰到树相关的题，说真的做的头有点大，于是开始恶补树的相关知识，未免忘记，就开启了我的博客之旅，当然我还是一个小白，内容啥的也非全原创，基本上是书上知识加上博客上一些大佬的总结，按照自己的阅读习惯整理了一边，自我感觉我写的应该通熟易懂，哈，就这样吧，省的说我刷字数，虽然想法是这样的，哈，大家心照不宣啊，我是小白一枚，小仙在此向各位大佬虚心求教，有什么不对的，请在下方评论去加以指正，我会及时改正的，嗯应该不会有错的吧。。。
正文：
树与子树
树，何为树？按照书上的定义来说
1 树就是n个结点的有限集合。当n=0时便为空树。（n>=0）
2 任意一颗非空树应该满足：
3 (1)有且仅有一个特定的称为根（Root）的节点；
4 (2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、......、Tn，其中每一个集合本身又是一棵树，并且称为根的子树。
从定义来看，已经简单明了，搁在现实中就是一颗倒挂的树，倒挂的树的顶部是根，在往下是枝干，枝丫，叶子啥的。如果说从定义上不懂，那么有一种表达方式肯定能懂，话不多说直接晒图：
这是树 这也是树
相信这些应该可以让你了解什么是树，若还不能了解，当我没说，继续往下看
了解了树，那么肯定要了解树的相关术语，要不然别人问你，你不知道那怎么办，想装逼都装不成，只能躲在角落画圈圈。。。
树的相关术语
- 结点 （node）： 包含一个数据元素及若干指向其子树的分支
- root根结点: 树的最开始的结点
- 父结点： 当前结点拥有上一级结点时，上一级的结点便是当前结点的父结点
（子结点只能拥有一个父结点） - 子结点： 当前结点拥有下一级结点时，下一级的结点便是当前结点的子结点
（父结点能拥有多个子结点） - 孩子： 一个结点的直接后继称为该结点的孩子。
- 双亲： 一个结点的直接前驱称为该结点的双亲。
- 兄弟： 同一双亲结点的孩子结点之间互称为兄弟。
- 祖先： 从根到该结点所经分支上的所有结点，
- 子孙： 一个结点的直接后继和间接后继的所有结点
- 堂兄弟： 其双亲在同一层的结点。
- 叶子结点： 树中度为0的结点，没有子结点的结点。
（可以理解为树的叶子，嗯现实中的，嘻嘻） - 分支结点： 树中不为0的结点，也称非终端结点。（有子结点的结点）
- 子树: 假设有两颗树 A和B ，A包含B，那么B便是A的子树
- 路径： 从root节点找到该节点的路线
- 有序树
- 结点的度： 结点拥有的子树数目称为度，即拥有子结点的数量
- 树的度： 树中所有结点的度的最大值。
- 结点的层次： 从树根开始定义，根结点时第1层，那么它的子结点便是第2层，以此类推
-
树的深度： 树中结点的最大层次数称为树的深度或高度
（将树比作楼房，树的深度就是说楼有多少层） - 森林
或许，这样子表达你会有点懵，仿佛有种它认识你，你不认识它的感觉，别灰心，哥向来都是拿图说话的，来人把我的图拿上来：
嗯，大家有何不懂的可以结合这张图，对术语品一品，细品。双管之下，有何难！！！！！
树的类型
对于树的类型，网上有很多关于它的介绍，但感觉好乱，有点强迫症的我更形象为它分为两类，二叉树与多叉树。
顾名思义：二叉树：就是有且仅有两个分叉的树，而多叉树当然是有很多分叉的树。
其中二叉树在树这种 数据结构更为常用，所以我了解更多的也是二叉树，在此，我为大家列举下二叉树与多叉树的代表树，并为它们简单介绍
二叉树：
线索化二叉树，二叉排序树，平衡二叉树，赫夫曼树，红黑树
多叉树：
B-树、B+树、字典树（trie树）、后缀树、广义后缀树。
各种树的介绍
线索化二叉树
二叉查找树（二叉排序树）
（图a）
二叉查找树是一种动态查找表（图a），具有这些性质：
（1）若它的左子树不为空，则左子树上的所有节点的值都小于它的根节点的值；
（2）若它的右子树不为空，则右子树上所有节点的值都大于它的根节点的值；
（3）其他的左右子树也分别为二叉查找树；
（4）二叉查找树是动态查找表，在查找的过程中可见添加和删除相应的元素，在这些操作中需要保持二叉查找树的以上性质。
平衡二叉树（AVL树）
（图b）
含有相同节点的二叉查找树可以有不同的形态，而二叉查找树的平均查找长度与树的深度有关，所以需要找出一个查找平均长度最小的一棵，那就是平衡二叉树（图b），具有以下性质：
（1）要么是棵空树，要么其根节点左右子树的深度之差的绝对值不超过1；
（2）其左右子树也都是平衡二叉树；
（3）二叉树节点的平衡因子定义为该节点的左子树的深度减去右子树的深度。则平衡二叉树的所有节点的平衡因子只可能是-1,0,1。
赫夫曼树
红黑树
（图c）
红黑树是一种自平衡二叉树，在平衡二叉树的基础上每个节点又增加了一个颜色的属性，节点的颜色只能是红色或黑色。具有以下性质：
（1）根节点只能是黑色；
（2）红黑树中所有的叶子节点后面再接上左右两个空节点，这样可以保持算法的一致性，而且所有的空节点都是黑色；
（3）其他的节点要么是红色，要么是黑色，红色节点的父节点和左右孩子节点都是黑色，及黑红相间；
（4）在任何一棵子树中，从根节点向下走到空节点的路径上所经过的黑节点的数目相同，从而保证了是一个平衡二叉树。
B-树
（图d）
B-树是一种平衡多路查找树，它在文件系统中很有用。一棵m阶B-树（图d为4阶B-树），具有下列性质：
（1）树中每个节点至多有m棵子树；
（2）若根节点不是叶子节点，则至少有2棵子树；
（3）除根节点之外的所有非终端节点至少有棵子树；
（4）每个节点中的信息结构为（A0,K1,A1,K2……Kn,An），其中n表示关键字个数，Ki为关键字，Ai为指针；
（5）所有的叶子节点都出现在同一层次上，且不带任何信息，也是为了保持算法的一致性。
B+树
（图e）
B+数是B-树的一种变形，它与B-树的差别在于（图e为3阶B+树）：
（1）有n棵子树的节点含有n个关键字；
（2）所有的叶子节点包含了全部关键字的信息，及指向这些关键字记录的指针，且叶子节点本身按关键字大小自小到大顺序链接；
（3）所有非终端节点可以看成是索引部分，节点中仅含有其子树（根节点）中最大（或最小）关键字，所有B+树更像一个索引顺序表；
（4）对B+树进行查找运算，一是从最小关键字起进行顺序查找，二是从根节点开始，进行随机查找。
字典树（trie树）
（图f）
字典树是一种以树形结构保存大量字符串。以便于字符串的统计和查找，经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。具有以下特点（图f）：
（1）根节点为空；
（2）除根节点外，每个节点包含一个字符；
（3）从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
（4）每个字符串在建立字典树的过程中都要加上一个区分的结束符，避免某个短字符串正好是某个长字符串的前缀而淹没。
后缀树
所谓后缀树，就是包含一则字符串所有后缀的压缩了的字典树。先说说后缀的定义。给定一长度为n的字符串S=S1S2..Si..Sn，和整数i，1 <= i <= n，子串SiSi+1…Sn都是字符串S的后缀。以字符串S=XMADAMYX为例，它的长度为8，所以S[1..8], S[2..8], … , S[8..8]都算S的后缀，我们一般还把空字串也算成后缀。这样，我们一共有如下后缀。对于后缀S[i..n]，我们说这项后缀起始于i。
- S[1..8], XMADAMYX， 也就是字符串本身，起始位置为1
- S[2..8], MADAMYX，起始位置为2
- S[3..8], ADAMYX，起始位置为3
- S[4..8], DAMYX，起始位置为4
- S[5..8], AMYX，起始位置为5
- S[6..8], MYX，起始位置为6
- S[7..8], YX，起始位置为7
- S[8..8], X，起始位置为8
- 空字串。记为$。
所有这些后缀字符串组成一棵字典树。
广义后缀树
广义后缀树是好几个字符串的的所有后缀组成的字典树，同样每个字符串的所有后缀都具有一个相同的结束符，不同字符串的结束符不同。
传统的后缀树只能处理一个单词的所有后缀。广义后缀树存储任意多个单词的所有后缀。例如字符串“abab”和“baba”，首先将它们使用特殊结束符链接起来，如表示成“ababbaba#”,然后求连接后的新字符的后缀树，遍历所得后缀树，如遇到特殊字符，如“
”,”#”等则去掉以该节点为跟的子树，最后所得后缀树即为原字符串组的广义后缀树。其实质是将两个字符串的所有后缀，即：abab,bab,ab,b,baba#,aba#,ba#,a#,组成字典树，再进行压缩处理。广义后缀树的一个常应用就是判断两个字符串的相识度。
参考文献：https://www.cnblogs.com/shixiangwan/p/7530015.html
我是小仙，小白一枚，一篇下来我也收益不菲。