Tree | 树
树的具体定义
既然已经有循序表，链表，队列等线性结构了，应该满足任何需求了吗？
不是的，想企业架构图谱，关系图，地图(四叉树)，家庭关系族谱等……，所以很多关系并不是常规的线性结构就可以表示的，常常存在这一对多，多对多的关系，比如 dom 树，目录树，等等 类似这样
企业的职级关系和家庭关系
 |  |
|---|
它们之间的关系都像自然界中的树一样，从同一个“根”衍生出许多“枝干”，再从每一个“枝干”衍生出许多更小的“枝干”，最后衍生出更多的“叶子”。
树（tree）是 n（n≥0）个节点的有限集。当 n=0 时，称为空树。在任意一个非空树中，有如下特点。
- 有且仅有一个特定的称为根的节点。
- 当n>1时，其余节点可分为m（m>0）个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。
在上图中，节点1是根节点（root）; 节点5、6、7、8是树的末端，没有“孩子”，被称为叶子节点（leaf）。图中的虚线部分，是根节点 1 的其中一个子树。
同时，树的结构从根节点到叶子节点，分为不同的层级。从一个节点的角度来看，它的上下级和同级节点关系如 下图。
节点 4 的上一级节点，是节点 4 的父节点（parent）;从节点4衍生出来的节点，是节点 4 的孩子节点（child）;和节点 4 同级，由同一个父节点衍生出来的节点，是节点 4 的兄弟节点（sibling）。
树的最大层级数，被称为树的高度或深度。显然，上图这两颗树的高度是4。
看看最典型的 🌲
什么是二叉树
二叉树（binary tree）是树的一种特殊形式。二叉，顾名思义，这种树的每个节点最多有2个孩子节点。注意，这里是最多有2个，也可能只有1个，或者没有孩子节点。
二叉树节点的两个孩子节点，一个被称为左孩子（left child），一个被称为右孩子（right child）。这两个孩子节点的顺序是固定的，就像人的左手就是左手，右手就是右手，不能够颠倒或混淆。
此外，二叉树还有两种特殊形式，一个叫作 满二叉树，另一个叫作 完全二叉树。
满二叉树
一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，那么这个树就是满二叉树。
简单点说，满二叉树的每一个分支都是满的。
完全二叉树
对一个有 n 个节点的二叉树，按层级顺序编号，则所有节点的编号为从 1 到 n。如果这个树所有节点和同样深度的满二叉树的编号为从 1 到 n 的节点位置相同，则这个二叉树为完全二叉树。
在上图中，二叉树编号从 1 到 12 的 12 个节点，和前面满二叉树 编号从 1 到 12 的节点位置完全对应。因此这个树是完全二叉树。
完全二叉树的条件没有满二叉树那么苛刻: 满二叉树要求所有分支都是满的;而完全二叉树只需保证最后一个节点之前的节点都齐全即可。
二叉树的存储
- 链式存储
- 数组
链式存储
链式存储是二叉树最直观的存储方式
链表是一对一的存储方式，每一个链表节点拥有data变量和一个指向下一节点的next指针。而二叉树稍微复杂一些，一个节点最多可以指向左右两个孩子节点，所以二叉树的每一个节点包含 3 部分。
- 存储数据的
data变量 - 指向左孩子的
left指针 - 指向右孩子的
right指针
数组存储
使用数组存储时，会按照层级顺序把二叉树的节点放到数组中对应的位置上。 如果某一个节点的左孩子或右孩子空缺，则数组的相应位置也空出来。
为什么这样设计呢？因为这样可以更方便地在数组中定位二叉树的孩子节点和父节点。
假设一个父节点的下标是 parent，那么它的左孩子节点下标就是 2 * parent + 1;
右孩子节点下标就是 2 * parent + 2。
反过来，假设一个左孩子节点的下标是 leftChild，那么它的父节点下标就是 (leftChild - 1)/ 2。
假如节点 4 在数组中的下标是 3，节点 4 是节点 2 的左孩子，节点 2 的下标可以直接通过计算得出。
节点2的下标 = (3 - 1)/2 = 1
显然，对于一个稀疏的二叉树来说，用数组表示法是非常浪费空间的。
什么样的二叉树最适合用数组表示呢？--二叉堆
二叉树的应用
二叉树包含许多特殊的形式，每一种形式都有自己的作用，但是其最主要的应用还在于进行 查找操作 和维持 相对顺序 这两个方面。
查找
二叉树的树形结构使它很适合扮演索引的角色。
这里我们介绍一种特殊的二叉树：二叉查找树（binary search tree）。
二叉查找树在二叉树的基础上增加了以下几个条件。
- 如果左子树不为空，则左子树上所有节点的值均小于根节点的值
- 如果右子树不为空，则右子树上所有节点的值均大于根节点的值
- 左、右子树也都是二叉查找树
二叉查找树的这些条件有什么用呢？当然是为了查找方便。
例如查找值为4的节点，步骤如下。
访问根节点6，发现4<6。
访问节点6的左孩子节点3，发现4>3。
访问节点3的右孩子节点4，发现4=4，这正是要查找的节点。
对于一个节点分布相对均衡的二叉查找树来说，如果节点总数是 n，那么搜索节点的时间复杂度就是 O(logn)，和树的深度是一样的。
这种依靠比较大小来逐步查找的方式，和二分查找算法非常相似。
维持相对顺序
这一点仍然要从二叉查找树说起。二叉查找树要求左子树小于父节点，右子树 大于父节点，正是这样保证了二叉树的有序性。
因此二叉查找树还有另一个名字——二叉排序树（binary sort tree）。
新插入的节点，同样要遵循二叉排序树的原则。例如插入新元素5，由于5<6，5>3，5>4，所以5最终会插入到节点4的右孩子位置。
再如插入新元素10，由于10>6，10>8，10>9，所以10最终会插入到节点 9 的右孩子位置。
这一切看起来很顺利，然而却隐藏着一个致命的问题。什么问题呢？下面请试着在二叉查找树中依次插入9、8、7、6、5、4，看看会出现什么结果。
怎么解决这个问题呢？这就涉及二叉树的自平衡了。二叉树自平衡的方式有多种，如红黑树、AVL树、树堆等
二叉树的遍历
在计算机程序中，遍历本身是一个线性操作。所以遍历同样具有线性结构的数组或链表，是一件轻而易举的事情但是二叉树不一样，是典型的非线性数据结构，遍历时需要把非线性关联的节点转化成一个线性的序列，以不同的方式来遍历，遍历出的序列顺序也不同。
那么，二叉树都有哪些遍历方式呢？
从节点之间位置关系的角度来看，二叉树的遍历分为4种。
- 前序遍历
- 中序遍历
- 后续遍历
- 层序遍历
从更宏观的角度来看，二叉树的遍历归结为两大类。
- 深度优先遍历（前序遍历、中序遍历、后序遍历）。
- 广度优先遍历（层序遍历）。
深度优先遍历 dfs
深度优先和广度优先这两个概念不止局限于二叉树，它们更是一种抽象的算法思想，决定了访问某些复杂数据结构的顺序。在访问树、图，或其他一些复杂数据结构时，这两个概念常常被使用到。
所谓深度优先，顾名思义，就是偏向于纵深，“一头扎到底” 的访问方式。可能这种说法有些抽象，下面就通过二叉树的前序遍历、中序遍历、后序遍历，来看一看深度优先是怎么回事吧。
前序遍历 Preorder Traversal (VLR)
二叉树的前序遍历，输出顺序是根节点、左子树、右子树。
顺序如上
 |  |  |
