树2019.3.13

参考资料：数据结构与算法，解学武，http://data.biancheng.net/
个人记录重要的笔记，非全原创，有copy部分。

基本知识

• 一对多的关系
• 树是由根结点和若干棵子树构成的。

一些定义

• 父结点（双亲结点）、子结点和兄弟结点
• 根结点：每一个非空树都有且只有一个被称为根的结点。
  树根的 判断依据为：如果一个结点没有父结点，那么这个结点就是整棵树的根结点。
• 叶子结点：如果结点没有任何子结点，那么此结点称为叶子结点（叶结点）
• 空树：如果集合本身为空，那么构成的树就被称为空树。空树中没有结点。
• 子树：略
• 度（深度、高度）：对于一个结点，拥有的子树数（结点有多少分支）
• 层次：树根为第一层，根的子节点为第二层，以此类推。
  一棵树的深度（高度）是树中结点所在的最大的层次。
• 森林：由 m（m >= 0）个互不相交的树组成的集合。

树的几种表示形式：

• 树最常用的表示方法是使用广义表的方式

二叉树

性质：

1. 二叉树中，第 i 层最多有 2i-1 个结点。
2. 如果二叉树的深度为 K，那么此二叉树最多有 2K-1 个结点。
3. 二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1。

满二叉树

• 如果二叉树中除了叶子结点，每个结点的度都为 2。
• 通俗地说 每层都是满的，没有缺。

满二叉树特性

1. 满二叉树中第 i 层的节点数为 2n-1 个。
2. 深度为 k 的满二叉树必有 2k-1 个节点 ，叶子数为 2k-1。
3. 满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
4. 具有 n 个节点的满二叉树的深度为 log2(n+1)。

完全二叉树

除去最后一层以外每一层都是满的，且最后一层的结点依次从左到右分布。

完全二叉树特性

1. n 个结点的完全二叉树的深度为 ⌊log2n⌋+1。
2. 对于任意一个结点 i ，当 i>1 时，父亲结点为结点 [i/2] 。（i=1 时，表示的是根结点，无父亲结点）
3. 如果 2*i>n（总结点的个数） ，则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2*i 。
4. 如果 2*i+1>n ，则结点 i 肯定没有右孩子；否则右孩子是结点 2*i+1 。

存储结构

顺序存储（针对完全二叉树）

• 如果我们想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树。
• 满二叉树也是完全二叉树的一种。
• 完全二叉树的顺序存储仅需从根节点开始，依次将树中节点存储到数组即可。

链式存储

1. 节点结构由 3 部分构成
   指向左子节点的指针（left）；
   节点存储的数据（data）；
   指向右子节点的指针（right）；

四种遍历算法

先序遍历

先序遍历的实现思想是：

1. 访问根节点；
2. 访问当前节点的左子树；
3. 若当前节点无左子树，则访问当前节点的右子树；
   
   图 中二叉树采用先序遍历得到的序列为：
   1 2 4 5 3 6 7

中序遍历

中序遍历的实现思想是：

1. 访问当前节点的左子树；
2. 访问根节点；
3. 访问当前节点的右子树；

图中采用中序遍历得到的序列为：
4 2 5 1 6 3 7

后序遍历

后序遍历的实现思想是：
从根节点出发，依次遍历各节点的左右子树，
直到当前节点左右子树遍历完成后，才访问该节点元素。

图 1 中二叉树进行后序遍历的结果为：
4 5 2 6 7 3 1

层次遍历

实现思想：
通过使用队列的数据结构，从树的根结点开始，依次将其左孩子和右孩子入队。
每次队列中一个结点出队后，都将其左孩子和右孩子入队。
直到树中所有结点都出队。

输出结果：1 2 3 4 5 6 7

普通树

存储结构

双亲表示法

• 采用顺序表（也就是数组）存储普通树
• 核心思想是：顺序存储各个节点的同时，给各节点附加一个记录其父节点位置的变量。
• 适合用于查找父节点。

孩子表示法

• 采用的是 “顺序表+链表” 的组合结构
• 存储过程：从树的根节点开始，使用顺序表依次存储树中各个节点，同时每个节点都会拥有一个记录其子节点的链表。
• 适用于查找某结点的孩子结点，不适用于查找其父结点
• 双亲表示法和孩子表示法可以组合，父节点和子节点都容易查询 。

孩子兄弟表示法

• 采用的是链式存储结构

• 实现思想：从树的根节点开始，依次用链表存储各个节点的孩子节点和兄弟节点。

• 节点组成：
  

  1. 节点的值；
  2. 指向孩子节点的指针；
  3. 指向兄弟节点的指针；
     

