先来做个小复习

上一课咱们了解了初阶的“数据结构”共有4种——

数组/链表/堆栈/队列

它们都是线性表。

堆栈和队列在形式上如同数组或链表一样，但是分别加入了“后进先出”和“先进先出”的规则。数据结构并不是一成不变规定好的，其实是可以根据需要灵活使用的，甚至可以自己发明适合使用的数据结构。

还有4种高阶数据结构

分别是：

树（Tree）

集（Set）

映射（Map）

图（Graph）

这些数据结构就不是“线性”的了，不如线性表那么常用，可是一旦使用，将发挥惊人的威力。

高阶数据结构不仅维护数据，还需要维护数据与数据之间的关系。

树（Tree）

树，是一种善于表达数据之间“层次关系”的数据结构，废话不说，先来个图片看看——

树结构

这就是一颗典型的“树”，还挺像生活中的树吧，只不过是倒过来的哈。

看着上图，我们讲解一下树上的节点名称：

1 每个圆圈的位置称为“节点”；

2 在节点上方且用线相连的，叫“父节点”；在节点下方且用线相连的，叫“子节点”；

3 如果平级的就叫“兄弟节点”，形象吧，比如 G H I 就是兄弟节点。

再看一遍这个树结构，它有3个特征：

1 有一个节点 A，它没有父节点，我们叫 A 为“根节点”；

2 每个节点有0个/1个/2个/n个子节点，但每个节点只有一个父节点；

3 树是有“高度”的，有几个层次高度就是几，比如上面结构中高度为4。

看到这里，我们完全可以把树结构看成是一种“家谱图”。

树结构怎么存储

其实树结构的存储方式很多，比如父节点法/子节点法/孩子兄弟法等，但它们的原理都是一样的：

每个节点都有一个数据域和一个指针域。

上例子：

父节点法简明图解

比如上图就是典型的父节点法，首先定义好下标的顺序，这其实也是数据域在数组中的下标，然后每个节点都有一个指针域parent，根节点指向-1，意思是它没有父节点；E节点的指针为2，而2对应的是C，意思是：E节点的父节点是C。

树中之王——“二叉树”

树结构特别擅长表示层次结构，比如计算机上的目录结构/一个公司的分支机构等等，而有一种特殊的树，结构更简单，用处却更大，它就是——

“二叉树”。

二叉树的形状

上图就是二叉树的形状，就是每个节点最多只有两个儿子。

二叉树分两类：

完全二叉树 与 不完全二叉树。

两类二叉树

从上图中的顺序存储形式来定义再好不过了，如果顺序存储形式中都存满了数，即“完全”；如果有空位，就是“不完全”。

树的讲究太多了，应用也广泛，我们后面再更详细地讲解。

集（Set）

集，也叫“集合”，跟咱们数学上说的集合完全是一回事，就是把一堆元素放在一起的总合。

严谨点儿说，集有3个特点：

1 无序

集里面的元素没有先后顺序，地位平等，不像树那样还会有父子关系；

2 互异

集里面的元素，必须没有重样的；

3 明确

一个对象，要么属于这个集，要么不属于，没有中间情况。

集合中每个元素必须互异

集的操作

集有哪些操作？

1 对集中元素操作：插入元素/删除元素/判断元素是否在集中；

2 集合之间的操作：求交集/并集/求差等等。

集的应用也很广泛，比如数独游戏算法中，可以使用集来管理每个小单元格的候选数列表。