线性结构

小编前面文章中有讲到的数组和链表属于逻辑上一对一的关系，在物理关系上，数据都是线性的。即，可以通过一根线（不管是直线还是曲线）将所有的数据串起来，所以称这种数据结构为线性表，如图：

树

与线性结构相反，树结构就是一对多的关系。即一个数据元素可能与另外多个数据元素有关系。就像大树一样。每一个枝桠，都会分支出许多树枝。如下图，数据A，与B、C、D三个元素有关系。数据B又同时与E、F。该数据结构看起来就像一颗倒过来的大树，所以称这种数据结构为树结构；

树的一些概念

节点：

树中的每一个元素都称为节点。

父节点、子节点、兄弟节点：

如上图，对B、C、D来说，A就是他们的父节点也叫双亲节点。相应的，对A来说B、C、D就是A的子节点，而B、C、D本身互相是平级的，共父节点，所以它们就是互为兄弟节点。

根节点：没有父节点的节点就是整个数的根节点。

子树：任何没有子节点的单个节点或者节点与其下属所有节点都可以是树的子树。如：以B为根节点的B、E、F、K、L即为树的子树。K、L、M任意一个也都能称为树的子树。

空树：没有任何节点的树称为空树。

度和层次

度：对于每个节点，它下面有几个分支就说该节点的度是多少。层次：如上图树，A为第一层，B、C、D为第二层，以此类推

深度：树的深度就是最大层数

有序树、无序树和森林

如果从左至由，节点的排序有规律，则称树为有序树，否则就是无序树。

很多树组成的集合就是森林，但是有一个条件就是各树不能有相交。如上图，B、C、D为根节点的子树就可以组成一个森林。

二叉树（Binary Tree）

什么是二叉数？二叉树必须同时具备下面两个条件：

如上图，只有a是二叉树，b不是，因为1这个节点的度为3，超过2了，所以不是二叉树。

满二叉树

除了叶子节点（及最后一层的节点）外，所有的节点的度都为2，不能少于2，那么我们称这个树为满二叉树。如上图中a树即为一个满二叉树，满二叉树也叫完美二叉树。

完全二叉树

先看两张图：

如上图，只有a为完全二叉树，b不是，因为完全二叉树也需要满足两个条件：

1、在满二叉树的基础上，最后一层节点可以不填满

2、但是最后一层所有的节点都需要靠左排列

上图b，因为最后一层节点不是靠左排列，所以不是完全二叉树；

完满二叉树

还有一种树叫完满二叉树，叫起来是不是很拗口呢？完满二叉树是只要一个节点有子节点，那么该节点的度就一定为2的树就是完满二叉树。

满二叉树（完美二叉树）、完全二叉树、完满二叉树对比