第六章 树和二叉树

树和二叉树

树

树的定义

• 形式化定义：
  
• 递归定义：
  

树的逻辑表示

• 树形表示法：
  
• 文氏图表示法：
  
• 凹入表示法：
  
• 括号表示法：
  

树的基本术语

• 结点的度与树的度
  
  • 结点的度指的是子树的个数；
  • 树的度是各结点度的最大值
  • m次数或者m叉树，其中的m均指的是树的度。（二叉树是被重新定义过的，它的度小于或者等于2）
• 分支结点与叶结点：
  
• 路径与路径长度
  
  • 路径是指两结点间的结点（包含自身）;
  • 路径长度是指两结点路径上的分支数目，不是结点的个数。
• 孩子结点、双亲结点和兄弟结点
  
• 子孙结点和祖先结点
  
  • 子孙结点与孩子结点的区别：子孙结点可以跨很多辈，而孩子结点只是比双亲低一辈；
  • 祖先结点与双亲结点的区别：祖先结点可以跨很多辈。
• 结点的层次与树的高度（深度）：
  
  • 与结点的度和树的度的关系类似，最大的结点的度为树的度；最大的结点的层次为树的高度（深度）。
• 有序树与无序树
  
• 森林：
  
  • 森林相当于树的上级；
  • 一棵树也同时也是森林。

树的性质

1. 树中的总结点数等于所有结点的度数之和加1。
   
   • 每个结点的度都表示它的子结点的个数，所以每个结点的度加起来可以表示结点的个数；
   • 但是根结点没有双亲结点，所以没有将根节点加进去，所以得在所有度之和的基础上加一表示根结点。
2. 每层的最大结点数
   
   • 相当于是从根结点递归推下来的：第1层只有一个，第二层最多有m个，第三层最多有$m * m$个，第四层最多有$m^3$个…
3. 一棵树最多的结点数
   
   • 在每层最多结点数的条件下累加起来（等比数列求和）
4. 一颗树的最小高度
   
   • 在一棵树结点数最多的情况下反解出最下高度。

树的基本运算

树的基本操作

树的基本运算

树的遍历

1. 先根遍历：若树不空，先访问根结点，然后依次先跟遍历各颗子树（递归描述）
2. 后根遍历：若树不空，先依次后根遍历各颗子树，然后访问根结点；
3. 层次遍历：若树不空，则自上而下，自左至右访问树中的每个结点。

树的先根遍历

• 根与结点始终是相对的。最开始先到A,此时B,C,D看做三颗子树，A过后到B,此时B又做根，E,F做子树，E,F依次访问完了，才又回到A的角度，遍历A的第二颗子树C，依次递归下去。

树的后根遍历

• 先找到第一个叶子结点，先从左往右访问它的兄弟结点，这个子树的兄弟结点都访问完了再回到双亲，双亲又访问它的兄弟结点，若它的兄弟结点下面还有结点，则将该结点以及它以下的结点看做一颗子树的整体，进入这颗子树后，又是从第一个叶子结点开始，层层回溯。直到最后回到根结点。

树的层次遍历

• 遵从从上至下，从左至右的顺序依次遍历即可。

二叉树

二叉树的定义

• 递归定义
  

• 二叉树的五种基本形态
  

  • 空树和单独一个根结点都可以看做二叉树；
  • 二叉树不须每个结点的度都为2，甚至是只要结点最大的度不超过2即可。这是二叉树与二次树的区别，二次树必须至少有一个度为2的结点（即二次树的度为2，二叉树的度小于或者等于2）

• 特殊的二叉树

  1. 满二叉树
     
  • 性质：高度为h的满二叉树恰有$2^h - 1$个结点（由树最多结点数的性质推导）
  2. 完全二叉树
     
     • 完全二叉树包含了满二叉树。
     • 完全二叉树最下层的叶子结点一定先集中在左边。

二叉树的性质

