之前的篇章主要讲解了数据结构中的线性结构，所谓线性结构就是数据与数据之间是一对一的关系，接下来我们就要进入非线性结构的世界了，主要是树与图，好了接下来我们将会了解到树以及二叉树，二叉平衡树，赫夫曼树等原理以及java代码的实现，先从最基础的开始学习吧。
一、树
树的定义：
树是n(n>=0)个结点的有限集合。
当n=0时，集合为空,称为空树。
在任意一颗非空树中，有且仅有一个特定的结点称为根。
当n>1时,除根结点以外的其余结点可分成m(m>=0)个不相交的有限结点集合T1,T2….Tm.其中每个集合本身也是一棵树,称为根的子树。
如下图就是一棵树:
可以看到，树这种数据结构数据之间是一对一或者一对多关系，不再是一对一的关系
在上图中节点A叫做整棵树的根节点，一棵树中只有一个根节点。
根节点可以生出多个孩子节点，孩子节点又可以生出多个孩子节点。比如A的孩子节点为B和C，D的孩子节点为G，H，I。
每个孩子节点只有一个父节点，比如D的父节点为B，E的父节点为C。
好了，关于树的定义介绍到这，很简单。
二、树的相关术语
节点的度
节点含有的子树个数，叫做节点的度。度为0的节点成为叶子结点或终端结点。比如上图中D的度为3，E的度为1.
G,H,I,J的度为0，叫做叶子结点。
树的度
一棵树中 最大节点的度树的度。比如上图中树的度为3
结点的层次
从根结点算起，为第一层，其余依次类推如上图。B,C的层次为2，G,H的层次为4。
树中节点的最大层次称为树的高度或深度。上图中树的高度或深度为4
三、树的存储结构
简单的顺序存储不能满足树的实现，需要结合顺序存储和链式存储来解决。
树的存储方式主要有三种：
双亲表示法：每个节点不仅保存自己数据还附带一个指示器指示其父节点的角标，这种方式可以用数组来存储。
如图：
这种存储方式特点是：查找一个节点的孩子节点会很麻烦但是查找其父节点很简单。
孩子表示法：每个节点不仅保存自己数据信息还附带指示其孩子的指示器，这种方式用链表来存储比较合适。
如图：
这种存储方式特点是：查找一个节点的父亲节点会很麻烦但是查找其孩子节点很简单。
理想表示法：数组+链表的存储方式，把每个结点的孩子结点排列起来，以单链表方式连接起来，则n个孩子有n个孩子链表，如果是叶子结点则此链表为空，然后n个头指针又组成线性表，采用顺序存储方式，存储在一个一维数组中。
如图：
这种方式查找父节点与孩子结点都比较简便。
以上主要介绍了树的一些概念以及存储方式介绍，实际我们用的更多的是二叉树，接下来我们看下二叉树。
四、二叉树的概念
二叉树定义：二叉树是n（n>=0）个结点的有限集合，该集合或者为空，或者由一个根结点和两课互不相交的，分别称为根结点左子树和右子树的二叉树组成。
用人话说，二叉树是每个节点至多有两个子树的树。
如图就是一颗二叉树：