9
20240616过几天就考试周了才开始讲树。。。
基本概念
无简单回路的连通无向图叫树，无简单回路的无向图叫森林，任意两个结点均存在唯一简单道路的无向图也叫树，等价的
指定某个结点为根，由此边可以有方向了，这样的树叫根树 rooted tree，由此有了儿子，兄弟，祖父，子孙、父亲、叶子、内部、子树等概念
结点的 level 即根到结点的简单道路长度，即层数，树的 height 即最大的 level
(full) m-ary tree，即 m 叉树，full 就是儿子满了
ordered rooted tree，即每个内部结点的儿子有顺序，可以分为左儿子、右儿子，左子树、右子树
满足AVL树要求的树就是 balanced 的
ordered 2-ary rooted tree 就是我们在fds、ads里面所谓的二叉树了
一些性质：
- 树的顶点比边多1个，即 root
- 含有 i 个内部结点的满 m 叉树的顶点数为 n=mi+1，多一个是 root
- 设 l 是叶子数，n为总结点数，我们有：
二元一次方程组的解罢了，没必要记
- m 叉树最多有 \(m^h\) 个叶子，废话，反过来 \(h\ge [log_ml]+1\) ，也是废话
引入
BST略，复杂度正比于高度，高度受节点数约束
前缀码
prefix code，我们希望给每个字母一串二进制数，为了避免一长串二进制数能解码出不同的字母组合，我们用前缀码编码
前缀码即任一的编码都不会称为其它编码的前缀
例如，0，10，110，1110，1111
前缀码可用哈夫曼树表示并优化
使用频率越高的字母放在越上面即可优化
生成树
从一个图生成包含所有结点的连通且不带回路的子图即为生成树
简单图是连通的当且仅当其有生成树
可以用DFS构造生产树，DFS也叫backtracking
死去的ADS开始攻击我，不对，前天才刚复习完ADS
生成树也可以用BFS生成
最小生成树
最小生成树是指边权重和最小的生成树
我们可以用Kruskal或Prim算法构造，他们都是贪心算法，即每一步决策都只选最优的策略
设有一个图里有 n 个点
Kruskal算法每轮选所有边中权重最小的边加入解集，检测有无回路生成，有则撤回，不再考虑这条边，加到 n-1 条边位为止
Prim算法则是先选最小的边，每轮从相邻边中选最小的加入解集，检测有无回路生成，有则撤回，不再考虑这条边，加到 n-1 条边位为止
完结撒花~202406191453于紫金港玉湖7幢b407研讨室