最优二叉树(赫夫曼树)
首先我们来看一个伪代码。这个是代表成绩的等级。 然后我们知道，每一次高考，学生的成绩分布应该接近某个比例，现在我们假如分别规律如下： 为此可以作出下面的这个树。 我们发现，概率分布主要是在70-79,80-89之间，如果有很多数据要比较，那...
算法笔记-ag真人官方网
图的存储结构(邻接表)
为什么要采用邻接表： 对于边数相对顶点较少的图，这种结构无疑是存储空间的极大浪费。 所以把数组和链表结合起来存储，这种方式在图结构中适用，称为邻接表（adjacencylist） 邻接表的处理方法如下： -顶点用一个一位数组存储（也可以用单...
图的存储结构(邻接矩阵)
邻接矩阵（无向图） 因为图是由顶点和边或弧组成的，所以最好是把他们分开存储。 下面来看无向图的邻接矩阵。 图的邻接矩阵（adjacency matrix）存储方式是用两个数组来表示图。 如下图所示： 由上图可以很明显的看出0表示不存在顶点间...
拓扑排序
一个无环的有向图称为无环图（directed acyclic graph），简称dag图。 在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称之为aov网（active on ver...
关键路径
aoe网：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为aoe网（activity on edge network）。 如下图所示： aov网与aoe网...
最短路径(迪杰斯特拉算法)
例如，要求下图v0到v8的最短路径 所以我们可以找到这样的一条最短路径 下面是他的邻接矩阵： 伪代码如下： #define maxvex 9 #define infinity 65535 typedef int patharc[maxvex...
最短路径(弗洛伊德算法)
迪杰特斯拉算法求的是一个顶点到所有顶点的最短路径，但弗洛伊德算法是求所有顶点到所有顶点的最短路径。 首先，来看下面这个简单的图： 我们把他的邻接矩阵和初始化的p做出来，如下图所示： 代码如下： #define maxvex 9 #defin...
树、森林、二叉树的转换
树转换成二叉树： 1.在树中所有的兄弟结点之间加一连线。 2.对每个结点，除了保留与其长子的连线外，去掉该结点的其他孩子连线。 如下图所示： 下面是森林转化二叉树： 1.先将森林中的每棵树变为二叉树。 2.再将各二叉树的根结点视为兄弟从左至...
平衡二叉树的实现原理
已经下面的这个数列 则构造的二叉树为： 下面把这个二叉树转为平衡二叉树： 如下图所示： 最后结果如下图：
二叉排序树的删除操作
先来看这个二叉排序树 下面是讨论删除的情况： 我们知道，如果要删除的叶子结点，则可以直接删除。 但如果删除的不是叶子结点呢？ 我们知道这个树的中序遍历如下： 也就是说，比如要删除105，则我们可以把104，或108提上去覆盖掉，这样实现了删...