数据结构与算法读书笔记1：树

一、树的基本概念

树是n（n>=0）个结点的有限集合，有且仅有一个根节点（如下图所示的结点A）。
n>1时，树上的其余结点可以分成m个互不相交的子树，子树本身还是一棵树（从这一点看树是一种包含了递归概念的数据结构）。

树：最多只有一个根节点（如上图所示的A结点。空树可以没有），每一个结点都可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前趋（即一个叶子结点不能有两个根）。
结点的度：一个根节点拥有的叶子数量称为度（degree）。
叶子结点：度为0的节点称为叶子结点或终端节点。（如上图所示的H/E/F/G结点）
非终端结点：度不为0的节点称为非终端结点或分支结点。
树的度：是树上所有结点的度的最大值。
父节点：所有非叶子结点都是父节点，即度大于0的结点就是父结点。
子节点：父结点的直接后继称为子结点。同一个父结点的多个直接后继结点之间称为兄弟。
子孙：树上的非根结点都是根结点的子孙。
树的层级：从根结点开始，根为第一层，根的孩子在第二层，依次类推。树上结点的最大层次称为树的深度或高度。
有序树和无序树：若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树(Ordered Tree)；否则称为无序树(UnorderedTree)。
深林：m（m>=0）棵互不相交的树的集合。

二、二叉树的概念和重要特征

每个结点最多有两个子树的有序树被称为二叉树（即树上所有结点的度<=2），二叉树的子树有左右之分，其次序不能任意颠倒。

二叉树的性质：

1、 二叉树的第i层上最多有$2^{i-1}$个节点（i>=1）
2、 深度为k的二叉树最多有$2^k-1$个结点（k>=1）
3、 任何一棵二叉树T，如果其终端结点数为$n_0$，度为2的结点树为$n_2$，则$n_0=n_2+1$。
满二叉树：一棵深度为k且有$2^k-1$个结点的二叉树称为满二叉树。满二叉树的所有分支结点都有左子树和右子树，所有叶子结点都在最下层，每一层上的结点数量都达到最大的结点数。

完全二叉树：如果二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

4、 具有n个节点的完全二叉树的深度是$[log_2n]+1$
5、 如果对一棵有n个节点的完全二叉树按照层序编号（从上到下，从左到右），如果i=1，即为根节点。如果i>1，其父节点=[i/2]。如果2i>n，则节点i为左孩子，反之，其左孩子是节点2i。如果2i+1>n，则节点i无右孩子，反之，其右孩子是节点2i+1。

三、二叉树的存储结构

顺序存储结构

链式存储结构

typedef  struct  Node
{
    DataType  data；
    struct  Node  *lchild, *rchild;  //如果有必要，还可以增加一个指向父节点的指针
}Node,  *Node;

四、二叉树的遍历方式

1、 前序遍历：顺序是：先父节点->左孩子（递归）->右孩子（递归）

2、 中序遍历：从左子树的叶子节点开始。顺序是：左孩子（递归）->父节点->右孩子（递归）

3、 后续遍历：从左子树的叶子节点开始。顺序是：左孩子（递归）->右孩子（递归）->父节点

4、 层序遍历：从上到下，从左向右

线索二叉树：

哪怕是满二叉树，末端的叶子节点因为没有左右孩子，它们的指针域为空。对于其它的二叉树，空指针域可能更多。因此，从某些角度看，保存左右孩子信息的二叉树数据结构的空间效率不足。
按照某种遍历方式对二叉树进行遍历，可以把二叉树中所有结点排序为一个线性序列。在该序列中，除第一个结点外每个结点有且仅有一个直接前驱结点；除最后一个结点外每一个结点有且仅有一个直接后继结点。这些指向直接前驱结点和直接后续结点的指针被称为线索（Thread），加了线索的二叉树称为线索二叉树。
【注意：线索链表解决了直接查找某结点的前趋和后继节点的问题，但出现了查找左、右孩子困难的问题。】
为了支持线索指针，线索二叉树节点结构中需要增加两个标志位表示指针域是线索还是孩子。

五、二叉树的典型应用

赫夫曼树（也称为最优二叉树）

1、基本概念

1、 路径和路径长度：树上一个结点到另一个结点的每一段分支组成了结点之间的路径。路径中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
2、 二叉树的路径长度：从二叉树的根节点到树的所有叶子节点的路径长度之和。
3、 结点的权及带权路径长度：如果对树的各个结点赋值，这个数值就被称为结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点权值的乘积。
4、 树的带权路径长度：为所有叶子结点的带权路径长度之和，记为WPL

如上图所示，
图（a）的WPL=7x2+5x2+2x2+4x2=36；
图（b）的WPL=7x3+5x3+2x1+4x2=46；
图（c）的WPL=7x1+5x2+2x3+4x3=35。
其中，图（c）所表示的树就是哈夫曼树，即带权路径长度最短的树（权值较大的结点离根更近）。

2、如何构建哈夫曼树

1、 把具有权值的节点按照从小到大的顺序排列。
2、 取出头两个结点作为左，右子树（注意，左子树的权值应小于右子树的权值）生成一棵新的树，同理新树需要生成一个新的根节点，且根节点的权值为这两个结点权值之和。
3、 找出剩余结点中权值最小的结点与第2步生成新生成的根节点比较，并重复第2步的动作；以此类推，直到森林中只有一棵树为止，此树便是哈夫曼树。【注意，在比较的过程中可能会出现新生成节点的权值与已有节点的权值相等的情况，此时应该优先选择新生成的节点】

3、赫夫曼树的应用

赫夫曼编码（数据传输过程中的两个重要原则：所有字符编码必须唯一，字符编码尽量短），通常情况下有两种编码方式：
1、等长编码，即所有字符的编码长度相同，这种方式比较容易保证编码的唯一性，但是无法保证长度最短。
2、变长编码，找出高频字符和低频字符，高频字符用短编码，低频字符用长编码，最终达到整体传送数据最短的原则。存在的问题，如何保证接收端区分短编码和长编码。具体的解决方案就是赫夫曼编码。（思想原则：每个字符的编码都不是同一字符集中另一个字符编码的前缀）

4、实现赫夫曼编码

1、 按照字符出现的频率作为权值构造赫夫曼树
2、 从根结点开始，为到每个叶子结点路径上的左分支赋予0，右分支赋予1，并从根到叶子方向形成该叶子结点的编码。

二叉排序树和平衡二叉树

二叉树排序的特征是：左子树<父节点<右子树，它主要用于动态查找表。动态增删二叉树排序树上结点的过程中，能够保持自平衡的又被称为平衡二叉树（AVL），STL模板库中的map、set中大量使用了这种平衡二叉树。