1 树的基础知识

  • 节点的高度:节点到叶子结点的边数
  • 节点的深度:跟节点到这个节点经历的边数
  • 节点的层数:节点的深度 + 1
  • 树的高度:根节点的高度

2 二叉树的分类

一般比较常用的就是二叉树,二叉树可以粗略的分为满二叉树和完全二叉树

2.1 完全二叉树的特性

一般存储一棵二叉树有两种方式,一是基于指针的二叉链式存储法,另外一种是基于数组的顺序存储法,链式存储比较好理解,这里只记录基于数组的顺序存储法。下图展示的就是如果用数组来保存。

基于数组的顺序存储法

可以发现,当使用数组保存的时候,如果数组的第一位为 1 开始保存的话,那么下标为 2 * i 的位置存储的就是左子节点,下标为 2 * i + 1 的地方就是右子节点。

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

3 二叉树的遍历

遍历方式分为前序、中序、后序和层序四种方式

4 二叉查找树

二叉查找树在二叉树的基础上补充了一条定义,即选取树中任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,而右子树中每个节点的值都要大于这个节点

4.1 二叉查找树的查找操作和插入操作

这两个操作比较简单,纯粹的比较,当比较满足条件的时候执行返回结果或是新建节点的操作

4.2 二叉查找树的删除操作

二叉树的删除操作需要分为三种情况来处理

  1. 第一种情况,如果要删除的节点没有子节点,我们只需要直接将父节点的指针置为 null
  2. 第二种情况,如果要删除的节点只有一个子节点,我们只需要将父节点原来指向要删除节点的指针指向这个子节点即可
  3. 第三种情况,如果要删除的节点有两个子节点,这个时候我们需要找到这个节点的右子树中的最小节点,然后把它替换到要删除的节点上,然后再把这个最小节点删除,因为这个最小节点肯定没有左节点(如果有,那他就不是最小节点了)。

4.3 二叉查找树的特性

  1. 中序遍历能够输出有序数列,并且时间复杂度只有 O(n)

4.4 二叉查找树如何支持重复数据

当需要存储重复的数据的时候,有两种方式存储

  1. 第一个方法,将节点内部存储数据的数据结构改成链表或者数组,这样就可以存储多个重复数据了
  2. 第二个方法,每个节点仍然只存储一个数据,插入时碰到节点的值相同,就将这个要插入的数据放到这个节点的右子树,也就是说,将这个新插入的数据当作大于这个节点的值来处理。
    • 这样改造之后对于查找和删除都要做相应的修改,查找的时候在找到这个值之后还要继续在右子树中寻找,删除同理

4.5 二叉树的时间复杂度分析

先看以下三棵树

三棵树

对于树的增删查操作都和树的高度有关,对于完全二叉树的高度小于等于 \(log_2n\),所以树的各种操作是 O(logn),但是当树退化成链表结构的时候,时间复杂度就变成 O(n) 了。

4.6 为什么不使用散列表而使用二叉树

  1. 第一,散列表中的数据是无需存储的,如果要输出有序的数据,需要先进行排序,对于二叉查找树来树,只需要中序遍历,就可以在 O(n) 的时间复杂度内输出有序的数据序列。
  2. 第二,散列表扩容耗时很多,而且当遇到散列冲突时,性能不稳定,尽管二叉查找树的性能不稳定,但是在工程中,我们最常用的平衡二叉查找树的性能非常稳定,时间复杂度稳定在 O(logn)
  3. 第三,笼统的说,尽管散列表的查找等操作的时间复杂度是常数级的,但因为哈希冲突的存在,这个常量不一定比 logn 小,所以实际的查找速度可能不一定比 O(logn) 块。加上哈希函数的耗时,也不一定就比平衡二叉树的效率高。
  4. 散列表的构造比二叉查找树要复杂,因为考虑的东西很多,比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡型这一个问题,而且增额问题的解决方案比较成熟、固定。