树的的概念与结构🤔
树是个甚么？和现实中的数差不多，有根有茎有枝有叶，长的和向下延伸的树根差不多，也可以看成一棵倒立的树，==树是一种非线性数据结构，由 n（n>=0）个有限节点组成一个具有层次关系的集合，具象一下就类似这样：
他有一个特殊的节点，称为根节点，也就是上图的 A 节点，除根节点外其余节点都被分成 M 个不相交的集合，每个集合又是一棵结构与树类似的子树，每棵子树根节点有且只有一个，后继节点可以是 0 个或者多个。因此，树是递归定义的。
这里就又需要思考递归的含义，递归是当前问题和子问题的集合，这里的树是根和n个子树构成，而每个子树的结构又是如此，开始逐渐套娃，直到遇到“叶子”结束。
注意，树与非树的区别就在于：
- ==树结构的子树是互不相交的（带回路的结构叫图）==
- ==除了根节点外，其余节点有且仅有一个父节点==
- ==一颗有N个节点的数有N-1条边==
基本术语🤔
不理解这些基本概念后面没法玩儿捏，还是得知道怎么去描述：
- 结点的度：结点的子树个数；
- 树的度：树的所有结点中最大的度数；
- 父结点：有子树的结点是其子树的根节点的父结点；
- 子结点：若A结点是B结点的父结点，则称B结点是A结点的子结点；
- 兄弟（姐妹）结点：具有同一个父结点的各结点彼此是兄弟结点（还有堂兄弟（姐妹）节点，自己意会就行懒得打字）；
- 祖先结点：沿树根到某一结点路径上的所有结点
- 子孙结点：某一结点的子树中的所有结点
结点的层次：规定根结点在1层，其他任一结点的层数是其父结点的层数加1；
- 森林：由m（m>0）棵互不相交的树的集合称为森林
树的表示🤔
树要进行表示可不好表示，因为有一个大问题——==子节点个数不确定==。
这里树必然是一个链式结构，每个节点都有存的值以及指向孩子的指针，现在我们所使用的结构大多为顺序表，有人会用数组来搞（下标为孩子个数），也可以使用C++语法的 vector 来进行操作，但这些都只能算是中规中矩，这里介绍一种很优秀的表示方法可以不用关心度的多少和空间的消耗：孩子&兄弟表示法。
在强调一遍，这个结构表示树是最优秀的，没有之一！
typedef int datatype;
struct node
{
struct node* first;//第一个孩子节点
struct node* next;//指向下一个兄弟节点
datatype data;//数据域
}来说明一下，随便以一个数结构为例：
A 的第一个孩子是B，则 first 指向B，而 A 的其他孩子怎么办呢？A 会先抛开不管，父母的二胎总喜欢叫老大来带，压力来到了 B 的身上， B 的 next 指向他的兄弟节点 C，也就是 A 的另一个孩子， C 没有兄弟了，就可以甩手无后顾之忧，他的 next 指向 NULL。
==总结一下就是父亲指向第一个孩子，其余的都用孩子的兄弟指针链接起来即可==，掌握了这个道理，无论多少孩子都无所谓，随便你玩儿。
树的实际应用🤔
树可以用来表示文件系统的目录树结构，比如最常见的：
其实这只是一种显示方式，目录树要依赖于其他主体，并不是内容本身，在Word ，Excel，Notepad++ 等平台都是不一样的。
二叉树🤔
二叉树这位重量级，各位多多少少有所耳闻吧，今天就换他来认识认识你。
二叉树就是一个度为 2 的树，即每个节点最多有两个子节点，当然，二叉树存在两个子节点时，节点有左右之分，顺序是绝对的，因此二叉树也是个有序树。
这里也介绍一下几个特殊的二叉树：
1. 斜二叉树
2. 满二叉树
每一层的节点都到达了最大值，层数为 n，那他的节点数就是 2^n-1 个（本质就是一个等比数列）。
3. 完全二叉树
这是一种效率贼高的数据结构，满二叉树是特殊的完全二叉树，完全二叉树由满二叉树引申出来，即（n-1）层都是满的，最后一层不满，但必须是从左到右挨的严严实实的。他们的优势就是用来表示一种数据结构——堆。
==那么问题来了，现在这里存了一堆数，这一堆数中谁是谁的左孩子，谁又是谁的右孩子呢？==
我们用数学关系是可以表示出来的，益父子节点的下标为关系计算：
父节点 = （子节点-1）/2；
左孩子节点：父节点 * 2 +1；
右孩子节点：父节点 * 2 + 2；
你可能会疑惑为什么父节点没有根据左孩子和右孩子来计算，原因很简单，不管是奇数还是偶数，相邻两个减1除2的结果是相同的。
二叉树的性质🤔
- 若规定根节点的层数为1，则一棵非空二叉树的第 n 层最多有2^(n-1)个节点;
- 若规定根节点的层数为1，则深度为 h 的二叉树最大结点数为 （2^h） -1；
- 任意二叉树，度为0的节点比度为 2 的节点永远多 1 个；
- 具有n个节点的完全二叉树深为log2x+1（其中x表示不大于n的最大整数）；
- 如果对一颗有n个结点的完全二叉树（其深度为[log2n]+1）的结点按层序编号（从第一层到[log2n]+1层，每层从左到右），对任一结点i（1<= i <=n）:
（1）如果i=1，则结点i是二叉树的根，无双亲，如果i>1,则其双亲结点是结点 i/2
（2）如果2i>n，则结点i无左孩子（结点i为叶子结点）否则左孩子是结点 2i。
（3）如果2i+1>n,则结点i无右孩子，否则其右孩子是结点2i+1。
