第六章：树

这是一个关于第六章：树的思维导图，涵盖了树的基本概念、二叉树以及森林和哈夫曼树等相关知识，适合用于课程学习、复习备考等场景。

第六章树

• 大题： 题型一：树，森林和二叉树的互相转化。 ①由树构造二叉树／将二叉树转化为树 ②由森林构造二叉树／将二叉树转化为森林 ③由遍历序列构二叉树／写二叉树的遍历序列 题型二：树，森林和二叉树的遍历。 ①树的遍历。 ②森林的遍历。 ③二叉树的遍历。 题型三：哈夫曼树和哈夫曼编码。 ①构造哈夫曼树。 ②写出哈夫曼编码。
• 二叉树
  • 用二叉树求表达式是中跟遍历
  • 1、二叉树的概念
    • ①二叉树是递归定义的数据结构。
    • ②二叉树是n个结点的集合。
    • ③二叉树的每个结点最多有两颗子树，即二叉树里任意结点的度≤2，允许不出现度＝2的结点。
    • ④二叉树是有序树，即结点从上到下从左往右是有序的，每个结点有左右子树之分，左右子树有左右孩子之分，不能颠倒。
  • 2、二叉树的存储结构
    • 顺序存储结构
      • 定义
        • 按照自上到下，从左到右编号，用一组地址连续的存储单元来存储二叉树的结点。
      • 存储步骤
        • ①（画满）首先画出一个与已知的二叉树同深度的满二叉树。
        • ②（标满）将满二叉树中的结点按从上到下从左往右进行编号。
        • ③（标二）根据编好号的满二叉树中各结点的位置，给已知的二叉树中对应的结点编号。
        • ④（存储）按照结点在二叉树中对应的位置，将其存储在一维数组的相应位置。（一维数组下标从一开始就行）
        • ⑤（存0）已知的二叉树对应同高度的满二叉树中不存在的结点，其相应数组中置为零。
      • 优点
        • 结点之间的关系，通过下标计算即可得到，因此容易访问结点i的双亲，左右孩子。
      • 缺点
        • 顺序存储比较适合于存储完全二叉树，但是对于一般的二叉树，其存储效率不高。特别的：当对于深度为h的右单支树，需长度为2h次的数组来存储，而且数组中仅有h个非零元。
    • 链式存储结构
      • 定义
        • 用二叉链表来存储一颗二叉树
      • 特点
        • ①定义一个二叉链表：Bitree T；
          • 二叉链表的根指针（头指针）T指向根结点。
        • ②每个结点含有两个指针区域。
          • 有n个结点，则有2n个指针域。
          • 有n个结点，则有n+1个空指针域。
          • 有n个结点，则有n-1个非空指针域（结点的头上连有指针域）。
        • ③每个结包含三个区域。
          • 左指针域：lchild
          • 右指针域：rchlid
          • 数据域：data
  • 3、二叉树的类型
    • 一般二叉树
      • 概念
        • 如果对满二叉树的结点按自上而下，从左到右的顺序进行编号，对一个深度为h有n个结点的二叉树，如果它与深度为h的满二叉树的前n个结点分布不一定相同，则称之为一般二叉树。
      • 特点
        • ①属于二叉树
        • ②从左到右，从上往下结点不一定连续。
    • 满二叉树
      • 概念
      • 特点
        • ①只有最后一层有叶子结点。
        • ②没有度为1的结点。
        • ③除了叶子结点，其余都是度为2的结点。
        • ④满二叉树不一定是哈夫曼树（WPL值不一定是最小）
        • ⑤满二叉树一定是完全二叉树
    • 完全二叉树
      • 概念
        • 如果将其与同深度的按自上而下，从左到右的顺序进行编号的满二叉树进行比较，它与此满二叉树的前n个结点分布相同，则称之为完全二叉树。
      • 特点
        • ①属于二叉树。
        • ②从左到右，从上往下结点连续。
      • 性质
        • 1、深度为h，则前h-1层已满。
        • 2、最后一层：最后一层叶子结点从从最左边开始，连续排列，没有间断。
        • 3、最后两层：只有最后两层可能出现叶子结点。
          • n个结点，n为奇数：叶子结点有（n+1）/2个
          • n个结点，n为偶数：叶子结点有n/2个
        • 4、最多只有1个度为1的结点。
        • 5、左右子树：一个结点若其右子树上的子孙的最大层次为k，那么其左子树上的子孙的最大层次为k或k+1。
        • 6、左右孩子：最多只能有一个度为1的结点，且该结点只有左孩子没有右孩子。
        • 7、结点数奇偶：
          • 结点数n为奇数：不存在度为1的结点，每一个分支结点都有左右孩子。
          • 结点数n为偶数：有且仅有1个度为1的结点，且该结点只有左孩子没有右孩子。
        • 8、高度／深度：
        • 9、对有n个结点的完全二叉树按层序编号以后，任意结点i以下结论
          • i＝1
            • i为根。
          • i＞1
          • 左右孩子
            • 结点i的左孩子是2i，如果此时2i＞n，改i结点一定没有左右孩子，即该结点为叶子结点。
            • 结点i的右孩子是2i+1，如果此时2i+1＞n，该i结点一定没有右孩子。
  • 4、二叉树的性质
    • 考点一
    • 考点二
      • 高度为h最多最少有几个结点？
      • 最多有几个叶子结点？
      • 第i层最多最少几个结点？
  • 5、二叉树的基本形态
    • ①空二叉树。
    • ②仅有根结点的二叉树。
    • ③左子树为空的二叉树。
    • ④右子树为空的二叉树。
    • ⑤左右子树非空的二叉树。
  • 6、二叉树的遍历
    • 概念
      • 遍历二叉树就是从根结点出发，按一定的次序访问所有的结点，而且每个结点只被访问一次。
    • 规则
      • 先序，中序，后序遍历
        • 基于树的递归特性，确定的遍历规则。
      • 层序遍历
        • 基于树的层次特性，确定的遍历规则。
    • 三个元素
      • 访问根结点：T→data
      • 访问左孩子：T→lchild
      • 访问右孩子：T→rchild
    • 四种口诀
      • 先序遍历
        • 根、左、右
      • 中序遍历
        • 左、根、右
      • 后序遍历
        • 左、右、根
      • 层序遍历
        • 自上到下，从左往右
          • ①初始化一个辅助队列。 ②根结点入队。 ③若队列非空，则对头结点出队，访问该结点，并将其左右孩子依次入队。（如果存在的话） ④重复步骤三直到队列为空。
    • 遍历序列
      • 特点
        • 推特点方法 ①画图推测法 ②口诀比对法
        • 先序遍历
          • 在先序遍历序列中，第一个为根结点。
        • 中序遍历（算数表达式）
          • 最左右结点。
            • 在中序遍历序列中，第一个为最左的结点。
            • 在中序遍历序列中，最后一个为最右的结点。
          • 左右子树。
            • 在中序遍历序列中，左子树的所有结点先于根结点被访问。
            • 在中序遍历序列中，右子树的所有结点后于根结点被访问。
          • 左子树最右，右子树最左结点
            • 在中序遍历序列中，访问了左子树上最右的结点后，紧跟着访问根结点。
            • 在中序遍历序列中，访问了根结点后，紧跟着就访问了右子树上最左的结点。
        • 后序遍历
          • 在后序遍历序列中，最后一个为根结点。
        • 层序遍历
          • 自上到下自左到右遍历即可
    • 由遍历序列构造二叉树
      • 注意
        • 已知二叉树的前、中、后、层序遍历序列的其中任何一种，都无法确定一棵二叉树。
      • 方法
        • 前序+中序遍历序列
        • 后序+中序遍历序列
        • 层序+中序遍历序列
        • 可以唯一确定一棵二叉树
          • 分支结点展开法
            • 每遇到一个结点时 就按照相应的遍历方法进行展开。
      • 步骤
        • ①确定根节点。
        • ②确定左右子树。
        • ③根据口诀慢慢推。
