5.1 二叉树的概念

  • 二叉树（binary tree）由结点的有限集合构成：
    • 或者为空集（NIL）
    • 或者由一个根结点及两棵不相交的分别称作左子树和右子树的二叉树组成（递归定义）
  • 相关概念
    • 父母（parent）
    • 子女（孩子） children
    • 边 edge
    • 兄弟 sibling
    • 路径 path
    • 祖先 ancestor
    • 子孙 descendant
    • 树叶 leaf
    • 内部节点或分支节点 internal node
    • 度数 degree
    • 层数 level
  • 满二叉树：结点或为树叶或为两棵非空子树
  • 完全二叉树
    • 只有下面的两层结点度数可以小于2
    • 最下面一层的结点都集中在该层最左边、连续的位置上
    • 性质：路径长度和最短
  • 扩充二叉树：当二叉树结点出现空指针（不是连接两片树叶的节点），进行扩充，把该节点扩充到连接两个树叶

5.2 二叉树的周游

  • 抽象数据类型ADT
  • 遍历（traversal），也称“周游”
    • 二叉树的线性化
      • 深度优先
      • 广度优先
    • 前序周游
    • 中序周游
    • 后序周游
    • 周游的遍历非递归算法（压栈）：
      • 复杂性分析：时间代价为O（n）,每个结点都被访问且只被访问一次
      • 栈深：与树的高度有关（深度搜索）
    • 广度优先遍历二叉树
      • 自上而下，从左到右
      • 队列实现，每次都处理队列的top，同时top的左右子树进队列

示例代码：二叉树节点定义 (C++)

template <typename T>
struct TreeNode {
    T value;
    TreeNode* left;
    TreeNode* right;

    TreeNode(T val) : value(val), left(nullptr), right(nullptr) {}
};

示例代码：前序遍历递归实现 (C++)

void preOrder(TreeNode<int>* root) {
    if (root == nullptr) {
        return;
    }
    // 访问根节点
    std::cout << root->value << " ";
    // 递归遍历左子树
    preOrder(root->left);
    // 递归遍历右子树
    preOrder(root->right);
}

5.3 二叉树的存储结构

  • 动态存储结构
    • 链式存储
      • 结点之间关系用指针表示
      • 二叉链表：left-info-right
        • 遍历查找父节点
      • 三叉链表：提供“向上”访问的能力
  • 静态存储结构
    • 顺序存储（完全二叉树）
      • 运用广度遍历排序
      • 下标公式
        • 子女结点：
          • 左子女：2i+1
          • 右子女: 2i+2
        • 父母结点：
          • [(i-1)/2]
        • 兄弟结点：
          • 偶数在右，奇数在左（因为根节点是0）

5.4 二叉搜索树（BST）

  • 二叉搜索树，也称二叉排序树
    • 是空树
    • 或者是
      • 一个结点K的左子树任意结点均小于K，右子树任意节点均大于K
      • 左右子树也分别为二叉搜索树
    • 性质
      • 按照中序周游打印，由小到大排列
      • 树中结点的值唯一
  • 二叉搜索树的搜索过程
    • 效率：只需检索二个子树之一
  • 二叉搜索树的插入过程
    • 小于进入左子树，大于进入右子树，相等返回
    • 遇到空指针时插入
  • 二叉搜索树的建立
    • 输入元素的次序会影响二叉树的平衡
  • 二叉树的删除
    • 无改进（会失衡）
      • 如果没有左子树
        • 直接用右子树的根代替被删除节点
      • 如果有左子树
        • 在左子树中找到按中序周游的最后一个结点，将右子树的根赋到此节点的右指针
        • 左子树的根取代被删除节点
    • 改进
      • 如果没有左子树
        • 直接用右子树的根代替被删除节点
      • 如果有左子树
        • 在左子树中找到按中序周游的最后一个结点，将该结点的左子树的根赋到自己处，该结点取代被删除节点

5.5 堆与优先队列

  • 堆的定义及其实现
    • 数据局部有序
      • 结点与其子女值之间存在大小比较关系
      • 两种堆（最大、最小）
      • 兄弟之间没有限定大小关系
    • 堆不唯一
    • 可以用数组表示的完全二叉树
    • 建堆：从堆的最后一个分支节点开始，自底向上，自右向左，逐步把以各分支结点为根的子树调整成堆
  • 优先队列
    • 一个集合，每个元素有一个关键码值，执行查找、插入和删除操作
    • 特点：从一个集合中快速地查找并移出具有最大值或最小值的元素
    • 堆是优先队列的一种自然的实现方法

5.6 Huffman树及其应用

  • 计算机二进制编码
    • ASCII码，中文编码等
  • 等长编码
    • 假设所有编码都等长，表示n个不同的字符需要log~k~^n^位
    • 字符的使用频率相等
  • 频率不等的字符，可以利用字符的出现来编码
    • 经常出现的字符的编码较短，不常出现的字符编码较长
  • 带权外部路径长度：二叉树叶结点带权外部路径长度总和
  • 哈夫曼（Huffman）树或称最优二叉树：具有最小带权路径长度的二叉树
  • 哈夫曼树的建立：
    • 将字母按照权重排序
    • 将最小的两个作为一个分支结点的两个子女，结点的权为两树叶的权之和，将结点的“权”放回序列当中的适当位置，使“权”的顺序保持
    • 重复上述步骤直至序列中剩一个元素，则Huffman树建立完毕
  • 哈夫曼编码：
    • 用d~0~,d~1~,…,d~n-1~作为外部结点构造具有最小带权外部路径长度的扩充二叉树
    • 把从每个结点引向其左子结点的边标上号码0，引向右子结点的边标上号码1

    • 从根结点到每个叶结点路径上的编号0 or 1连接起来，就是这个外部结点所代表字符的编码，得到的二进制前缀码就称作Huffman编码

    • 性质：
      • 不等长编码，编码长度取决于字符权重（使用相对频率）
      • 任何一个字符的编码都不是另一个字符编码的前缀，保证了代码串被反编码的时候，不会有多种可能
    • 译码：
      • 从二叉树的根开始，把二进制编码每一位的值与Huffman树边上标记的01相匹配，确定选择左分支还是右分支，直至确定一条到达树叶的路径