离散数学 第七单元 tree
目录
树的定义
树的特点
Spanning Tree 生成树（重要！）
生成树算法
DFS 深度优先
BFS 广度优先
Minimun Spanning Tree 最小生成树
Kruscal算法
Prim算法
根树
根数的遍历
前序遍历
中序遍历
后序遍历
表达式的二叉树
中缀形式
前缀形式
编辑后缀形式
最优树
树的定义
树：连通而不含回路的无向图
叶子：度数为1的节点
分支点：度数大于1的节点
树的特点
Spanning Tree 生成树（重要！）
生成树算法
这种算法不好用！详见DFS和BFS，better
DFS 深度优先
BFS 广度优先
Minimun Spanning Tree 最小生成树
Kruscal算法
选取的边数等于节点数-1时，选取完成！ 比如一个图有12个节点，那你选到11条边就ok
1. 选出权值最小的边，权值最小为1，发现只有ef为1，画上
2. 选出权值为2的边。。
3. 选出权值为3的边。。
（以此类推，选边的个数小于节点数-1即可，注意只要选的边不会出现回路就可以）
蓝色为选取边，最后卷面上列个表即可
Prim算法
蓝色的是选取的边。看样子，最后要把选了哪些边列个“表”
根树
根数的遍历
前序遍历
中序遍历
后序遍历
表达式的二叉树
中缀形式
前缀形式
后缀形式
（我有个想法就是，中序和后序都先转化为二叉树，再用中序写表达式计算会怎么样。。）