• 哈夫曼树（最优二叉树）（考大题）
  • 1、定义
    • 在含有n个带权叶子结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树。
  • 2、基本术语
    • ①路径
      • 一个结点到另一个结点的分支
    • ②路径长度
      • 路径上分支的数目。
    • ③结点的权
      • 结点内具有特定意义的实数。
    • ④结点的带权路径长度
      • 从某结点到根结点之间的路径长度×该结点权值。
    • ⑤树的带权路径长度
      • 树中所有叶子结点的带权路径长度之和，记作WPL。
  • 3、哈夫曼构造算法
    • 构造方法
      • 一定要找两个较小权值 计算根结点要仔细
      • 1、（构造n个树）根据给定的n个权值构造n个只有根结点的二叉树，这些二叉树组成一个F集合。
      • 2、（较小权值构造新树）在1中构造的n棵二叉树中，选取两棵权值较小的树，分别作为左右子树构造一棵新的二叉树，构造出的这颗新的二叉树的根结点是选取的这两颗权值较小的树的权值之和。
      • 3、（删除旧树，加入新树）在F中删除2选取的两棵树，并将新得到的二叉树加入F中。
      • 4、（重复2和3）重复步骤2和3，直到F中只剩下一棵树为止，这棵树就是哈夫曼树。
    • 特点
      • ①对于给定的n个权值，虽然其哈夫曼树不唯一，但他们的wpl相等。
      • ②因为哈夫曼树不唯一，所以哈夫曼树不一定是完全二叉树。
      • ③每一个初始结点最终都会成为度为零的结点。（叶子结点）
      • ④哈夫曼树中不存在度为一的结点。
      • ⑤除了叶子结点，其余都是度为2的结点。
      • ⑥给了n个叶子结点，它的结点总数是2n- 1。
      • ⑥给了n个叶子结点，要经过n-1次合并才能形成哈夫曼树，共出现n-1个新结点，且这n-1个新结点的度都为2。
      • ⑦哈夫曼树中权越大的叶子结点的离根结点越近。
      • ⑧n个分支的哈夫曼树共n+1个结点
  • 4、哈夫曼编码
    • 定义
      • 没有一个编码是另一个编码的前缀（没有一片树叶是另一片树叶的祖先），则此编码为前缀编码，即哈夫曼编码。
    • 对比概念
      • 固定长度编码：对每个字符用相等长度的二进制位表示。
      • 可变长度编码／哈夫曼编码：允许对不同字符用不等长的二进制位表示。
    • 约定
      • 画正字数编码个数法
      • （左0）左分支表示零
      • （右1）右分支表示一
