树与二叉树知识导图

本图梳理了数据结构中树与二叉树的内容，包括树的基本概念、二叉树、树和森林、哈夫曼树和哈夫曼编码等，适用于考试复习！

树与二叉树

• 树的基本概念
  • 树的定义
    • 树是n个节点的有限集
  • 基本术语
    • 结点（根节点、双亲结点、兄弟节点、子结点、叶子结点）
    • 子树、空树
    • 度、层次
  • 表示方法
• 二叉树
  • 定义
    • 一种树形结构，每个结点至多只有两棵子树
  • 特殊二叉树
    • 满二叉树
    • 完全二叉树
  • 二叉树的性质
    • 非空二叉树上的叶子结点等于度为2的结点数+1，即n0=n2+1
    • 非空二叉树上第k层上至多有2^(k-1)个结点
    • 高度为h的二叉树至多有2^h-1个结点
    • 完全二叉树的性质
      • 结点i的双亲的编号为[i/2],向下取整
      • 当2i<=n时，结点i的左孩子编号为2i，当2i+1<=i时，i的右孩子编号为2i+1
      • 结点i所在深度为 [log2(i)]+1,向下取整
      • 具有n个结点的完全二叉树的高度为 [log2(n)]+1,向下取整
  • 二叉树的存储结构
    • 顺序存储结构
    • 链式存储结构
      • 在含有n个结点的二叉链表中，含有n+1个空链域
  • 二叉树的遍历
    • 递归算法
      • 先序遍历
        • 访问根结点，先序遍历左子树，先序遍历右子树
      • 中序遍历
        • 中序遍历左子树，访问根结点，中序遍历右子树
      • 后序遍历
        • 后序遍历左子树，后序遍历右子树，访问根结点
    • 非递归算法
      • 借助栈
    • 层次遍历
      • 借助队列
    • 由遍历序列构造二叉树
      • 先序序列和中序序列，可以唯一地确定一棵二叉树
      • 后序序列和中序序列
      • 层次序列和中序序列
      • 若只知道先序和后序，无法唯一确定
  • 线索二叉树
    • 概念
      • 将二叉链表中的空指针改为指向前驱或后继的线索。若无左子树，则令lchild指向前驱结点；若无右子树，则令rchild指向后继结点。
    • 中序线索二叉树的构造
      • p143
    • 中序线索二叉树的遍历
      • p144
• 树和森林
  • 树的存储结构
    • 双亲表示法
      • 采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置
      • 区别树的顺序存储结构和二叉树的顺序存储结构
    • 孩子表示法
      • 将每个结点的孩子结点都用单链表连接起来，此时n个结点就有n个孩子链表（叶子结点为空表
    • 孩子兄弟表示法
      • 又称二叉树表示法，即以二叉链表作为树的存储结构
      • 每个结点包括三部分：结点值、指向第一个孩子结点的指针，指向下一个兄弟结点的指针
  • 树、森林、二叉树的转换
  • 树和森林的遍历
• 哈夫曼树和哈夫曼编码
  • 定义
    • 带权路径长度：从树的根到任意结点的路径长度与该节点上权值的乘积
    • 在含有n个带权叶结点的二叉树中，其中带权路径WPL最小的二叉树成为哈夫曼树
  • 构造
    • 选权值最小的树作为新节点的左右子树
  • 编码
    • 可将字符的编码解释为从根至该字符的路径上边标记的序列
• 20301121 肖若诗