之前就说过我们的数据结构分为两种，分别是线性结构和非线性结构，我们今天要学的第一种线性结构就是树型结构。
1. 树型结构
树型结构并非我们熟悉的重点，所以在这里只做了解。
概念：
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
1. 有一个特殊的结点，称为根结点，根结点没有前驱结点
2. 除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm，其中每一个集合Ti (1 <= i <=m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
3. 树是递归定义的
比如生活中见到的树：
数据结构中的 “ 树 ” 和现实中的树有点区别，数据结构中的 “ 树 ” 是倒着树，我们自己动手画一棵：
我们来看一看非树的情况：
我们可以得到如下结论：
1. 子树是不相交的
2.除了根结点外，每个结点有且仅有一个父亲结点
3.一颗N个结点的树，有N - 1 个边（这个后面还会用到）
书上有的很多关于树的概念这里就不介绍了，可以直接看书。例如：
结点的度：一个结点含有子树的个数称为该结点的度；
树的度：一棵树中，所有结点度的最大值称为树的度；
叶子结点或终端结点：度为0的结点称为叶结点；
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；
等等。
1.2 树的表示形式
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。
代码示例：
class Node { int value; // 树中存储的数据 Node firstChild; // 第一个孩子引用 Node nextBrother; // 下一个兄弟引用 }
图示：
1.3 树的应用
比如我们电脑文件管理就是一个树结构的：
2. 二叉树
我们上面的文件管理有多个子节点，我们统称为多叉树，当树的度不大于2时，我们称之为二叉树，例如：
二叉树不仅仅是考试的重难点也是未来面试的一个重难点。
2.1 概念
一棵二叉树是结点的一个有限集合，该集合：
1. 或者为空
2. 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
从上图可以看出：
1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
注意：对于任意的二叉树都是由以下几种情况复合而成的：
2.2 特殊的二叉树
1. 满二叉树: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
2. 完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
关于二叉树的更多性质可以查看下图
好了，了解以上知识，就算碰到二叉树的门槛了，关于二叉树的具体实现，还得接着往下看
3. 二叉树的实现
上代码：
class TreeNode {//结点的实现 int val;//data域 public TreeNode left;//左子节点的引用 public TreeNode right;//右子节点的引用 public TreeNode(int val) { this.val = val; } }
每个结点都存在三个域，数据域和左右子节点，其叶子节点也存在左右子节点，只不过其左右子节点均为null，所以左右子节点均为null的也叫做叶子节点。
我们再来看看二叉树的概念：
1. 空树
2. 非空：根节点，根节点的左子树、根节点的右子树组成的
4. 二叉树的基本操作
在我们真正去实现二叉树的时候一般都是使用LinkedList去实现，我们模拟也是用LinkedList去模拟的。
我们的模拟主要有如下几个
// 获取树中节点的个数
int size(Node root);
// 获取叶子节点的个数
int getLeafNodeCount(Node root);
// 获取第K层节点的个数
int getKLevelNodeCount(Node root,int k);
// 获取二叉树的高度
int getHeight(Node root);
// 检测值为value的元素是否存在
Node find(Node root, int val);
//层序遍历
void levelOrder(Node root);
// 判断一棵树是不是完全二叉树
boolean isCompleteTree(Node root);
还有最最基础的前中后序遍历。
我们先来第一个前序遍历。
1. 前序遍历
思路如下：
我们简易的口诀就是根、左、右；如图：
我们用数字来表示路径，从最开始的根走，找到第二层的根并且把其根全部走完，再走左，把左全部走完最后走右，每一根左右下面都还有一层根左右。
动图表示：
芝士代码：
// 前序遍历 void preOrder(TreeNode root) { if (root == null) { return; } System.out.print(root.val + " "); preOrder(root.left); preOrder(root.right); };
2. 中序遍历
思路：
类似于前序遍历，但是我们的路径发生改变，路径为左、根、右。
每一层的左、根、右都还有左、根、右。
动图表示：
芝士代码：
// 中序遍历 void inOrder(TreeNode root) { if (root == null) { return; } inOrder(root.left); System.out.print(root.val+ " "); inOrder(root.right); };
3. 后序遍历
思路：
一样类似于前序遍历，但是我们的路径发生改变，路径为左、右、根。
每一层的左、右、根都还有左、右、根。
动图表示：
芝士代码：
// 后序遍历 void postOrder(TreeNode root) { if (root == null) { return; } postOrder(root.left); postOrder(root.right); System.out.print(root.val+ " "); };
当然拉我们做二叉树问题的大部分思路都是递归去解决，也有问题可以用其他方法解决，余下的二叉树模拟方法，包括一些oj题还有层序遍历我放在下一章来讲解。
