数据结构学习笔记 - 二叉树_完全二叉树的时间复杂度2n方

二叉树

简介

树, 非线性表结构
树有三个概念:
高度从下向上数, 起点是0
深度从上向下数, 起点是0
层数从上向下数, 起点是1

二叉树

每个节点最多两个叉
有两种特殊二叉树:
满二叉树, 除了叶子节点, 每个节点都有左右两个子节点
完全二叉树, 叶子节点都在最底下两层, 最后一层叶子节点都靠左排列, 且除了最后一层, 其它层节点个数都达到最大
满二叉树是完全二叉树的一种特殊情况

存储二叉树

1. 基于指针的二叉链式存储法
   每个节点三个字段, 一个存数据, 另外两个存左右子节点的指针, 这种方式比较常用, 大部分二叉树代码都是通过这种结构来实现的
2. 基于数组的顺序存储法
   把根节点存储在i=1的位置, 左子节点存在2i的位置, 右子节点存储在2i+1的位置, 以此类推
   此种存储方式, 是完全二叉树的话, 只浪费一个下标0的存储位置, 非完全二叉树的话, 会浪费更多的数组存储空间

所以一个树是完全二叉树的话, 用数组存储是最节省内存的一种方式, 也是为什么完全二叉树被单拎出来说明的原因.
堆其实就是一种完全二叉树, 最常用的存储方式就是数组

二叉树的遍历

如何打印所有节点, 经典方法有三种:
前序遍历, 对于树中的任意节点来说, 先打印这个节点, 再打印左子树, 最后打印右子树 (todo)
中序遍历, 对于树中的任意节点来说, 先打印左子树, 再打印本身, 最后打印右子树 (todo)
后序遍历, 对于树中的任意节点来说, 先打印左子树, 再打印右子树, 最后打印它本身 (todo)
实际上二叉树的三种遍历, 就是一个递归的过程
遍历的时间复杂度是O(n)
不常用的遍历, 按层遍历 (todo)

二叉查找树

也叫二叉搜索树
特点, 支持动态数据集合的快速插入删除, 查找操作
二叉查找树要求, 在树的任意一个节点, 其左子树中的每个节点的值, 都要小于这个节点的值, 而右子树节点的值, 都大于这个节点的值

1. 查找操作
   先取根节点, 等于就返回, 比根节点小就在左子树递归查找, 比根节点大就在右子树递归查找
2. 插入操作
   新插入的数据一般在叶子节点上, 类似查找操作, 从根节点开始比较, 如果要插入数据比节点大, 并且节点的右子树为空, 则直接插到右子节点位置, 如果不为空, 再递归遍历右子树找位置, 如果数据比节点小, 同理遍历左子树查找位置
3. 删除操作
   相对复杂, 分为三种情况
   第一种, 要删除节点没有子节点, 直接将父节点指针置为null
   第二种, 要删除节点有一个子节点, 更新父节点指针指向要删除节点的子节点
   第三种, 要删除的节点有两个子节点, 需要找到右子树中的最小节点, 替换到要删除的节点上, 然后删除掉这个最小节点
4. 其他操作
   二叉查找树还支持快速的查找最大节点和最小节点, 前驱节点和后继节点
   重要特性, 中序遍历二叉查找树, 可以输出有序的数据序列, 时间复杂度O(n), 非常高效

支持重复数据的二叉查找树

• 第一种, 二叉查找树中每个节点不只存一个数据, 借助链表和支持动态扩容的数组等数据结构, 把值相同的数据存在同一个节点上
• 第二种, 每个节点仍然只存储一个数据, 插入时, 遇到值相同的节点, 就插入到这个节点的右子树, 也就是把这个数当作大于这个节点处理
  查找数据时, 遇到值相同的节点不停下, 继续在右子树查找, 直到遇到叶子节点, 就可以把所有值相等的节点找出来
  删除操作同理

二叉查找树的时间复杂度

不同形态的二叉查找树时间复杂度不同, 时间复杂度和树的高度成正比, 也就是O(height)