一、树的基本概念

树：是 n ( n>=0 ) 个结点的有限集。

• n = 0 时称为空树。
• 在任意一棵非空树中:
  • 有且仅有一个根结点
  • 当 n > 1 时，其余结点可分为一个或多个互不相交的有限集。 其中每一个集合本身又是一棵树，并且称为根的子树。

1、结点分类

• 结点的度：结点拥有的子树数
• 叶结点：度为 0 的结点
• 分支结点：度不为 0 的结点
• 树的度：树内各结点的度的最大值

2、结点间关系

• 孩子：结点的子树的根称
• 双亲：上一结点
• 兄弟：同一个双亲的孩子
• 祖先：从根到该结点所经分支上的所有结点

3、树的其他相关概念

• 层次：根开始定义起，根为第一层 ，根的孩子为第二层
• 堂兄弟：双亲在同一层的结点
• 树的深度：树中结点的最大层次
• 有序树：树中结点的各子树从左至右有次序，不能互换
• 无序树：非有序树
• 森林：m (m>=0) 互不相交的树的集合

二、二叉树

1、二叉树的定义

二叉树：是 n(n >= 0) 个结点的有限集合，该集合或者为空集(称为空二叉树)，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

1）主要特征

• 每个结点最多有两棵子树，所以二叉树中不存在度大于 2 的结点。
• 左子树和右子树是有顺序的，次序不能任意颠倒。
• 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树.

2）特殊二叉树

• 斜树：都只有一边子结点
  • 左斜树：所有的结点都只有左子树的二叉树
  • 右斜树：所有结点都是只有右子树的二叉树
  • 线性表结构可以理解为是树的一种极其特殊的表现形式
• 满二叉树：每层结点都排满了
• 完全二叉树：按层排序，到结尾中间没有漏掉的结点

3）二叉树性质

• 在二叉树的第 i 层上至多有 2^{i-1} 个结点 (i >= 1 ) 。

• 深度为 k 的二叉树至多有2^k-1个结点 (k >= l) 。

• 对任何一棵二叉树 T，如果其终端结点数为 n_0，度为 2 的结点数为 n_2，则 n_0 = n_2 +1。

• 具有 n 个结点的完全二叉树的深度为 [log_2n]+1 ([x] 表示不大于 x 的最大整数)。

• 如果对一棵有 n 个结点的完全二叉树(其深度为 [log_2n]+1 ) 的结点按层序编号(从第 1 层到第 [log_2n]+1层，每层从左到右) ，对任一结点 i (1<= i<= n)有:

  • 如果 i = 1 ，则结点 i 是二叉树的根，无双亲；如果 i > 1 ，则其双亲是结点 [i/2]。

• 如果 2i > n ，则结点 i 无左孩子(结点 i 为叶子结点)；否则其左孩子是结点 2i。

  • 如果 2i+1 > n ，则结点 i 无右孩子；否则其右孩子是结点 2i+1 。

2、二叉树的存储结构

1）顺序存储结构

顺序存储结构一般只用于完全二叉树。

用一维数组存储二叉树中的结点，数组的下标和结点序号一致。没有结点的存空。

2）链式存储结构

二叉链表：一个数据域和两个指针域的链表。

指针域分别存左孩子和右孩子的指针。

3、二叉树的遍历

1）遍历方法

• 前序遍历：根节点->左子树->右子树
• 中序遍历：左子树->根节点->右子树
• 后序遍历：左子树->右子树->根节点
• 层序（宽度优先、广度优先）遍历：每一层从左向右输出

前序、中序、后序遍历用迭代很简单。

层序遍历，元素储存有先进先出的特性，选用队列。

2）遍历推导

• 己知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
• 已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树 。
• 已知前序和后序遍历，是不能确定一棵二叉树的

3）二叉树的建立

扩展二叉树：将每个结点的空指针引出一个虚结点，值为特定值（如“#”）