• 森林（考大题）
  • 概念
    • 森林是m颗互不相交的树的集合。（m≥0）
  • 树、森林和二叉树的转化
    • 用树→构造二叉树
      • 1、步骤
        • ①（确定根结点）树的根结点就是二叉树的根结点。 ②（口诀）按照左孩子右兄弟的口诀进行构造，二叉树即可。
        • 2、特点
          • 从树转化为的二叉树，只有左子树，没有右子树。
            • 所以利用二叉链表表示树，根结点的右指针为空
    • 用森林→构造二叉树
      • 1、步骤
        • ①（确定根结点）用森林构造出的二叉树的根结点是森林最左边第一棵树的根结点。 ②（第一行兄弟）森林中多棵树的第一行的根节点互为兄弟。 ③（口诀）按照左孩子右兄弟的口诀进行构造二叉树即可。
        • 2、特点
          • 从森林转化为的二叉树，既有左子树，又有右子树。
            • 左子树：从森林转化为的二叉树的左子树，是森林最左边第一棵树所对应的二叉树。T1-1
            • 右子树：从森林转化为的二叉树的右子树，是由除了森林最左边的第一棵树之外的其余树组成的二叉树。T2+T3
    • 用遍历序列→构造二叉树
  • 树、森林和二叉树的遍历
    • 因为树和二叉树可以相互转换，森林和二叉树可以相互转换， 所以对树和森林的遍历可以转化为对应的二叉树遍历操作。
      • 遍历规则
        • 树的遍历
          • ①对当前的树直接进行各种（前、中、后）遍历即可。
        • 森林的遍历
          • ①先转化为森林对应的二叉树。 ②对森林转化为的二叉树的遍历就是森林的遍历。
      • 规则图片
