树与二叉树

[yangsirgo]

树与二叉树的特性

1. 结点的度：一个结点的子树的个数记为该结点的度。
2. 叶子节点：也称为终端结点，指度为0的结点。
3. 内部结点：指度不为0的结点称为分支节点或非终端节点。除根结点之外，分支结点也称为内部结点。
4. 结点的层次：根为第一层，根的孩子为第二层，依次类推，若某节点在第i层，则其孩子结点在第i+1层。
5. 树的高度：一颗树的最大层次数记为树的高度（深度）。

二叉树特性

1. 在二叉树的第I层上最多有 2^（i-1）个结点（i≥1）
2. 深度为k的二叉树，最多有多少个结点 2^k-1（i≥1）
3. 对任何一颗二叉树，如果其子结点树为n0，度为2的结点数为n2，则n0=n2+1；
4. 如果对一颗有n个结点的完全二叉树的节点按层序编号，对任一节点i（1≤i≤n），有：
   • 如果i=1，则结点i无父结点，是二叉树的根；如果i>1，则父结点是L i/2 ˩ ；
   • 如果2i>n，则结点i为叶子结点，无左子结点；否则，其左子结点是结点2i；
   • 如果2i+1>n，则结点i无右子叶点，否则，其右子结点是结点2i+1。

别记了 到时候算吧。

特殊的树

1. 二叉树：二叉树是每个结点最多有两个孩子的有序数，可以为空树，可以只有一个结点。

2. 满二叉树（full binary tree 满的二叉树）：任何结点，要么是叶子结点，要么是恰有两颗非空子树。

3. 完全二叉树（complete binary tree 完整的二叉树）：除了底下一层，上面的是满二叉树，底下的一层是从左到右排列的，左边的节点都是满的，缺的只是右边的节点。从上到下按序列数，正好能序列上，没有缺数，就是完全二叉树。官方的定义（最多只有最小面的两层结点的度可以小于2，并且最下面一层的结点全都集中在该层左侧的若干位置）。 备注： 完全二叉树是满二叉树最后一层少若干个右子节点。 满二叉树是完全二叉树。完全二叉树不是满二叉树。

4. 查找二叉树（排序二叉树）：任何一个节点的权值，大于其左孩子结点，小于其右孩子结点。提升查找效率。

5. 最优二叉树（哈夫曼树）： 它是一类带权路径长度最短的树。

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

6. 线索二叉树：在每个结点中增加两个指针域来存放遍历时等到的前驱和后继信息。优化遍历的效率。

7. 平衡二叉树：树中任一结点的左右树高度之差不超过1。每个结点的平衡度只能为-1,1，或者0（对于叶子结点，平衡度都是0；因为左子树为0，右子树也为0，相减呢是0） 示意图： 快速记忆：防止树不要太斜了，也就是两个子树高度差不要太大。

   • 排序二叉树会有多种，平衡度比较好的遍历的效率高，看如下的图片例题：

树的遍历

遍历时按某种策略访问树中的每个结点，且仅访问一次的过程。

1. 前序遍历（先序遍历）：根左右遍历

2. 后序遍历：左右根遍历

3. 中序遍历：左根右遍历 前中后指的是根所在的位置。遍历按一个根节点和两个爷子节点为整体处理。 已知先序遍历结果和后序遍历结果，无法推断中序遍历结果，因为无法将左子树节点和右子树节点区分开。

4. 层序遍历：自上而下，自左向右依次访问各层级节点（高度一致的节点）。

[yangsirgo]

完全二叉树，高度h与节点的个数n的关系是log2n+1。log2n是2的几次方等于n。

[yangsirgo]

哈夫曼树的构造

1. 数列（给定的权值集合）中取出最小的两个数（权值），构造一颗字数作为其孩子节点，，二者全职之和作为根节点。
2. 在数列中删除这两个数（权值），并引入根节点的权值取代。
3. （1）（2）步骤连续。直到原权值结合为空。
4. 整理树：从左到右，大小排列树，变成排序二叉树。
5. 严格按这个步骤处理，注意每次取两个值。

哈夫曼编码

哈夫曼树的边长进行编码，编码长度与路径长度相关，左侧分支编码为0（或1），右侧分支编码为1（或0），从根节点到对应的叶子节点所有路径分支编码记录下来，即为叶子节点的编码。 备注： 树需要排序好，变成排序二叉树

[yangsirgo]

大顶堆，小顶堆，是完全二叉树。 堆排序最大的特点是按大小快速的排列出前几位。