C++实现树 - 08 并查集
写在前面：这一讲我们来讲一个非常实用的小技巧即并查集，一开始理解起来可能需要一点时间，但是它的实际代码其实非常的短，在后面的内容中我们也会用到。并查集定义并查集是一种非常精巧而实用的树形数据结构，他主要是处理一些不相交集合的合并和查询的问题。比如我给定一些数字并给定它们属于哪个集合，并且每次询问当中的两个数字时可以告诉我这两个数字是否处于同一个集合，这就是一个典型的并查集问题。查找我们可以利用一....
C++实现树 - 07 平衡二叉树
写在前面：这一讲我们来讲讲目前为止难度最大的一种树，当然后面要有 B 树、B+ 树和红黑树等着我们。同样，我会将详细的代码附到详解的最后。平衡二叉树的定义我们之前学了二叉排序树，但是二叉排序树存在一个致命的问题，如果我每次插入的值都比上一次插入的大，那它就会形成一个斜树，这对我们的查找删除等功能影响很大。我们经过平衡操作就可以得到这样一颗树（具体如何操作下面会讲到）：所以平衡二叉树就由此诞生了，....
C++实现图 - 01 图的概述及实现
写在前面：前面我们讲的数据结构都是针对于一对一或一对多的情形，如果涉及到多对多的复杂情况就要用到我们接下来讲解的图了，这一讲我们重点讲解邻接表、邻接矩阵、十字链表以及邻接多重表的代码实现。如果已经对图的概念比较熟悉的小伙伴，可以拉到下面看相关的代码实现。图的概述图 G 是由两个集合 V 和 E 组成，记为 G = （V，E），其中 V 代表顶点，E 代表边，如下图（这里涉及到有向边和无向边，下面....
C++实现树 - 06 哈夫曼树编码
写在前面：这一讲我们来学习一个比较有趣的树 —— 哈夫曼树，在许多非常知名的算法里也出现了哈夫曼树，这一讲我们就好好来唠唠什么是哈夫曼树。前置概念概念一：什么是结点路径的长度从根结点到该结点的路径上的连接数。例如上图（下面将会用到），从结点 28 到结点 2 的连接数为 3 。概念二：什么是树的路径长度就是树的每个叶子结点的路径长度之和，上图的树的路径长度就为 3 + 3 + 3 + 3 + 1....
C++实现树 - 05 线索二叉树
写在前面：上一讲我们实现了代码量较大的二叉排序树，这一讲我们讲一个新的类型 —— 线索二叉树。这一讲代码量不多，但在理解上需要大家花一点功夫~思考在我们之前学到的树中可以发现，一个拥有 N 结点的二叉树，它一定有 N-1 条边是指向节点的即有效分支，但是有 2N-(N-1) = N+1 条边是指向空指针域的，这就导致了空间上的浪费。此外，当对二叉树进行中序遍历时可以得到二叉树的中序序列。如果所示....
C++实现树 - 04 二叉树的构建（数组）
写在前面：通过前面两讲的学习，大家可能对二叉树有了比较深的感悟，但可能会发现一个小问题，我们在构建二叉树的时候都是一个个插入的，非常的不方便。那么这节课我们就来看看，如何通过输入一个数组来快速构建起一个二叉树。这里会介绍通过顺序数组、前序数组和后序数组如何构建二叉树。完全二叉树的构建在前面的学习中，我们知道了完全二叉树有一个非常 nice 的性质，它每个结点的左孩子在数组中的位置等于 2x ，右....
C++实现树 - 03 二叉排序树
写在前面：上一讲我们介绍了二叉树的代码实现以及其遍历方法，这一讲我们来看一看进阶版的二叉树 —— 二叉排序树（二叉搜索树）。第一次接触这一讲知识点的朋友一时反应不过来不用太焦虑，其实是非常正常的，看讲解以及代码的同时动手画一画或者实现以下会让你更容易理解~性质二叉排序树它和普通的二叉树不同：（1）如果根结点的左子树不为空，那么它左子树的所有结点的值都小于根结点。（2）如果根结点的右子树不为空，那....
C++实现树 - 02 二叉树
写在前面：这一讲我们来看看二叉树的实现，还不清楚树的结构的小伙伴建议先看看上面一讲关于树的定义。二叉树的定义二叉树是每个结点最多有两个子树的树结构。也就是说二叉树不允许存在度大于2的树。它有五种最基本的形态：二叉树可以是空集。根可以有空的左自树或者右子树；或者左右子树都是空。其中只有左子树或者右子树的叫做斜树。二叉树的主要性质性质结论性质一在二叉树的 i 层上至多有 2 ^ ( i - 1 ) ....
C++实现树 - 01 树的三种表示法
写在前面：今天我们开始进入树的学习啦，在学习高级搜索树之前，我们先看看一些简单树的实现，先理解好概念，入门就很快了。另外，本讲将会为大家介绍双亲表示法、孩子表示法和孩子兄弟表示法的代码实现。树的定义之前我们学习的是线性表，也就是线性的存储结构。今天我们开始学习非线性的存储结构，树就是非线性的存储结构，它可以拥有一对多的元素。在学习代码之前，我们先弄明白下面这几个定义：结点： 使用树结构存储的每⼀....
C++实现线性表 - 06 队列（链表实现）
写在前面：上一讲，我们用的是数组来实现队列的功能，这一讲我们尝试用链表来实现，其实我认为链表实现比数组实现更容易理解一些。队列的插入书接前文，由于上一讲我们已经对队列的定义进行深入的讲解了，我们直接进入代码部分，同样我们也直接实现双端队列的功能。用链表进行操作其实就用到了之前我们讲的双向链表操作啦，对应到双端队列里就是左插入和右插入，左删除和右删除。为了方便，这里创建了头结点和尾结点，通过头结点....
本页面内关键词为智能算法引擎基于机器学习所生成，如有任何问题，可在页面下方点击"联系我们"与我们沟通。
开发与运维
集结各类场景实战经验，助你开发运维畅行无忧
+关注