• 树
  • 树定义
    • ①树是树型结构的简称。②树是一种非线性数据结构，是一种递归定义的数据结构。③树是n个元素（结点）的有限集。（n≥0）
      • 空树
        • n＝0（结点为零）为空树。
      • 非空树
        • n≥1，为非空树。
          • • 根结点→有且仅有一个（根结点没有前驱结点，即没有双亲）。
            • 当n＞1，除根节点以外的其他结点组成的互不相交有限集（子树）→m个（m≥0）
      • 特点
        • 一对多
        • 层次性
        • 树形状
  • 基本术语
    • 1、结点。（点）
      • 树中的元素。
    • 2、结点的度。（边）
      • 结点的分支数。
    • 3、叶子结点／终端结点（分支为0的点）
      • 度为0的结点。（叶子结点没有后继结点，即没有孩子 叶子结点可以一个或多个）
    • 4、分支结点／非终端结点（分支不为0的点）
      • 度不为0的结点。
    • 5、孩子结点。（下）
      • 某结点子树的根结点称为该结点的孩子。
    • 6、双亲结点。（上）
      • 相应的，该某结点称为孩子的双亲结点。
    • 7、兄弟结点。（同一双亲）
      • 同一个双亲的孩子之间互称兄弟。
    • 8、祖先结点。（前驱结点）（上）
      • 从根节点到该结点所经分支上所有结点称为该结点祖先。
    • 9、子孙结点。（后继结点）（下）
      • 某结点为根以下所有子树上的结点称为该结点子孙。
    • 10、堂兄弟结点。（双亲在同一层）
      • 双亲在同一层的节点互称堂兄弟。
    • 11、结点的层次（深度／高度）。（从上往下第几行）
      • 横向看有几行。（根结点为第一层）
    • 12、树的度。（边最大）
      • 结点的最大分支数。
    • 13、树的层次（深度／高度）。（最大几行）
    • 14、有序树。
      • 如果树中各结点的子树从左到右是有次序的，则称为有序树。
        • 第一棵子树
          • 有序数中，某结点最左边的子树
        • 第一个孩子
          • 有序数中，某结点最左边的子树的根称为该结点的第一个孩子。
    • 15、无序树。
      • 树中各结点从左到右没有次序，则称为无序树。
    • 16、森林
      • 森林是m颗互不相交的树的集合。
  • 树的性质
    • 考点一
    • 考点二
      • 度为m的树
        • 一定是非空树。
        • 至少有一个结点的度为m。
        • 任意结点的度都≤m（这里的小于和等于是且的关系）
        • 度为m的树一定是m叉树。
      • m叉树
        • 可以是空树。
        • 可以没有度为m的结点，所有结点的度都小于m是被允许的。
        • 任意结点的度都≤m（这里的小于和等于是或的关系）
        • m叉树不一定是度为m的树。
    • 考点三
      • 度为m的树
        • 高度为h最多最少有几个结点？
        • 第i层最多几个结点？
      • m叉树
        • 高度为h最多最少有几个结点？
        • 最高最低有多少高度？
        • 第i层最多最少几个结点？
  • 树的存储结构
    • ①双亲表示法
      • 1、概念
        • 双亲表示法是用一片地址连续的存储区域来按层顺序存储树的结点，并在每个结点中附设一个指示器，指示其双亲结点的位置，指示器中存的是对应双亲在数组中的下标。
      • 2、特点
        • 根节点固定存储在数组下标为0的位置，双亲位置显示-1表示没有双亲。
      • 3、优缺点
        • 找结点的双亲很容易，找结点的孩子不容易。
    • ②孩子表示法
      • 1、概念
        • 树中每个结点的孩子存放在一个单链表中，而且这些单链表的头指针保存在一个一维数组中。
      • 2、特点
        • 结点
          • 一个结点有几个孩子则对应的单链表有几个结点
            • 数据域
              • 单链表中某孩子结点的数据域保留的是该孩子结点在数组中对应的下标。
            • 指针域
              • 单链表某孩子结点的指针域保留的是该孩子结点的直接后继的指针。
        • 空
          • 空表
            • 叶子结点的孩子链表为空表。
          • 空指针
            • 某结点的孩子链表中，某个孩子的下一个直接后继结点的话，指针域为空。
      • 3、优缺点
        • 找结点的孩子很容易，找结点的双亲不容易。
    • ③孩子兄弟表示法
      • 1、概念
        • 以二叉链表来表示树，因此又称为二叉链表表示法／二叉树表示法。
      • 2、特点
        • 左右子树
          • 从树转化为的二叉树，只有左子树，没有右子树。
          • 从森林转化为的二叉树，既有左子树，又有右子树。
        • 兄弟结点
          • 二叉链表同是兄弟的几个结点，在一条斜线上。
      • 3、结点由三个域构成
        • firstchild
          • 指向某结点的左孩子。
        • data
          • 存放某结点的值。
        • nextsibling
          • 指向某结点的右兄弟。
  • 树的遍历
    • 先根遍历
    • 后根遍历