1. 非空二叉树的叶结点数
   
   • 利用度的总数与结点总数的关系推得。
2. 非空二叉树每一层上最多的结点数
   
3. 非空二叉树最多的结点数
   
4. 完全二叉树的性质
   1. 度数为0的结点数为0或1：
      
      • 最后一行如果没有满，就必须从左至右排列叶子结点，上一层同时有两个结点都只有一个分支的情况是不可能发生的。
   2. 根据编号判断分支结点和叶子结点
      
   3. 双亲的编号与孩子的编号之间的关系
      

二叉树的存储结构

1. 顺序存储结构
2. 链式存储结构

二叉树的顺序存储结构

• 完全二叉树的顺序存储结构
  
  • 利用双亲与孩子结点编号之间的关系，确定每个结点在数组中的下标，并且根据这种关系来用数组恢复二叉树的逻辑关系。
• 非完全二叉树的顺序存储结构
  
  • 用空结点将非完全二叉树补全为完全二叉树，之后再依次标号，好使用完全二叉树双亲与孩子结点编号直接的关系表达二叉树的逻辑结构。
• **二叉树顺序存储结构的特点：
  1. 十分适合用来存储完全二叉树；
  2. 对于一般的二叉树，特别是单分支结点较多的二叉树来说，可能会使很多空结点未被利用，造成存储空间的大量浪费。
  3. 二叉树的顺序存储结构中，找一个结点的双亲和孩子结点十分容易，只需根据下标换算即可。

二叉树的链式存储结构

• 结点的类型定义：
  
  • 链式存储是利用递归思想来表现二叉树的逻辑结构。
• 链式存储结构的表现：
  
• 链式存储结构的空指针域
  
  • 总指针域数（结点数的两倍）减去分支数（结点度数之和）
• 二叉树链式存储结构的特点
  1. 除了会有一些空指针域的浪费，二叉链较顺序存储结构更为节省空间；
  2. 在二叉链中，找一个结点的孩子容易（根据自己的指针域找即可）,但是找双亲就很麻烦。（可以设计指回去的指针噻。）

二叉树（链式）的基本运算

二叉树的基本操作

二叉树的遍历运算

• 遍历只允许每个结点仅被访问一次。
• 不管采用哪种方法遍历，在有选择的地方都是从左至右的。

先序遍历

• 基本原理
  

  • 每到一个结点都看作是最简单的三个结点的二叉树，贯彻递归的思想。

• 先序遍历的递归算法
  

  • 所有遍历的前提都是树不空，所以遍历之前要判断树是否为空，这也是递归结束的条件。

• 先序遍历的非递归算法1

  • 基本原理：出栈访问法
    
    • 利用栈的特性。从根结点进栈后，将其出栈，出栈接受访问的同时将它的右左孩子进栈，之后再依序将左孩子出栈，并将其的右左孩子进栈，一层嵌一层，从而实现了类似递归的效应。
  • 具体算法：
    
    * 注意，一切操作之前还是要先判断二叉树是否为空。
    * 进栈的顺序是先右孩子，后左孩子，出栈时才能实现先左后右。
    * 遍历结束的条件是栈为空。

• 先序遍历的非递归算法2

  • 基本原理：进栈访问法
    
    
    • 注意：算法有瑕疵，在进栈的循环完之后在进入出栈的步骤前，应该增加一步取栈顶元素指针的步骤，每次出栈的是栈顶元素，不应都用一个指针来混淆。
    • 进栈时访问了根结点，将根结点进栈，然后转向左子树，将左子树进栈访问，然后再将当前结点视为相对根结点转向其左子树依次进行下去，直到左子树被穷尽，之后出栈栈顶元素（最后进来的左结点）,转向其右子树。
  • 具体算法：
    
    • 虽说遍历的结束条件是栈为空或者p为NULL,但是实际上遍历结束时，定是栈既为空p也为NULL,但是未遍历结束到达循环底部，单独栈为空时p必不为NULL,p为NULL时栈必不为空；之所以将条件设置为或者是因为刚要进入遍历循环前，栈为空，但是p不为NULL,这样设置既能保证进入循环又能保证控制循环的结束。（改为do while循环便可减少条件但仍能进入循环）

