你好，我是王健伟。 这节课我们接着讨论删除黑色叶子节点导致的红黑树平衡性调整问题。现在还有一种情况我们没有讨论到，那就是待删节点的父节点为黑色，兄弟节点也为黑色且兄弟节点不待任何孩子节点的情况。 随着我的讲解，你也可以回想上节课的思考题，看一看你想到...

你好，我是王健伟。 前面我们已经讲过了很多种二叉树，这节我想再和你分享一种特殊的二叉树——哈夫曼树（Huffman Tree）。 哈夫曼树也有人称为霍夫曼树或最优二叉树。先说点有趣的，哈夫曼（David Huffman）是美国的一位数学家。他在195...

你好，我是王健伟。 前面我们讲过了各种二叉树，这方面的知识已经够多的了，本节就来讲一讲更通用的概念：树、森林以及与二叉树之间的转换问题。 树的存储结构前面我们学习了树形结构的基本概念，在满足这个概念的前提下，一棵树可以有任意形状，可以有任意多的孩子，...

你好，我是王健伟。 经过了长期努力，我们一起学习了树相关的知识。树是整个课程中占据篇幅最大的话题，也是面试和使用中的热门话题。而这一次，我们来说一说图。 图这种数据结构比树更加复杂。我们回想一下，树形结构中的节点或者说数据之间有明显的层次关系，一个父...

你好，我是王健伟。 对于图这个话题，我们要解决的第一个问题是要把图存储起来，也就是图的存储结构问题。 首先要说的是，对于图来讲，顶点位置是个相对概念，任何一个顶点都可以看成第一个顶点，这个点的邻接点之间也不存在次序关系。所以对于图的存储是需要一些特殊...

你好，我是王健伟。 上节课我们讲解了用邻接矩阵、邻接表、十字链表进行图的存储，他们都有各自的优点、局限性和所适用的场景。这节课，我就带你学习另外两种图的存储结构，分别是邻接多重表和边集数组。 邻接多重表邻接多重表是存储无向图的另一种链式存储结构。换句...

你好，我是王健伟。 上节课我们讲述了邻接矩阵、邻接表、十字链表、邻接多重表、边集数组共5种数据结构，解决了对图进行存储的问题。接下来的问题， 就是对图进行遍历了。 所谓图的遍历，就是指从图中任意一个顶点出发访遍图中其余顶点，且使每个顶点都被访问且只被...

你好，我是王健伟。 前面我们已经讲解了图的概念、图的存储结构以及图的遍历问题。那么你可能非常想知道图都有哪些具体的实际用途。这节课，我就和你分享图的第一个实际用途——最小生成树。 首先我们先一起看一看什么是最小生成树。 最小生成树前面我们曾经展示过生...

你好，我是王健伟。 上节课我带你实现了用普里姆算法寻找一个无向连通图的最小生成树，并且我们已经知道，普里姆算法比较适合顶点数比较少，边数比较多的图。 这节课我带你看一看另外一种寻找无向连通图最小生成树的方法——克鲁斯卡尔（Kruskal）算法。话不多...

你好，我是王健伟。 前面我们讲解了用普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法来寻找连通图的最小生成树，从而解决诸如如何修路费用最少这样的问题。这次我和你分享图的第二个实际用途——最短路径。那么，什么是最短路径呢？ 最短路径在带权图中，...