树

小朋友都知道没有环的连通图就是树，而多个树在一起就是森林，度数为 $1$ 的点叫叶结点，简称就是叶 ( •̀ ω •́ )y

和赋权图一样，也有赋权树这种东西，就是树上的边多了数字

种一棵树

如果有一个图，它端点一个不少得到的权值最小的树叫做它的最小生成树

专家给了两种求一个图的最小生成树的方法：避圈法和破圈法

避圈法是从最小的边开始选，如果选了会成环就不选那条，直到选到 $n-1$ 条为止，选中的边就能组成最小生成树

破圈法是从最大的边开始删，如果选了会断开就不选那条，直到剩下 $n-1$ 条为止，剩下的边就能组成最小生成树

有方向的树

有向树就是没有环的有向图，入度为 $0$ 的叫根节点，入度出度都为 $1$ 的叫叶节点

如果一颗有向树只有一个根节点，那它就是根树，也是平常见到最多的树，从根到别的结点的通路长度叫做那个节点的层数，树的最大层数叫做树高，记作 $h(T)$ ，如果每层的全部结点都规定了次序，这就是个有序根树，简称有序树

父亲、儿子、兄弟、祖先、后代这些概念应该一点就通

根树的结点和它的全部后代导出的子图叫做根子树，也叫子树

对于树的遍历，有三种方式，前序遍历，中序遍历和后序遍历

这个前中后啊，指的是根与它的子树的遍历次序

前序遍历就是先看根，再看子树；中序是先看一颗子树，再看根，再看别的子树；后序就是先看完所有子树再看根

这些遍历都是要递归的

二叉的树

二叉树个个都见过，懒得重复定义了

有个东西叫前缀码，但是这玩意咋解释呢，就是一组看开头不会混淆的字符串吧

二叉树每个点当然也可以有赋值，如果一棵树只有叶有赋权，那这棵树叫叶赋权树，每个叶的值乘上它的层数之和就是这棵树的权值 $W(T^*)$ ，改变叶节点位置得到的权值最小的二叉树叫最优二叉树，亦称最优树或哈夫曼树

那咋求哈夫曼树呢？先挑出最小的两个点，给它们一个父亲，让父亲的值是两者之和，之后把父亲加入到未选择的点里面，然后再在所有未选择的点中选择最小的两个结为兄弟，同时再给一个父亲，重复直到所有点都在一棵树里面。

由最优树生成的前缀码又称最优前缀码或哈夫曼码

欸？树这章就这点东西吗，那为啥还要单开一章