中序遍历

• 基本原理
  

  • 左中右的顺序。先找到最左边的元素，访问它的左结点，此时定为空，然后访问自身，再转向右结点，之后回到这颗左子树对应的根结点，递归下去。

• 中序遍历的递归算法
  

• 中序遍历的非递归算法

  • 基本原理：
    
    • 源自先序遍历的进栈访问法，只是将访问的时间改变成了出栈时。
  • 具体算法：
    

后序遍历

• 基本原理
  

  • 左右后的顺序。先序，中序和后序的区别在于根结点在何时被访问，二先左后右的顺序是始终没有改变过的。
  • 同中序遍历类似，先找到最左边的元素，访问它的左结点，此时定为空，然后转向右结点并访问，之后回到该左边的元素，访问它，然后回到这颗左子树对应的根结点，依次递归下去。

• 后序遍历的递归算法
  

• 后序遍历的非递归算法

  • 基本原理
    
    • 源自中序遍历的非递归算）,但是由于根结点必须最后访问，但是从左结点到右结点必须经过根结点，但第一次经过根结点时又不能访问它，所以需要设计一个标识来判读此时的指针指向的结点能不能被访问。
  • 具体算法：
    
    • 由于第一次经过根结点时不能直接访问，但根据中序遍历的算法每次都是进入访问栈顶元素的循环中，直接访问栈顶元素，所以使用一个r指针和flag标识，当此时根结点有右孩子时，跳过访问它的步骤，而转向它的右孩子，并将flag标识设为false表明此时已经不是在处理栈顶元素了，需要退出处理栈顶元素的循环。
    • 在退出处理栈顶元素的循环后，将此时指针指向的右孩子结点进栈，变为新的栈顶元素，再进入处理栈顶元素的循环中，将其出栈访问，并且将r标识指向它，表明它已经被处理过了，之后继续在处理栈顶元素的循环中运行，此时根节点由于有了r指针说明它的右孩子已经被处理过了，所以能够顺利地出栈访问。
    • 依次递归进行下去，层层出栈逐渐处理回上层结点。
    • 这个两个标识设计得确实秒啊！！！
    • 怪不得老师在先序遍历的第二种非递归算法和中序遍历的非递归算法中要单独注释处理栈顶元素的循环，原来是为这里做准备！

层次遍历

• 层次遍历：对于一颗二叉树，从根结点开始，按从上到下，从左至右的顺序访问每一个结点。

• 基本原理：
  

  • 利用队列先进先出的特性遍历二叉树。根结点进队，然后出队，出队时依次将它的左右孩子进队，然后左右孩子出队，同时又将它们的孩子进队，依次递归下去。

• 算法实现

  • 结点定义：
    
    • 采用环形队列
  • 具体算法：
    
    • 队空时说明二叉树已经遍历完了。因为此时遍历倒数第二层结点时储存在队列中的的叶子结点已经全部出队了。

线索二叉树

线索二叉树的定义

• 在二叉树的链式存储结构的基础上，修改空链域为指向结点的前驱和后继结点的地址。这样指向该二叉树中的前驱和后继的指针，称为线索。（这里的前驱和后继是相对于遍历的先后顺序来说的）
• 创建线索的过程称为线索化
• 生成的线索二叉树与采用的遍历方法有关，据此，线索二叉树分为三种：1. 先序线索二叉树；2.中序线索二叉树；3.后序线索二叉树。

线索二叉树的基本原理

• 结点的设计
  • 设计原理：
    
    • 每个结点都只有两个指针域，这两个指针域是指向自己的孩子结点还是指向自己的前驱和后继结点，则需要设置标志来判断。
  • 结点类型定义：
    