扩展二叉树可以用递归采用前序、中序、后序遍历的一个遍历序列就确定一颗二叉树。

4、线索二叉树

1）基本概念

• 线索：指向前驱和后继的指针称为线索
• 线索链表：加上线索的二叉链表称为线索链表
• 线索化：将二叉链表中的空指针改为指向前驱或后继的线索

线索二叉树，等于是把一棵二叉树转属变成了一个双向链表，对插入删除结点、查找某个结点都带来了方便

2）构造

每个结点增设两个标志域 ltag 和 rtag，区分指针是指向孩子还是指向前驱、后继。

在遍历的过程中修改空指针。

如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。

三、树、森林

1、树的存储结构

1 ）双亲表示法

除了根结点外，其余每个结点，它不一定有孩子，但是一定有且仅有一个双亲。以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。

存储结构的设计是一个非常灵活的过程。

• 双亲域：增加一个结点指示其双亲结点的域
• 长子域：增加一个结点最左边孩子的域
• 右兄弟域：增加一个右兄弟域体现兄弟关系

当算法中需要在树结构中频繁地查找某结点的父结点时，使用双亲表示法最合适。当频繁地访问结点的孩子结点时，双亲表示法就很麻烦，采用孩子表示法就很简单。

2）孩子表示法

由于树中每个结点可能有多棵子树，可以考虑用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，我们把这种方法叫做多重链表表示法。

• 方案一：指针域的个数就等于树的度
  • 树中各结点的度相差很大时，浪费空间
• 方案二：每个结点指针域的个数等于该结点的度
  • 各个结点的链表是不相同的结构，还要维护结点的度的数值，浪费运算时间

孩子表示法

把每个结点的孩子结点排列起来，以单链表作存储结构，则 n 个结点有 n 个孩子链表，如果是叶子结点则此单链表为空。然后 n 个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中

双亲孩子表示法

使用孩子表示法存储的树结构，正好和双亲表示法相反，适用于查找某结点的孩子结点，不适用于查找其父结点。可以将两种表示方法合二为一

孩子兄弟表示法

把一棵复杂的树变成一棵二叉树

链表中每个结点由 3 部分组成：

• 孩子指针域：表示指向当前结点的第一个孩子结点
• 数据域
• 兄弟指针域：表示指向当前结点的下一个兄弟结点

2、树、森林与二叉树的转换

1）树转换为二叉树

1. 加线。在所有兄弟结点之间加一条连线。
2. 去钱。对树中每个结点，只保留它与第一个孩子结点的连线，删除色与其他孩子结点之间的连线。
3. 层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。（注意第一个孩子是结点的左孩子，兄弟转换过来的孩子是结点的右孩子）

2）森林转换为二叉树

1. 把每棵树转换为二叉树。
2. 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。

3）二叉树转换为树

1. 加线。若某结点X的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点…，都作为结点X的孩子。将结点X与这些右孩子结点用线连接起来。
2. 去线。删除原二叉树中所有结点与其右孩子结点的连线。
3. 层次调整。

4）二叉树转换为森林

假如一棵二叉树的根节点有右孩子，则这棵二叉树能够转换为森林，否则将转换为一棵树。

1. 从根节点开始，若右孩子存在，则把与右孩子结点的连线删除。再查看分离后的二叉树，若其根节点的右孩子存在，则连线删除…。直到所有这些根节点与右孩子的连线都删除为止。
2. 将每棵分离后的二叉树转换为树。

3、树和森林的遍历

1）树的遍历

分为两种方式

• 一种是先根遍历树，即先访问树的根结点，然后依次先根遍历棍的每棵子树。
• 另一种是后根遍历，即先依次后根遍历每棵子树，然后再访问根结点

2）森林的遍历

也分为两种方式:

• 前序遍历: 先访问森林中第一棵树的根结点，然后再依次先根遍历根的每棵子树，再依放用同样方式遍历除去第一棵树的剩余树构成的森林。
• 后序遍历: 是先访问森林中第一棵树，后根遍历的方式遍历每棵子树，然后再访问根结点，再依次同样方式遍历除去第一棵树的剩余树构成的森林。

