第六节 数据结构基础（2）树、二叉树和图
我们之前讲了数据结构中的几个线性结构，链表、栈还有队列。那么如果想要一个能表示多个元素之间关系的数据结构，就要使用我们的树形结构和图了。在ACM和蓝桥杯的比赛中，有关树和图的题目是百分百出现的。
树
树形结构是一类非常重要的非线性数据结构，其中以树和二叉树最为常用。树结构在客观世界中广泛存在，比如我们日常生活中常见的组织结构图：
树是n个结点的有限集合，在任意一棵非空的树中：
- 有且仅有一个特定的，称为根（Root）的结点
- 当n>1时，其余结点可分别为m（m>0）个互不相交的有限集合T1,T2,…,Tm，其中每一个集合本身又是一棵树，并且称为根的子树
以上就是一棵树的定义。
结点的子树称为它的“孩子”，相应地，该节点称为“双亲”。同一个双亲的孩子称为“兄弟”。孩子的数量称为“度”。
规定根为第一层，它的孩子为第二层，以此类推。树中最大的层数称为树的深度或高度。
森林：m（m>0）课互不相交的树的集合。
二叉树
二叉树的定义和性质
在讨论一般树的存储结构及操作之前，我们首先研究一种名为二叉树的抽象数据结构类型。
二叉树是另一种树形结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点）。并且，二叉树的子树左右之分，其次序不能任意颠倒。
下面是二叉树的一些性质：
- 在二叉树的第i层上至多有2^(i-1)个结点（i>=1）；可以使用数学归纳法来证明
- 深度为k的二叉树至多有2^k-1个结点（k>=1）；由第一个性质推导
- 对任何一棵二叉树T，若其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
- …
二叉树的存储结构
二叉树的概念和性质不是我们研究的主要问题，我们来看一下二叉树的存储结构。二叉树可以使用顺序存储结构和链式存储结构，这里我们先讲一下顺序存储结构。
我们规定，用一组地址连续的存储单元，自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存放在一维数组下表为i（i-1）的分量中。对于一般的二叉树，则应该将其每个节点与完全二叉树相对照，存放在一维数组中。其中0表示不存在此结点。（想想我们之前讲过的memset函数）
链式存储可以使用拥有两个指针域或者三个指针域的链表来表示，这里要看我们对这个二叉树的操作需求。如果需要返回访问根节点，则需要三个指针域。结合下面的内容，理解一下。
lchild data rchild
lchild data parent rchild
二叉树的遍历和线索二叉树
在二叉树的一些应用中，我们常常要求在树种查找具有某种特征的结点，或者对树中全部结点做统一处理，我们就要对二叉树进行遍历。遍历就是按照某条搜索路径巡访树中的每个节点，就比如我们要输出的时候。对于一个线性结构，比如说数组，我们进行遍历就很方便，但是二叉树就比较复杂了。下面我们介绍三种操作方法：
先序遍历：
- 访问根节点
- 先序遍历左子树
- 先序遍历右子树
中序遍历：
- 中序遍历左子树
- 访问根节点
- 中序遍历右子树
后序遍历：
- 后序遍历左子树
- 后序遍历右子树
- 访问根节点
我们知道，二叉树的遍历是以一定的规则将其排列成一个线性结构，但是当以二叉链表作为存储结构时，我们只能找到结点的左右孩子信息，而不能找到结点在任一序列中的前驱和后继。这种信息只有在动态的过程中才能够得到。那么想要保存的话，我们需要在每个节点上再加两个指针域用来存放结点的前驱和后继的信息。
lchild LTag data RTag rchild
以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索二叉链表，对某种次序遍历使其变成线索二叉树的过程叫做线索化。
图
图的定义
图是较线性表和树更为复杂的数据结构。在图结构中，结点之间的关系是任意的——图中任意两个元素都有可能相关。图中的数据元素称为定点（Vertex），VR是表示两个点之间的关系的集合,<v,w>是VR中的元素，表示的是从v到w的的一条弧（Arc）。v为初始点（弧尾），w为终端点（弧头），此时的图称为有向图。如果对任意的<v,w>都有<w,v>，则用无序队（v,w）来代替这个有序对，表示v和w之间的一条边，此时的图为无向图。
有关图的问题还有很多，在数学上，我们专门有一门研究图的学科，叫做图论，这也将是接下来我们的研究对象。在今后的学习中，我们可能会接触到以下内容：
图的存储方法
图的遍历
深度优先搜索（dfs）
广度优先搜索（bfs）
图的连通性
克鲁斯卡尔算法
最短路径
单源最短路径
迪杰斯特拉算法
多源最短路径
普里姆算法
