先来做个小复习
上一课咱们了解了初阶的“数据结构”共有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 集合之间的操作:求交集/并集/求差等等。
集的应用也很广泛,比如数独游戏算法中,可以使用集来管理每个小单元格的候选数列表。