数据结构·树与二叉树

树的基本概念

树的定义

基本术语

• 祖先
• 子孙
• 双亲
• 孩子
• 兄弟
• 结点的度
• 树的度
• 分支结点（非终端结点）
• 叶结点（终端结点）
• 堂兄弟
• 深度
• 高度
• 树的高度（深度）
• 有序树
• 无序树
• 路径（只能从上往下！！）
• 路径长度（边的个数）
• ❗树的路径长度（根结点到每个叶结点路径长的和）
• 森林

树的性质

二叉树的概念

二叉树的定义及其主要特征

• 二叉树的定义
• 几个特殊的二叉树
  • 满二叉树
  • 完全二叉树
  • 二叉排序树
  • 平衡二叉树
• 二叉树的性质

二叉树的存储结构

• 顺序存储结构（注意下标）
• 链式存储结构
  • ⭐含有n个结点的二叉链表中，含有n+1个空链域

二叉树的性质

• 非空二叉树上的叶结点数等于度为2的结点数加1
• …
• 具有n个（n>0）结点的完全二叉树的高度为$ceil(\log_2(n+1))或floor(\log_2n)+1$.

二叉树的遍历和线索二叉树

二叉树的遍历

• 先序遍历
• 中序遍历
• 后序遍历
• 递归算法和非递归算法的转换
• 层序遍历
• 由遍历序列构造二叉树

线索二叉树

• 基本概念
• 构造

树、森林

树的存储结构

• 双亲表示法（顺序存储+双亲序号）
• 孩子表示法（每个结点牵着孩子们）
• 孩子兄弟表示法

树、森林与二叉树的转换

树和森林的遍历

• 先根遍历（与对应二叉树先序遍历相同）
• 后根遍历（与对应二叉树中序遍历相同）
• 森林的遍历应直接理解为对应二叉树的遍历

树与二叉树的应用

哈夫曼树和哈夫曼编码

• 哈夫曼树的定义
  • 结点的权
  • 结点的带权路径长度
    • 根结点到某叶结点路径长度（边数）与该叶结点权值的乘积
  • 树的带权路径长度（WPL）
    • 单独WPL表示树的带权路径长度
  • 哈夫曼树（最优二叉树）（WPL最小）
• 哈夫曼树的构造
  • 算法
  • 哈夫曼树的特点
    • 结点总数为2n-1
    • 不存在度为1的结点
• 哈夫曼编码

并查集

• 逻辑结构
  • 元素之间为“集合关系”
• 基本操作
  • 初始化
  • Find
  • Union
• 存储结构
  • 双亲…
• 优化
  • 用根结点绝对值表示结点总数
  • 小树并大树
  • *Find操作的究极优化：路径压缩