非线性结构
现实中不是只有那种一对一的线性结构，还有很多一对多的非线性结构，如树、图等
树
线性表、队列、栈都是线性的，这个数据结构不能反映元素之间的层次特性。使用树形结构来描述数据之间的关系。
树的定义
树是n个节点的集合，集合中有一个称为根(root)的特殊节点，在根节点下分布着一些互不相交的集合，每一个集合又是一个树，这些树称为根节点的子树。
在一棵树中，有且仅有一个节点没有前驱，这个节点就是树的根节点
除根节点外，其余每个节点有且仅有一个前驱
每个前驱可以有任意多个后继
相关术语
- 父节点、子节点、兄弟节点 每个节点的子树的根称为该节点的子节点，相应的，该节点被称为子节点的父节点，具有同一父节点的节点称为兄弟节点
- 节点的度 一个节点的子树的数量称为该节点的度，度为0的节点称为叶子节点，度不为0的节点称为分支节点
- 树的度 一棵树的度值该树中节点的最大度数
- 叶节点和分支节点 树中度为0的节点称为叶节点或终端节点。树中度不为0的节点称为分支节点
- 节点的层数 每个节点都处在一定的层次上，从树根开始计算，根节点为第一层，依次向下，树中节点的最大层数称为树的深度
- 树的深度 一棵树中节点的最大层数称为树的深度
- 有序树和无序树 若树中各节点的子树(兄弟节点)是按照一定次序从左到右排列的，称为有序树，否则称为无序树
- 森林 多个互不相交的树的集合
二叉树
二叉树任意节点最多只能有两个子节点；如果只有一个子节点，可以是左子树，也可以是右子树，二叉树的度最大为2，二叉树是有序树
特点
- 在二叉树的第i层上至多有$2^{i-1}$个节点
- 深度为k的二叉树至多有$2^k-1$个节点
- 对任何一棵二叉树T，如果其叶子节点数为$n_0$，度为2的节点数为$n_2$，则$n_0=n_2+1$
- 具有n个节点的完全二叉树的深度为$log_2n$ + 1
- 如果对一棵有n个节点的完全二叉树的节点按层序编号，对任一节点i有：如果i=1，则节点i是二叉树的根；如果i>1，则双亲节点时i/2；如果2i>n，则节点i无左孩子节点；否则其左孩子节点为2i；如果2i+1>n，则节点i无右孩子；否则其右孩子是节点2i+1
特殊结构
- 满二叉树 在二叉树中，除最下一层的叶节点外，每层的节点都有两个子节点，就构成了满二叉树
- 完全二叉树 除二叉树最后一层外，其他各层的节点数都达到最大个数，且最后一层从左到右的叶节点连续存在，只缺右侧若干节点，就是完全二叉树
- 满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树
存储结构
可以有三种存储方式
- 双亲表示法：在每个节点中记录双亲节点地址，以及该节点数据，但是如果要获取孩子节点需要遍历整个树
- 孩子表示法：每个节点都可能有多棵子树，可以使用链表来保存孩子节点的地址
- 孩子兄弟表示法：任意一棵树，它的节点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的，可以保存该节点的第一个孩子节点地址和该节点的右兄弟节点地址，如果有必要，也可以增加双亲节点地址
图
图是由顶点的有穷非空集合和顶点间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V表示G中顶点的集合，E表示图G中边的集合
- 在图中数据元素，称为顶点，且顶点不能为空
- 在图中，任意两个顶点之间都有可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的