• 线索二叉树的基本模型
  
  • 先要根据具体的遍历方法，找到每个结点的前驱和后继；
  • 左指针域指向左孩子结点或者前驱结点，此处根据中序遍历规则，最左边最下面的结点没有前驱结点，最右边最下面的结点没有后继结点，所以设置了一个额外的头结点来做这种没有前驱或者后继的结点的“前驱和后继”。

线索化二叉树

• 线索化的过程
  

  • 依照某种遍历方法遍历该二叉树，在遍历的过程中，检查每个结点的指针域是否为空，并根据具体的情况，将这些空指针域指向各自的前驱或者后继结点。

• 建立中序线索二叉树的算法

  • 基本原理
    
    • 在中序遍历该二叉树的同时设立两个指针，分别指向互为前驱和后继的两个结点，其中有一个一直指向当前结点，另一个指向它的前驱结点。
  • 具体算法：
    
    • 线索化二叉树的函数有两个，一个负责修改二叉树中各个结点的指针域（Thread）,一个负责创建头结点等开始启动工作和修改最后一个结点的指针域等收尾工作。
    • 先将头结点创建好，并将其后继结点设为头结点并修改标识符（如果这是一个空树，则将头结点的左孩子指针域指向头结点，示意这是空树）
    • 头结点的左孩子结点设为二叉树的根结点，pre指针指向头结点，将二叉树的根结点指针传入Thread函数；
    • 在Thread函数中，应用中序遍历的递归算法，只不过把中间访问根结点的步骤改为检查当前结点的指针域并修改的步骤；
    • 结束Thread函数后，该二叉树除了最后一个结点的后继线索未设置好之外，其余结点的线索均已设置好；
    • 最后结束Thread函数，再次进入CreateThread函数中时，只需再将最后一个结点的线索修改好即可。

遍历线索化二叉树

• 基本原理
  
  

  • 找到开始结点（采用不同的线索化方式而有不同，开始结点不是头结点，而是整个遍历过程中要第一个访问的结点）。
  • 在遍历过程中要由线索指向的结点才接受访问。
  • 最后遍历的指针指向了头结点时，则说明整颗树已经遍历完成了。

• 具体算法：
  

  • 如果是线索就直接访问它，如果不是线索就转向它而不访问。

二叉树的构造

• 二叉树序列性质：

  • 同一颗二叉树，具有唯一的先序序列，中序序列和后序序列。但不同二叉树可能具有相同的先序序列、中序序列和后序序列。
    • 示例：
      
  • 通过一颗二叉树的先序、中序和后序序列可以唯一确定该二叉树。（同时有三种序列）
  • 仅有先序、中序和后序中的一种，无法唯一构造该二叉树。
  • 任何n个不同结点的二叉树，都可有它的中序序列和先序序列唯一地确定。（或者中序序列和后序序列）。即必须有中序序列。

• 由先序序列和中序序列构造二叉树

  • 基本原理：
    
    • 通过递归的思想理解，把两种序列都看作根结点、左子树和右子树三个部分。然后同一个结点对应在两个序列的相同部分（比如说都是在根结点部分）的不同位置。
  • 示例：
    
  • 具体算法：
    
    • 先确定是否为空树（**这是确定最后递归结束的重要条件），再确定在这两种序列中的左子树，右子树和根结点的三个部分。
    • 采用分而治之的递归思想，在每一个左右子树部分执行同样的的操作，递归下去，直到序列走尽。

• 由后序和中序序列构造二叉树

  • 基本原理：
    
    • 通过根结点确定序列左子树、右子树和根结点的三个部分是关键。（之所以只用先序和后序序列不能构造二叉树，就是因为这两个的根结点都位于开头或者结尾，无法通过根结点划分序列为三个部分，而单独中序序列由无法确定根结点的位置）
  • 示例：
    
    • 每次放入二叉树的结点的都是相对的根结点。
  • 具体算法：
    
    • 整体是先构造根结点再构造左子树和右子树，是先序遍历的思路。

