在树的结构中，树的定义如下。
树（tree）是n（n>=0）个节点的有限集，当n=0时，称为空树。在任意一个非空树中，有如下特点：
1、有且仅有一个特定的称为根的节点。
2、当n>1时，其余节点可分为m(m>0)个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。
【相关节点】
树的最大层级树，被称为树的高度或深度。
树的每个节点最多有2个孩子节点。
树的一种特殊形式。树的每个节点 最多有2个孩子节点 。
二叉树的两个孩子节点，一个被称为 左孩子 ，一个被称为 右孩子 。这两个孩子节点的顺序是固定的。
二叉树有两种特殊形式：满二叉树、完全二叉树。
满二叉树 ：一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层接上。简言之，满二叉树的每一个分支都是满的。
完全二叉树 ：对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。
一棵树，若为满二叉树，那么一定是完全二叉树。反之，不一定。
在内存中存储 ：
为什么这么设计？可以更方便的定位孩子节点、父节点。
若父节点的下标是parent，那么左孩子节点下标是2 parent+1，右孩子节点下标是2 parent+2。
反之，若左孩子节点下标是leftChild,那么父节点下标是(leftChild - 1)/2。
稀疏二叉树，用数组表示会很浪费空间。
二叉树的应用：查找操作、维持相对顺序。
1、查找
二叉查找树在二叉树的基础上增加了以下几个条件：
如果左子树不为空，则左子树上所有节点的值均小于根节点的值；
如果右子树不为空，则右子树上所有节点的值均大于根节点的值；
左、右子树也都是二叉查找树。
对于一个节点分布相对均衡的二叉查找树来说，如果节点总数是n，那么搜索节点的 时间复杂度都是O(logn) ，和树的深度是一样的。
2、维持相对顺序（插入）
二叉查找树的特性保证了二叉树的有序性，因此还有另外一个名字：二叉排序树。
插入的过程中，可能会出现需要二叉树进行自平衡，例如下图的情况：
如图所示，不只是树的外观看起来怪异，查询节点的时间复杂度也退化成了O(n)。
二叉树的自平衡的方式有很多种，如红黑树、AVL树、树堆等。
二叉树的遍历：
从节点之间位置关系的角度：
* 前序遍历：输出顺序：根节点、左子树、右子树
* 中序遍历：输出顺序：左子树、根节点、右子树
* 后序遍历：输出顺序：左子树、右子树、根节点
* 层序遍历：按照从根节点到叶子节点的层级关系，一层一层横向遍历各个节点。
从更宏观的角度:
* 深度优先遍历(前、中、后序遍历，前中后是相对根节点)
* 广度优先遍历(层序遍历)
二叉堆：本质上是一种完全二叉树。
二叉堆本质上是一种完全二叉树，分为2个类型：
最大堆 ：任何一个父节点的值，都大于或等于它左、右孩子节点的值；
最小堆 ：任何一个父节点的值，都小于或等于它左、右孩子节点的值。
二叉堆的根节点，叫作 堆顶 。最大堆的堆顶是整个堆中最大元素，最小堆的堆顶是整个堆中最小元素。
二叉堆虽然是一个完全二叉树，但它的存储方式并不是链式存储，而是顺序存储，如下图所示：
假设父节点的下标是parent，那么它的左孩子的下标就是 2 * parent + 1 ，右孩子的下标就是 2 * parent + 2 。
二叉堆的3种操作（假设是最小堆）：
1、插入节点：时间复杂度O(logn)
插入节点是通过“上浮”操作完成的：当二叉堆插入节点时，插入位置是完全二叉树的最后一个位置，将该节点与它的父节点进行比较，如果该节点小于它的父节点，那么该与它的父节点交换位置，直到比较到堆顶位置。
2、删除节点：时间复杂度O(logn)
删除节点是通过“下沉”操作完成的：将要删除的节点看作是堆顶，只看该节点及它下面的部分。因为堆顶元素要进行删除，将最后一个节点元素替换堆顶元素，将替换后的元素与它的左、右子树进行比较，如果左、右孩子节点中最小的一个比该节点小，那么该节点“下沉”，直到叶子节点。
3、构建二叉堆：时间复杂度O(n)
构建二叉堆，也就是把一个无序的完全二叉树调整为二叉堆，本质就是让所有非叶子节点一次“下沉”。
优先队列不再遵循先入先出的原则，而是分为两种情况：
最大优先队列 ，无论入队顺序如何，都是当前最大的元素优先出队；
最小优先队列 ，无论入队顺序如何，都是当前最小的元素优先出队。
二叉堆节点的“上浮”和“下沉”的时间复杂度都是O(logn)，所以优先队列入队和出队的时间复杂度也是O(logn)。
https://blog.csdn.net/qq_28958301/article/details/91590545