删除|字节算法大神熬了三个通宵整理的数据结构与算法笔记（万字长文）( 五 )

数组中为空的位置就很多，这样会浪费很多存储空间。
二叉树的遍历
二叉的遍历就是循环打印出二叉树中的所有节点。经典的方法有三种，分别为：前序遍历、中序遍历和后序遍历。其中的前、中、后指的是节点与它的左右子节点遍历打印的先后顺序，即：
1. 前序遍历：本节点 --> 左子节点 --> 右子节点；
2. 中序遍历：左子节点 --> 本节点 --> 右子节点；
3. 后序遍历：左子节点 --> 右子节点 --> 本节点。
可以看到，前、中、后就是本节点在遍历中的顺序。示意图：

二叉查找树
二叉查找树（Binary Search Tree）是二叉树中最常用的一种类型，又称「二叉搜索树」，它支持快速查找、插入、删除一个数据。
结构特点
二叉树中的任一节点，其左子树中每个节点的值，都小于该节点的值；右子树中每个节点的值都大于该节点的值。示意图：

查找
查找步骤：
1. 先将要查找元素的值与根节点的值比较，若相等则返回；
2. 若小于根节点的值，则在左子树中递归查找；
3. 若大于根节点的值，则在右子树中递归查找。
查找过程示意图：

插入
插入过程与查找的比较过程有些类似，操作示意图如下：

删除
相比查找和插入，删除过程略微复杂一些。主要分为三种情况：
1. 待删除的节点无子节点：直接删除（下图的节点55）；
2. 待删除的节点有一个子节点：将待删除节点的父节点指向待删除节点的子节点（下图的节点13）；
3. 待删除的结点有两个子节点：需要先找到待删除节点的右子树中的最小节点，用它替换要删除的节点，然后再删除该最小节点（下图的节点18）。
这三种情况的删除操作示意图如下：

二叉树&散列表
1. 散列表中的数据是无序的；二叉查找树中序遍历可在O(n)时间复杂度内输出有序的数据序列；
2. 散列表的扩容比较耗时，散列冲突时性能不稳定；平衡二叉查找树的性能稳定在O(logn)；
3. 散列表构造比二叉树复杂不少（散列函数设计、冲突解决、扩容等）；二叉树只需考虑平衡性问题，且解决方案比较成熟、固定。
堆
堆（Heap）是一种特殊的树，它满足以下结构特征：
1.堆是一个完全二叉树；
2.堆中每个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
其中，每个节点值都大于等于子树中每个节点值的堆称为「大顶堆」，小于等于树中每个节点值的堆称为「小顶堆」。示意图：

其中 1、2 为大顶堆， 3 为小顶堆， 4 不是堆（不是完全二叉树）。
存储
前面分析了二叉树的存储方法有两种：链式存储和顺序存储，而顺序存储比较适合完全二叉树。堆的顺序存储示例如下：

堆化
当向堆中插入元素、或从堆中删除元素时，可能会导致堆不满足其结构特点。因此需要对其进行调整使其重新满足堆的特性，该过程称为堆化（heapify）。
堆化有两种方式：从下往上和从上往下。
从下往上堆化示意图（插入节点22）：

从上往下堆化示意图（删除节点33）：

注意：这样操作会使堆不满足完全二叉树的特性。
如果转换思路，把最后一个节点放到堆顶，然后再进行从上到下堆化，如图所示：

这样就不会出现“数组空洞” ，又能满足完全二叉树的特性。
应用场景
堆的几个非常重要的应用场景：优先级队列、Top K问题、求中位数。
小结
1. 数据结构中的树可以类比生活中常见的树倒过来。其中二叉树最常用，二叉树有两种特殊的情况：满二叉树和完全二叉树；