树、森林和二叉树的关系

树的存储结构

树的双亲存储结构

• 使用顺序存储结构来存储树的结点。
• 在每一个结点的数据元素之外，再加上一个记录它的双亲元素的位置的元素。（即新增一个元素存储该结点双亲的下标）。

树的孩子链存储结构

• 每个结点都用一个指针指向，让后每一个结点内不仅包含自身的数据，还要再设置一个指针类型的数组来记录它的孩子结点的指针。
• 空指针域会很多。

树的孩子兄弟链存储结构

• 每个结点只设置两个指针域，一个指向孩子结点（或者孩子结点构成的链）,一个指向兄弟结点。
• 结束的结点应该两个指针域均为空。

二叉树与树、森林之间的转换

树、森林转化为二叉树

• 一棵树转化为二叉树
  
  • 实现步骤：
    1. 将树的根节点直接作为二叉树的根节点
    2. 将树的根节点的第一个子节点作为根节点的左儿子，若该子节点存在兄弟节点，则将该子节点的第一个兄弟节点（方向从左往右）作为该子节点的右儿子
    3. 将树中的剩余节点按照上一步的方式，依序添加到二叉树中，直到树中所有的节点都在二叉树中.
  • 总的来说：每个点的左儿子是它的第一个儿子，右儿子是它从左往右数的第一个兄弟。
• 多棵树（森林）转化为二叉树
  
  • 法一：
    1. 把森林的每一棵树转成二叉树
       1. 以某一棵树作为起始树，下一棵树的根结点作为右孩子连接到上一颗树的根结点。直到处理完最后一棵树。
  • 法二：
    1. 新增一个结点，把这个结点作为总的根结点，然后将所有树组成一个新的树；
    2. 按照处理一颗树的方式，把这棵树转化为二叉树；
    3. 最后删除新增的结点。

二叉树还原为森林、树

• 将一棵二叉树还原为一棵树
  
  • 实现步骤：
    1. 加线。如果某个结点存在左孩子，则将左孩子的右结点，其右结点的右孩子…也就是一直深入到没有右孩子，将这些结点与父结点连线。
    2. 去线。删除所有结点与其右孩子的连线。
    3. 调整结构，让原本某结点的右孩子与该结点处于一个水平线，则他们成为了兄弟。
• 将一棵二叉树还原为多棵树（森林）
  
  • 实现步骤：
    1. 将所有结点的右孩子与其的连线切断，从而还原出很多二叉树；
    2. 将还原出的二叉树再进一步还原为普通树。

哈夫曼树

哈夫曼树的定义

• 带权路径长度
  
  • 根结点到各个叶结点的路径长度与权值的乘积之和。
• 哈夫曼树
  
  • 哈夫曼树是在叶结点权值相同情况下构造出的带权路径长度最小的二叉树。
  • 哈夫曼树首先是二叉树；
  • 哈夫曼树又称为最优树。
• 哈夫曼树的特点
  1. 没有度为1的结点.
  2. $n=n_0+n_1+n_2=2n_0-1$

构造哈夫曼树->???

• 基本原理
  • 权值越大的叶结点越靠近根结点，反之，权值越小的叶结点越远离根结点。
• 构造哈夫曼树的过程
  
• 构造哈夫曼树的算法
  • 结点结构
    
  • 具体算法：
    
    • 关键在于每次剔除已经有了双亲结点的结点。

哈夫曼编码 =》？？？

• 定义
  

  • 哈夫曼编码是二进制的01代码
  • 特点：权值越大的字符编码越短，反之越长。
  • 哈夫曼编码是针对叶结点而言的。=》在一组字符中，不可能出现一个字符的哈夫曼编码是另一个字符哈夫曼编码的前缀。
  • 哈夫曼编码又称前缀编码。

• 哈夫曼编码的生成算法

  • 哈夫曼编码的存储结构
    
  • 具体算法：