「数据结构与算法」二叉树

数据结构
留言

树：树是一种非线性的数据结构，一棵树是n（n>=0）个节点的集合。
用来连接相邻节点之间的关系，我们叫做“父子关系”。
我们把没有父节点的节点叫做根节点，节点的上一层节点是其父节点，下一层节点是其子节点，拥有相同父节点的子节点之间互称为兄弟节点。

  • 树的三个比较相似的概念：高度（Height）、深度（Depth）、层（Level）。
    • 节点的高度：节点到叶子节点的最长路径（边数）
    • 节点的深度：根节点到这个节点所经历的路径（边数）
    • 节点的层数：节点的深度 +1
  • 树的高度：根节点的高度。

1. 二叉树

二叉树：每个节点最多有两个子节点，分别是左子节点和右子节点。
二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

  • 两个比较特殊的二叉树：
    • 满二叉树：树中每个分支节点（非叶节点）都有两棵非空子树，并且所有的叶节点都在同一层。
    • 完全二叉树：除最后一层外，其他层的节点都满；并且最后一层的节点从左到右是连续排列，中间没有断开，空位都在右边。

有两种方法存储一棵二叉树，一种是基于指针或者引用的二叉链式存储法，一种是基于数组的顺序存储法。

2. 存储二叉树

基于基于指针的链式存储法。
每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。
从根节点开始，就可以通过左右子节点的指针，把整棵树都串起来。这种存储方式我们比较常用。大部分二叉树代码都是通过这种结构来实现的。

基于数组的顺序存储法。
如下图，我们把根节点存储在数组下标 i=1 的位置，那左子节点存储在下标 2*i = 2 的位置，右子节点存储在 2*i+1 = 3 的位置。以此类推，B节点的左子节点存储在 2*i = 2*2 = 4 的位置，右子节点存储在 2*i+1 = 2*2+1 = 5 的位置。

如果节点X存储在数组中下标为 i 的位置，下标为 2*i 的位置存储的就是左子节点，下标为 2*i+1 的位置存储的就是右子节点。
反过来，下标为 i/2 的位置存储就是它的父节点。
通过这种方式，我们只要知道根节点存储的位置（通常根节点会存储在下标为1的位置），这样就可以通过下标计算，把整棵树都串起来。

堆其实就是一种完全二叉树，最常用的存储方式就是数组。

3. 遍历二叉树

经典的方法有三种，前序遍历、中序遍历和后序遍历。

  • 前序遍历：对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
  • 中序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
  • 后序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。

实际上，二叉树的前、中、后序遍历就是一个递归的过程。
比如，前序遍历，其实就是先打印根节点，然后再递归地打印左子树，最后递归地打印右子树。

4. 二叉查找树（Binary Search Tree）

二叉查找树，也叫二叉搜索树。
顾名思义，二叉查找树是为了实现快速查找而生的。不过，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值都比该节点的值小，而右子树节点的值都比该节点的值大。

4.1 二叉查找树的查找操作

先取根节点，如果它等于我们要查找的数据，那就返回。
如果要查找的数据比根节点的值小，那就在左子树中递归查找；
如果要查找的数据比根节点的值大，那就在右子树中递归查找。

4.2 二叉查找树的插入操作

二叉查找树的插入操作二叉查找树的插入过程有点类似查找操作。
新插入的数据一般都是在叶子节点上，所以我们只需要从根节点开始，依次比较要插入的数据和节点的大小关系。

4.3 二叉查找树的删除操作

分三种情况来处理。

  1. 如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为null。(比如图中的删除节点55。)
  2. 如果要删除的节点只有一个子节点，我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。(比如图中的删除节点13。)
  3. 如果要删除的节点有两个子节点，可以用后继节点或者前继节点替换删除节点，然后再删除掉替换节点。（比如图中的删除节点18。)
    • 后继节点：删除节点的右子树中的最小节点，即右子树中最左节点。
    • 前继节点：删除节点的左子树中最大节点，即左子树中最右节点。

4.2 二叉查找树的其他操作

  • 除了插入、删除、查找操作之外，二叉查找树中还可以支持快速地查找最大节点和最小节点、前驱节点和后继节点。
  • 中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 O(n)，非常高效。因此，二叉查找树也叫作二叉排序树。
  • 支持重复数据的二叉查找树
    1. 通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。
    2. 每个节点仍然只存储一个数据。新插入值相同的数据当作大于这个节点的值来处理。查找时，遇到值相同的节点不停止，而是继续在右子树中查找，直到遇到叶子节点才停止。这样就可以把键值等于要查找值的所有节点都找出来。删除时，也需要先查找到每个要删除的节点，依次删除。

5. 平衡二叉树

二叉查找树支持快速插入、删除、查找操作，各个操作的时间复杂度跟树的高度成正比，也就是O(height)，完全二叉树的高度height<=log2n；理想情况下，时间复杂度是O(logn)。
不过，二叉查找树在频繁的动态更新过程中，可能会出现树的高度远大于log2n的情况，从而导致各个操作的效率下降。极端情况下，二叉树会退化为链表，时间复杂度会退化到O(n)。

为了解决二叉查找树因为动态更新导致的性能退化问题，发明了平衡二叉查找树这类数据结构。
平衡二叉查找树的高度接近logn，所以插入、删除、查找操作的时间复杂度也比较稳定，是O(logn)。
在工程中，很多用到平衡二叉查找树的地方都会用红黑树。红黑树是一种特殊的平衡二叉查找树。

平衡二叉树的严格定义：**二叉树中任意一个节点的左右子树的高度相差不能大于1**。

从这个定义来看，完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。

但是很多平衡二叉查找树其实并没有符合严格的定义，比如红黑树，它从根节点到各个叶子节点的最长路径，有可能会比最短路径大一倍。

所以，平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。