二叉搜索树：中序遍历的前驱后继结点

二叉排序树：可能退化成链表

平衡二叉树（AVL）:每个结点左右子树高度差不超过1

哈夫曼树：带权最短路径WPL最小的二叉树 ，就是让权值越大的路径越短（可用于数据压缩）

最小生成树

普利姆（prim）算法:每次维护一个联通集（已构造好的），然后每次加入距离最短的结点，同时更新剩余结点的联通集（通过新加入的结点让距离更小）—适合顶点多

库鲁斯卡尔（Kruskal）算法：把edge全部排好序，每次找最短的边连起来，通知保证不构成环。—适合边少

最短路径

单源：迪杰斯特拉（Dijkstra）:每次找到最近的结点，并更新v0到该节点的最短路径(若通过新结点更近)。O(n2)

若想要找到所有结点之间的最短路径，则要再一次迪杰斯特拉（Dijkstra）算法，此时时间复杂度O(n3)

多源：弗洛伊德（Floyd）算法：三重循环（k,v,w），如果更过下标k能让v-w的路径更短，则更新vw的路径。

参考文章

评论可见，请评论后查看内容，谢谢！！！评论后请刷新页面。