森林的前序遍历和二叉树的前序遍历结果相同，森林的后序遍历和二叉树的中序遍历结果相同。

当以二叉链表作树的存储结构时，树的先根遍历和后根遍历完全可以借用二叉树的前序遍历和中序遍历的算法来实现。

四、二叉树的应用

1、BST（二叉排序树/二叉查找树/二叉搜索树）

1）定义

二叉排序树：又称为二叉查找树、二叉搜索树。它或者是一棵空树，或者是具有下列性质的二叉树。

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值;
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值;
• 它的左、右子树也分别为二叉排序树。

二叉排序树利于插入和删除的实现。

2)操作

• 查找：查找成功返回ture，指向成功结点；查找失败返回false，指向上一结点。
• 插入：查找不成功，则插入到上一节点的子节点
• 构建：反复插入
• 删除：
  • 叶子节点直接删；
  • 只有左或右子树的，“子继父业”；
  • 左右子树都有的，找到需要删除的结点 p 的直接前驱(或直接后继) s，用 s 来替换结点 p，然后再删除此结点 s，s 的子结点移到 s 原来的位置

2、平衡二叉树

1）定义

• 平衡二叉树：是一种二叉排序树，其中每一个节点的左子树和右子树的高度之差的绝对值不超过 1。
• 平衡因子：二叉树上结点的左子树深度减去右子树深度的值（只可能是-1 、0 和 1）
• 最小失衡子树：在新插入的结点向上查找，以第一个平衡因子的绝对值超过1的结点为根的子树称为最小不平衡子树。

2）失衡调整

• LL失衡：右旋（Zig）。当传入一个二叉排序树 P，将它的左孩子结点定义为 L ，将 L 的右子树变成 P 的左子树，再将 P 改成 L 的右子树，最后将 L 替换 P 成为根结点。
• RR失衡：左旋（Zag）。与右旋对称。
• LR失衡：先左旋后右旋（Zig-zag）
• RL失衡：先右旋后左旋（Zag-zig）

3、堆

最大堆、最小堆

4、红黑树

把树中的节点定义为红、黑两种颜色，并通过规则确保从根节点到叶节点的最长路径的长度不超过最短路径的两倍。

5、哈夫曼(Huffman)树和哈夫曼编码

1）赫夫曼树定义

• 路径长度：从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做路径长度。
• 树的路径长度：就是从树根到每一结点的路径长度之和。
• 带权路径长度：结点的带权的路径长度为从该结点到树根之间的路径长度与结点上权的乘积。
• 树的带权路径长度：为树中所有叶子结点的带权路径长度之和 。

赫夫曼树：带权路径长度 WPL 最小的二叉树称做赫夫曼树。

2)赫夫曼树构造

1. 根据给定的 n 个权值 {w_1,w_2,...,w_n} 构成 n 棵二叉树的集合 F={ T_1,T_2,...,T_n}，其中每棵二叉树 T_i 中只有一个带权为 w_i 根结点，其左右子树均为空。
2. 在 F 中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3. 在 F 中删除这两棵树，同时将新得到的二叉树加入 F 中 。
4. 重复 2 和 3 步骤，直到 F 只含一棵树为止。这棵树便是赫夫曼树。

3)赫夫曼编码

赫夫曼编码：对需要编码的字符集，统计各个字符出现的次数或频率，作为权值，构造赫夫曼树。规定赫夫曼树的左分支代表0，右分支代表1，从根节点到叶子结点所经过的路径分支组成的 0 和 1 的序列便为该结点对应字符的编码。

• 定长编码：像 ASCII 编码
• 变长编码：单个编码的长度不一致，可以根据整体出现频率来调节
• 前缀码：所谓的前缀码，就是没有任何码字是其他码字的前缀