数据结构之二叉树汇总
数据结构其实是研究数据间关系的学科。主要分为三大块：
- 逻辑结构，
- 存储结构，
- 算法操作。
前言
四种逻辑结构：
- 集合，元素仅属于与同一个集体，之间没有关系。
- 线性结构，存在一对一关系，序列相邻，次序关系。
- 树形结构，存在一对多关系，层次关系。
- 图状结构（网状结构），存在多对多关系，任意性。
四种存储结构：
- 顺序结构，按内存地址连续存储。
- 链式存储，不连续的的一种存储方式，但每一项之间存在关系。
- 索引存储，附加索引。
- 散列存储，根据结点的关键字，直接计算出该店的储存地址。
现实中，一种问题对应一种逻辑结构，但往往对应多种存储结构。采用不同的存储结构，往往效率是不同的。
算法的 4 个特性：
- 正确性
- 可读性
- 健壮性、容错性
- 效率、控件时间复杂度
算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，但在过程中消耗的资源和时间却会有很大的区别。
那么我们应该如何去衡量不同算法之间的优劣呢？
主要还是从算法所占用的「时间」和「空间」两个维度去考量。
时间维度：
1.是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。
2.每条语句执行的时间基本差不多，通过语句数量 频度也可以描述。
空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。
基本术语
- 结点：一般指数中的一个元素，常用一个字母来表示。
- 度：一个结点包含子树的数目，成为该结点的度。（二叉树中度最大为 2）
- 树叶：度为 0 的结点，称为叶子节点、或者树叶。也叫终端节点。
二叉树的存储结构
1.顺序存储：
二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法从树根起，自上层至下层，每层自左至右地给所有结点编号,缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点存储空间。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。
（左）完全二叉树 （右）顺序存储结构
对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。如图给出了一棵一般二叉树改造后的完全二叉树形态和其顺序存储状态示意图。显然，这种存储对于需增加许多空结点才能将一棵二叉树改造成为一棵完全二叉树的存储时，会造成空间的大量浪费，不宜用顺序存储结构。最坏的情况是右单支树，如图所示，一棵深度为k的右单支树，只有k个结点，却需分配2k－1个存储单元。
（左）二叉树 （右）补全的完全二叉树
补全的完全二叉树存储状态
下面来一个极端的例子：
2.链式存储：
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。
通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。其结点结构为：
其中，data域存放某结点的数据信息；lchild与rchild分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号∧或NULL表示）。利用这样的结点结构表示的二叉树的链式存储结构被称为二叉链表
3.索引存储
4.散列存储：
二叉树的遍历
先序：根左右
中序：左根右
后续：左右根
比如上图二叉树遍历结果
前序遍历：ABCDEFGHK
中序遍历：BDCAEHGKF
后序遍历：DCBHKGFEA关于线索二叉树
和双向链表结点一样，在二叉树链表上添加一个头结点，如下图所示，并令其lchild域的指针指向二叉树的根结点（图中第一步），其rchild域的指针指向中序遍历访问时的最后一个结点（图中第二步）。反之，令二叉树的中序序列中第一个结点中，lchild域指针和最后一个结点的rchild域指针均指向头结点（图中第三和第四步）。这样的好处是：我们既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。
哈夫曼树
1.树的路径长度:树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。
-
结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。比如说出现的频率。
-
结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。
- 树的带权路径长度：定义为树中所有叶结点的带权路径长度之和
哈夫曼树是一种 带权路径长度最短的二叉树 ，也称为最优二叉树。下面用一幅图来说明。
上图， 80 的路径为：0
35 的路径为 00
8 的路径为 0010
二叉树 树 森林的相互转换
1、树转换为二叉树
由于二叉树是有序的，为了避免混淆，对于无序树，我们约定树中的每个结点的孩子结点按从左到右的顺序进行编号。
将树转换成二叉树的步骤是：
（1）加线。就是在所有兄弟结点之间加一条连线；
（2）抹线。就是对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线；
（3）旋转。就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。
2、森林转换为二叉树
森林是由若干棵树组成，可以将森林中的每棵树的根结点看作是兄弟，由于每棵树都可以转换为二叉树，所以森林也可以转换为二叉树。
将森林转换为二叉树的步骤是：
（1）先把每棵树转换为二叉树；
（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。
3、二叉树转换为树
二叉树转换为树是树转换为二叉树的逆过程，其步骤是：
（1）若某结点的左孩子结点存在，将左孩子结点的右孩子结点、右孩子结点的右孩子结点……都作为该结点的孩子结点，将该结点与这些右孩子结点用线连接起来；
（2）删除原二叉树中所有结点与其右孩子结点的连线；
（3）整理（1）和（2）两步得到的树，使之结构层次分明。
4、二叉树转换为森林
二叉树转换为森林比较简单，其步骤如下：
（1）先把每个结点与右孩子结点的连线删除，得到分离的二叉树；
（2）把分离后的每棵二叉树转换为树；
（3）整理第（2）步得到的树，使之规范，这样得到森林。
根据树与二叉树的转换关系以及二叉树的遍历定义可以推知，树的先序遍历与其转换的相应的二叉树的先序遍历的结果序列相同；树的后序遍历与其转换的二叉树的中序遍历的结果序列相同；树的层序遍历与其转换的二叉树的后序遍历的结果序列相同。由森林与二叉树的转换关系以及森林与二叉树的遍历定义可知，森林的先序遍历和中序遍历与所转换得到的二叉树的先序遍历和中序遍历的结果序列相同。
参考资料：