|---|---|---|
| 1 | 2 | 3 |
 |  |  |
| 4 | 5 | 6 |
- 首先输出的是根节点1。
- 由于根节点1存在左孩子，输出左孩子节点2。
- 由于节点2也存在左孩子，输出左孩子节点4
- 节点4既没有左孩子，也没有右孩子，那么回到节点2，输出节点2的右孩子节点5。
- 节点5既没有左孩子，也没有右孩子，那么回到节点1，输出节点1的右孩子节点3。
- 节点3没有左孩子，但是有右孩子，因此输出节点3的右孩子节点6。
到此为止，所有的节点都遍历输出完毕。
中序遍历 Inorder Traversal (LDR)
二叉树的中序遍历，输出顺序是左子树、根节点、右子树。
顺序如上
 |  |  |
|---|---|---|
| 1 | 2 | 3 |
 |  |  |
| 4 | 5 | 6 |
- 首先访问根节点的左孩子，如果这个左孩子还拥有左孩子，则继续深入访问下去，一直找到不再有左孩子的节点，并输出该节点。显然，第一个没有左孩子的 节点是节点4。
- 依照中序遍历的次序，接下来输出节点4的父节点2。
- 再输出节点2的右孩子节点5。
- 以节点2为根的左子树已经输出完毕，这时再输出整个二叉树的根节点1。
- 由于节点3没有左孩子，所以直接输出根节点1的右孩子节点3。
- 最后输出节点3的右孩子节点6。
后序遍历 Postorder Traversal (LRD)
二叉树的后序遍历，输出顺序是左子树、右子树、根节点。
上图就是一个二叉树的后序遍历，每个节点左侧的序号代表该节点的输出顺序。
广度优先遍历 bfs
深度遍历就像是上楼梯，每层楼有四个工作室，你一路之上，一头扎到顶，每一层其他工作室你都先不看，最后在回来挨个看。而层序遍历就是一层一层都看完在上去。这也就是层序遍历，顾名思义，就是二叉树按照从根节点到叶子节点的层次关系，一层一层横向遍历各个节点。
层序遍历
上图就是一个二叉树的层序遍历，每个节点左侧的序号代表该节点的输出顺序。
这里同样需要借助一个数据结构来辅助工作，这个数据结构就是队列
详细遍历步骤如下
 |  |  |
|---|---|---|
| 1 | 2 | 3 |
 |  |  |
| 4 | 5 | 6 |
- 根节点1进入队列。
- 节点1出队，输出节点1，并得到节点1的左孩子节点2、右孩子节点3。让节点2和节点3入队。
- 节点2出队，输出节点2，并得到节点2的左孩子节点4、右孩子节点5。让节点4和节点5入队。
- 节点3出队，输出节点3，并得到节点3的右孩子节点6。让节点6入队。
- 节点4出队，输出节点4，由于节点4没有孩子节点，所以没有新节点入队。
- 节点5出队，输出节点5，由于节点5同样没有孩子节点，所以没有新节点入队。
- 节点6出队，输出节点6，节点6没有孩子节点，没有新节点入队。
到此为止，所有的节点都遍历输出完毕。