二叉树、 树、森林基本概念和性质

  • 二叉树总节点个数

    • $n = n_0 + n_1 + n_2$
    • $总分支数 + 1$
      • 分支 $n_2$ 即度为 $2$ 两个分支， $n_1$ 度为 $1$ ，衍生： $2n_2 + n_1 + 1$

  • 满二叉树节点个数： $2^n - 1$

  • 某层最大节点数：$2^{(n - 1)}$

  • 叶子节点数 $n_0 = n_2 + 1$

  • 完全二叉树深度：$\left \lfloor log_2n \right \rfloor + 1$

  • 二叉树遍历相关算法：

    • 中序遍历非递归算法
    • 二叉树的层次遍历
    • 二叉树的建立
    • 复制二叉树
    • 计算二叉树深度
    • 计算二叉树节点总数
    • 计算二叉树叶子节点个数
    • 线索二叉树的创建

  • 树

    • 树的存储结构
      • 数组配合链表进行存储
        • 双亲表示法
        • 孩子表示法
        • 结合上两种表示法 –> 带孩子的双亲链表表示法
      • 二叉链表示法
        • 孩子兄弟表示法

  • 树的遍历

    • 先、后序遍历
    • 层次遍历

  • 森林

    将森林看成三个部分：

    1. 森林中第一棵树的根节点
    2. 森林中第一棵树的子树森林
    3. 森林中的其他树构成的森林

  • 森林的遍历

    • 先序遍历，即遍历顺序为：$1 \to 2 \to 3$
    • 中序遍历，遍历顺序为：$2 \to 1 \to 3$
    • 后序遍历，遍历顺序为：$3 \to 2 \to 1$

  • 树与二叉树的相互转换

    • 树 $\to$ 二叉树：
      • 兄弟相连留长子
    • 二叉树 $\to$ 树：
      • 左孩右右连双亲，去掉原来右孩线

  • 森林和二叉树的相互转换

    • 森林 $\to$ 二叉树
    • 树变二叉根相连
    • 二叉树 $\to$ 森林
      • 去掉全部右孩线，孤立二叉再还原

树表的查找

  • 二叉排序树（二叉搜索树、二叉查找树）

    • 有以下性质
      • 左子树的值小于根节点
      • 右子树的值大于或等于根节点
      • 子树也是二叉排序树
    • 中序遍历非空二叉排序树得到的序列是单调递增的
    • 二叉排序树查找某关键字时 $比较关键字次数 = 此节点所在层次$ ，$最多比较次数 = 树的深度$
    • 二叉排序树平均查找长度和树的形态有关
      • 最优的情况（形态均衡）：$O(log_2n)$
      • 最坏的情况（即单支树）：$O(n)$
    • 我们可以对二叉排序树做平衡化处理，得到一棵平衡二叉树
    • 二叉排序树的删除操作
      • 将因删除的节点断开，二叉树链表重新链接起来
      • 防止重新链接后导致树的高度增加
        • 删除的是叶子节点 $\to$ 直接将指向该叶子节点的指针设置位 $null$ 即可
        • 删除的节点只有左子树（或右子树） $\to$ 将指向该节点的指针指向节点的左子树（或右子树）
        • 删除的节点即有左子树又有右子树
          • 直接将被删除节点与所在根节点的子树最大值节点，数值替换，在将那个最大值节点删去（删去此节点同样按照具体情况删除）
          • 也可以用后继替换值，然后再删除该后继节点（后继节点中值最小的节点）

  • 平衡二叉树（Adelson-Velskii and Landis)

    • 有以下性质的二叉排序树

      • 左右子树高度差的绝对值 小于等于 1
      • 左右子树也是平衡二叉排序树

    • 平衡调整的四种类型

      • $LL型:$ 插入的节点位于失衡节点的左子树的左子树上
      • $LR型:$ 插入的节点位于失衡节点的左子树的右子树上
      • $RL型:$ 插入的节点位于失衡节点的右子树的左子树上
      • $RR型:$ 插入的节点位于失衡节点的右子树的右子树上

    • 调整原则

      1. 降低树高度
      2. 保持二叉排序树性质

散列表的查找

  • 关于散列表术语

    • 散列方法（杂凑法）
      • 选取某个函数按关键字计算元素的存储位置，将其位置返回后将元素存放在此位置
      • 查找时，还是由此函数来根据关键字计数位置信息，之后将其与地址单元的关键码进行比较，确定查找是否成功
    • 散列函数：散列方法中使用的转换函数
      • 直接定址法
      • 数字分析法
      • 平方取中法
      • 折叠法
      • 除留取余法
      • 随机数法
    • 散列表：按上述方法存取元素所构造的表
    • 冲突：不同的关键码映射到同一个散列地址
      • 处理冲突的方法：
        • 开放地址法（开地址法）
        • 链地址法（拉链法）
        • 再散列法（双散列函数法）
        • 建立一个公共溢出区
    • 同义词：通过散列函数计算出相同的函数值的关键字被称为同义词

  • 根据散列函数直接查找到数据对应位置

    • 优点：查找效率高，时间复杂度为：$O(1)$
    • 缺点：空间效率低，空间复杂度为：

  • 散列表的技术具有很好的平均性能，优于一些传统的技术

  • 链地址法优于开放地址法（动态空间，不会冲突，无聚集现象）

  • 除留余数法作为散列函数优于其他类型函数（取 $质数\lem$）