4.2 非线性数据结构
简单地说，非线性结构就是表中各个结点之间具有多个对应关系。其中各个数据元素不再保持在一个线性序列中，数据元素之间是一对多，或者是多对一的关系。根据关系的不同，可分为树形结构和图结构。
现实世界中的一棵树是一种生物，它的根在地上，树枝上有叶子、果实。树的分支以一种有组织的方式展开。在计算机科学中，树被用来描述数据如何被组织，除了根在顶部，树枝、树叶跟随向底部蔓延，并且树的绘制与真实树相比被倒置。
树形结构是一种日常生活中应用非常广泛的形式，图4-2的企业内部组织结构图就是一种典型的树形结构，总经理是职能权利最大，物业管理部是其下属机构，而环境部主管又是物业管理部的分支机构。在计算机领域中，树形结构也是应用很广泛的，比如操作系统与数据库都是树形结构。
图4-2 企业组织树形结构图
树是由一个或者一个以上的节点组成，存在一个特殊的节点，称为树根，或者根节点，图4-3中的A节点就是树根。每个节点都是一些数据和指针组合而成的记录，除了树根外，其余节点都是可分为n个互斥的集合。其中每一个子集合本身也是一种树形结构，即此根节点的子树。为了引入更多的符号，根始终位于树的顶部，后面的其他节点称为分支，每个分支中的最终节点称为叶。可以将每个分支想象成一颗较小的树本身。根通常称为父节点，它下面引用的节点称为子节点。具有相同父节点的节点称为兄弟节点。
在图4-3中，A为根节点，B、C、D、E、F均为A的子节点。B是A的子节点，B和D、E也构成了一个子集合，B为这个子集合的根节点，D、E是它的子节点。
图4-3 树形结构图
小白逆袭：树的存储形式
在Python中一切皆对象，树这种数据结构也是一种对象，它在Python中可以通过列表和链表来储存。列表也可以将每个节点对象都储存起来，但是列表在逻辑上不够形象，所以很少用到。所以使用最多的方式是通过链表来构建树对象，其基本属性是根节点，根节点的左树属性和右树属性连接不同的节点，依次构建一棵庞大的树。
另外一种非线性数据组织形式就是图。图是一种与树有些相似的数据结构。如果从数学的角度归类，图结构其实是树结构的一种表现形式。我们都知道树可以用来模拟很多现实的数据结构，比如家谱、公司组织架构等。那么图长什么样子呢？或者说什么样的数据使用图来模拟更合适呢？很简单，像人与人的关系网、中国的高速公路网以及北京的地铁网络等都适合用图来模拟。
在图4-4中，图结构中的点称为顶点（vertex），如1、2、3、4、5、6等。顶点与顶点之前的连线称为边（edge），如1和3之间的直线。所有的顶点构成一个顶点集合，所有的边构成边的集合，一个完整的图结构就是由顶点集合和边集合组成。图结构中顶点集合不能为空，必须包含一个顶点，但构边集合可以为空，表示没有边。非线性数据结构的模型要比线性数据结构更加复杂。
图4-4 图结构
由于篇幅有限，只能概括性地描述数据结构的内容。数据结构的内容非常多，也非常重要。从编程的发展趋势来看，算法是区别普通程序员和大牛程序员的重要指标，也是大数据领域和人工智能领域绕不开的门槛，希望大家多多重视，从一开始就打好基础。