知乎盐选会员精选文章抽象数据模型
我们介绍了两个序列数据结构，数组和链表。
关于数组和链表除了理论上的操作和约束，我们还讲了它们是如何对应到计算机内存的存储空间上去的。
之所以要讲到这个程度，是因为我们后面所有的代码都要用到这两个数据结构，而对代码中某些细节的理解要借助于对相应数据结构实现的认知，因此不得不讲到如此层面。
这一章我们要介绍两种相对复杂的数据结构：树和图。
鉴于本门课内并不会在代码层面涉及到这两种结构，我们仅讨论作为抽象数据类型的树和图。
NOTE：所谓抽象数据模型（ADT），指的是计算机科学中数据结构的数学模型或者语义。
抽象数据类型是纯粹的理论实体，仅定义其上可执行的操作以及这些操作的效果的数学约束，而不涉及到具体的实现。
抽象数据类型方便用来简化描述算法，也便于初学者理解复杂数据结构。
树和图的数学理论基础都是图论（Graph Theory）。
图
图论中的图
在图论中，图是一种由一个对象集合组成的结构，这些对象之间存在着若干具有某种联系的「对象对（pair）」。
经过数学抽象，这些对象被抽象成了顶点（vertice），也可以叫节点（node），每对关联对象之间的联系被抽象成了边（edge），也可以叫做弧（arc）。
下图就是一个图结构的示意图：
加载中…
有向图和无向图
图中的边可以有方向，也可以无方向。
边有方向的图叫做有向图（Directed Graph），反之叫做无向图（Undirected Graph）。
加载中…
图中所有的边都无向，才能叫无向图。
那么可能有的同学要问了：有向图所有的边都必须有向吗？可不可以有的边有向，有的边无向呢？
大家想一想，边无向和有向的区别是什么？无向边就是被连接的两个顶点可以互通的意思，而有一个方向的有向边连接的两者，只能从其中一个顶点到另一个，反之不可以。
如果有向边方向是双向的呢？比如下图顶点 2 和顶点 3 之间那样。
加载中…
双向就是无向，因此，只要一个图里有了一条有向边（单向），我们就可以让所有无向边都变成双向的，以此达到所有边都有向的效果。
加载中…
也就是说只要包含了一条单向边的图，就是有向图。
图的相关概念和算法
图当中还涉及到一个重要的概念：环（cycle）。
环的定义很直接：在图中的一条由边组成的路径，沿着这条路径，从一个顶点出发可以它自身。
我们上面几副图中都有环。
根据有向无向，有环无环等属性的区别，图被分成了很多的类型，例如：简单图、多重图、连通图、有向无环图、完全图、二分图、正则图等等，不一而足。这些我们也不在此分别细讲。
有一点希望大家知道，图的遍历算法，是图这一数据结构的算法中最常用也最重要的。
所谓遍历，可以简单地理解成「走一遍」。毕竟图论的起源就是著名的柯尼斯堡七桥问题。
柯尼斯堡七桥问题
18 世纪东普鲁士柯尼斯堡（今日俄罗斯加里宁格勒）市区横跨普列戈利亚河，河中心有两个小岛，和河的两岸有七座桥连接。
加载中…
很多人经过了许多种尝试都不成功。但也不能确认永远都不会成功。
欧拉与图论
直到 1735 年，数学天才莱昂哈德·欧拉（下图）指出：没有方法能圆满解决这个问题。
加载中…
欧拉在第二年发表论文《柯尼斯堡的七桥》，严格证明了符合条件的走法不存在！
欧拉的论文成为了图论的先驱，后来经过众多数学家的贡献，才建立了数学的分支：图论。
欧拉 1736 年论文中提到的问题是遍历问题中的一种：一笔画问题。除此之外，遍历还有其他几种方式。
图的遍历问题本身就是一个大问题，其中包含若干子问题，我们在这里不做详细讨论。
NOTE：因为和图相关的算法大都难度比较大，并不适合初学者一上来就学。
本课里暂不涉及和图相关的算法。因此，对于图，我们仅仅知道一下它的数学定义就可以了。
只是希望大家记住，一旦遇到图相关的算法，遍历算法是绝对不能被忽略的基础算法。
树
数学中的树
在图论中，树（Tree）是一种无向图，其中任意两个顶点间存在唯一一条路径。或者说，只要没有回路的连通图就是树。
换言之，数学上的树其实是图的一个子集，是一种特殊的图。
虽然树也是一种相对复杂的数据结构，但是因为它的应用实在太广泛，而且部分基础算法的难度并不算高，所以，虽然本课并未讲述和树有关的算法的细节，我们还是有必要了解一下作为计算机领域数据结构的树的。
计算机领域的树
在计算机科学里的树和图论中的树并不完全相同，计算机领域的树是可以有方向的（当然也可以没有），而且作为数据结构的树一般都是有根树（rooted tree）。
所谓有根的树是指其中有一个特殊的节点：根节点。
有根树是分层的，每一层中包含若干节点，属于同一层的节点互为兄弟（sibling），但它们互相之间却没有连接。
每个节点都只能连接它上面那层的某一个节点。在相互连接的两个节点中，靠上那层的节点称为父母（parent），靠下那层的称为孩子（child）。
父母可以有多个孩子，但一个孩子只能有一个父母。最上层的那个没有父母的节点叫做根（root），没有孩子的节点叫做叶子（leaf）。
下图就是一棵这样的树：
加载中…
这颗树中：
a 节点是根节点，它是 b 节点 c 节点和 d 节点的父母；
b， c 和 d 节点是 a 节点的孩子，b， c 和 d 是兄弟（sibling），如此逐层类推；
每个分支末端没有孩子的节点，都是叶子节点。
一棵有根树的层数叫做这棵树的高度，比如上图中，这棵数的层数就是 5。
虽然理论上有根树的节点的孩子数可以是任意正整数，但当一棵有根树被构建出来以后，每个节点的孩子的数量就是确定值了——这个时候，我们设孩子最多的那个节点的孩子数为 n，这棵树就叫做 n 叉树。
比如上图的中 n=4，这就是一棵四叉树。
二叉树
每个节点最多可以有两个孩子的有根树叫做二叉树（Binary Tree）。
二叉树中每个节点的两个孩子，分别叫做左孩子和右孩子。
以其中某个节点的左右孩子为根，分离出的子树，叫做该节点的左子树和右子树。
子树是指以某个节点为根，由这个节点及其所有子孙组成的原树的子集。
二叉树的分支具有左右次序，不能随意颠倒。
加载中…
二叉树是有根树的一个特例，它节点的最大分支度为 2，分支还有有左、右次序之分，这些限制都是普通树没有的。
但恰恰是这些限制的加持，使得二叉树具备了很多普通树没有的性质，也因此使得它在计算机领域能够作为一种常用数据结构支持许多高效算法。
二叉树是一种非常重要的数据结构，当我们在计算机领域讨论树的时候，绝大多数情况下都是在说二叉树。
二叉树本身还分为多种细化类型，每一种都有一些特殊的性质。这些，以及实现层的树的表示和存储等问题，在本课中都不展开叙述了。