登录以参加训练计划

树

树也是图的一种，不过树可以用来干更多事情，衍生的算法也很多。树有一种特性，便是只有 $n$ 个点，$n-1$ 条边。这使得树可以用多种方法构建。

树的构建方式

1. 直接构建

可以用图的方式构建树，不会受到其他影响。一般来说用邻接表构建，遍历方式就是做深搜，枚举从除父节点之外的子节点，直到遍历完整个树。

2. 链表构建

用链表连接父节点与子节点。可以放心遍历，遍历起来也比较简单（针对二叉树），不过初始化很复杂，不建议使用。

树的遍历

树有三种遍历方式，分别是前序遍历、中序遍历、后序遍历。前序遍历的遍历方法是根->左->右，中序是左->根->右，后序是左->右->根。遍历方式的题目一般考初赛，就是通过某前/后序遍历与中序遍历，得后/前序遍历。

树的变形

树的变形也很多，比如哈夫曼树、二叉搜索树等。

哈夫曼树

哈夫曼树也是初赛重要考点，难度较高，也十分抽象。构建方式就是取一串数，把两个最小的数合并成一个树，左节点小，右节点大，根节点便是这两个数的和。通过多次合并，最终将两个大节点合并，成为一个完整的树。至此，那些用的频率较高的东西可以用短的编码，用的频率较低的东西可以用长的编码，提升了数据存储和传输效率。

二叉搜索树

二叉搜索树顾明思议，就是父节点有最多两个分支，可以搜索某个数字的树。假如说 $6$ 是根节点，那么当要存储 $8$ 的时候，便将 $8$ 移到右侧；当要存储 $4$ 的时候，便将 $4$ 移到左侧。也就是说，大的数往右移，小的数往左移。这样做可以快速知道每个节点的位置，平均时间复杂度 $O(logn)$。当然最差的时间复杂度为 $O(n)$ ，优化需要用到Splay树等知识点，属于高阶算法。

当然，树还有许多衍生的算法，不过难度较高，如树形dp等。它们属于提高组算法，不在普及组范围内。