• 即通过孩子兄弟表示法，任意一棵普通树都可以相应转化为一棵二叉树。
  即，任意一棵普通树都有唯一的一棵二叉树于其对应。

• 孩子兄弟表示法可以作为将普通树转化为二叉树的最有效方法，通常又被称为"二叉树表示法"或"二叉链表表示法"。

哈夫曼树

名词解释

• 路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径
• 路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。
• 结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。
• 结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。

定义

• 二叉树的一种，也叫“最优二叉树”。
• 当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小
• 权重越大的结点离树根越近。

构建哈夫曼树

对于给定的有各自权值的 n 个结点，构建哈夫曼树的办法：

1. 在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树
2. 新二叉树的根结点的权值为左右孩子权值的和；
3. 在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；
4. 重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。
   

• 哈夫曼树的构建是从叶子结点开始，不断地构建新的父结点，直至树根，所以结点中应包含指向父结点的指针。
• 但是在使用哈夫曼树时是从树根开始，根据需求遍历树中的结点，因此每个结点需要有指向其左孩子和右孩子的指针。

最优二叉树的查找算法

查找权重值最小的两个结点，思想是：

1. 从树组起始位置开始，首先找到两个无父结点的结点（说明还未使用其构建成树），然后和后续无父结点的结点依次做比较
2. 有两种情况需要考虑：
   • 如果比两个结点中较小的那个还小，就保留这个结点，删除原来较大的结点；
   • 如果介于两个结点权重值之间，替换原来较大的结点；

哈夫曼编码

• 哈夫曼编码是在哈夫曼树的基础上构建的，这种编码方式最大的优点就是用最少的字符包含最多的信息内容。
• 根据发送信息的内容，通过统计文本中相同字符的个数作为每个字符的权值，建立哈夫曼树。
• 对于树中的每一个子树，统一规定其左孩子标记为 0 ，右孩子标记为 1 。
• 用到哪个字符时，从根结点开始，依次写出经过结点的标记，最终得到的就是该结点的哈夫曼编码。
• 文本中字符出现的次数越多，在哈夫曼树中的体现就是越接近树根，编码的长度越短。
• 案例：下图中：
  字符 a 用到的次数最多，其次是字符 b 。字符 a 在哈夫曼编码是 0 ，字符 b 编码为 10 ，字符 c 的编码为 110 ，字符 d 的编码为 111 。
  

求哈夫曼编码的两种方法

1. 逆向：从叶子结点一直找到根结点，逆向记录途中经过的标记。但要记得所得的结果要逆序输出。
2. 正向 从根结点出发，一直到叶子结点，记录途中经过的标记。

回溯法

• 又被称为“试探法”。
• 解决问题时，每进行一步，都是抱着试试看的态度，如果发现当前选择并不是最好的，或者这么走下去肯定达不到目标，立刻做回退操作重新选择。
• 回溯和递归唯一的联系就是，回溯法可以用递归思想实现。
• 回溯法的求解过程实质上是先序遍历“状态树”的过程。

回溯法解决八皇后问题

• 八皇后问题是使用回溯法解决的典型案例。
• 解决思路是：
  1. 从棋盘的第一行开始，从第一个位置开始，依次判断当前位置是否能够放置皇后，判断的依据为：同该行之前的所有行中皇后的所在位置进行比较，如果在同一列，或者在同一条斜线上（斜线有两条，为正方形的两个对角线），都不符合要求，继续检验后序的位置。
  2. 如果该行所有位置都不符合要求，则回溯到前一行，改变皇后的位置，继续试探。
  3. 如果试探到最后一行，所有皇后摆放完毕，则直接打印出 8*8 的棋盘。
  4. 最后一定要记得将棋盘恢复原样，避免影响下一次摆放。

N个节点能够构成多少种树

• 由于普通树能够用孩子兄弟表示法转化成二叉树，则本问题等同于【n 个结点可以构建多少种形态不同的二叉树】。
• 每一棵普通树对应的都是一棵没有右子树的二叉树。所以对于 n 个结点的树来说，树的形态改变是因为除了根结点之外的其它结点改变形态得到的，所以，n 个结点构建的形态不同的树与之对应的是 n-1 个结点构建的形态不同的二叉树。
• 如果 tn 表示 n 个结点构建的形态不同的树的数量，bn 表示 n 个结点构建的形态不同的二叉树的数量，则两者之间有这样的关系：
  t_n=b_n-1

方法一：递推

方法二

略，累了，以后看吧。
http://data.biancheng.net/view/34.html