终于学到树了，也是不容易，打算 把数据结构和算法学一遍然后就开始刷leetcode了，加油！
树的定义什么是树，在先介绍树之前，我们先看几张图
我从图中可以发现，树这种数据结构，如果把他倒过来，很像生活中的树，最顶上的元素好像就是树根，下面的是一个一个的分枝。所以我们把树上每个元素称为节点，最上面的元素称为根节点。节点与节点之间有一定的父子关系，上下节点为父子节点，左右节点称为兄弟节点。
下面再来看一张图
在图中，节点A是节点B的父节点，节点B是节点A的子结点。因为B，C，D这三个节点的父节点是同一个节点，所以他们称为兄弟节点。我们把没有父节点的节点称为根节点，如图中的E节点，我们把没有子结点的节点称为叶子节点，如图中的G，H，I，J。
除此之外，我们还需要了解几个概念：高度，深度，层
#节点的高度 = 节点到叶子节点最长路径长度（边数）
#节点的深度 = 根节点到这个节点的路径长度（边数）
#节点的层 = 节点的深度 + 1
#树的高度 = 根节点的高度
下面再来看几张图
二叉树的定义
树的结构多种多样，不过，最常用的还是二叉树。
对于二叉树，每个节点最多有两个叶子节点，分别是左子节点和右子节点，但是二叉树也不要求每个节点必须有两个节点，可以有左子节点，也可以有右子节点。下面来看一个图。
在上图中，编号为2和3的树比较特殊。在编号为2的树中，他的叶子节点全部在最底层，然后除了叶子节点外，每个节点都有两个叶子节点 ，这种二叉树称为满二叉树。编号为3的树中，他的叶子节点分布在最底层和倒数第二层，而且最下面一次的叶子节点都靠左排列，我们把这种二叉树称为完全二叉树。这个树可能不太好分清，而且可能还会有疑问为什么最下面一层的叶子节点必须都靠左排列，下面我会进行讲解，现在先来看图。
二叉树的存储要完全理解二叉树，我们还需要知道二叉树是如何存储的，存储一颗二叉树一般有两种方法，一个是基于指针（引用）的链式存储方式，另一种是基于数组的顺序存储方式。‘
先来看一张图
从图中可以看出，每个节点包含三个字段，数据本身和指向左右节点的指针，我们可以根据指针，将整个树给串联起来.
下面看看二叉树链式存储的代码实现
public class Node{
public int data;
public Node left;
public Node right;
}
下面看看基于数组的顺序存储方式。
我们用数组来存储所有的节点。对于节点之间的父子关系，通过计算数组下标获得。如果节点x存储在数组中下标为i的位置，那么下标为2i存储的就是他的左子节点，下标2i+1存储的就是右子节点，下标i/2存储的是父节点。
通过这种方式，我们只要知道根节点的下标在什么位置，就可以知道其他子结点的下标了，还有我们为了方便计算，通常把根节点存放在下标为1的地方。下面通过一张图进行举例说明
对于节点B，他存放的位置i = 2，所以他的左子节点（D）2i = 4.右子节点(E)2i+1 = 5。他的父节点(A)i/2 = 1。
大家仔细看这张图应该就会发现，他是一棵完全二叉树存储的。在数组中是连续的。如果换成非完全二叉树又是什么结果呢？看一个图。
从图中可以发现，采用数组来存储非完全二叉树，我们会浪费较多的空间。所以，对于非完全二叉树，我们一般会采用链式存储的方式来进行存储。对于完全二叉树，采用线性存储，基于数组的形式存储完全二叉树会更大的节省内存，也不需要记录左右子节点的指针。这就是完全二叉树要求最下面一层的叶子节点都靠左排列的原因。
二叉树的遍历上面讲了关于二叉树的定义和存储，相信大家对二叉树都有了一个概念和基本的了解。这次我们来聊一聊二叉树的遍历。
将二叉树中节点进行输出，经典的方法有三种，前序遍历，中序遍历，和后序遍历。
前序遍历(根左右)：对于树中的任意节点，先输出自己，然后输出左子树，然后右子树
中序遍历(左根右)：对于树中任意节点，先输出左子树，然后输出自己，然后右子树
后序遍历(左右根)：对于树中任意节点，先输出左子树，再输出右子树，最后输出自己
实际上对树的很多操作是非常适合用递归来进行实现的。二叉树的前序，中序，后序就是典型的递归过程。例如前序遍历就是先输出根节点，然后左子树，然后右子树。
递归的写法主要是写出递归公式，关于写出递归公式关键是将子问题进行分解。比如说，要解决A，就要假设B和C都已经解决了。下面看看递推公式
前序遍历递推公式：
preOrder(root) = print root -> preOrder(root.left) -> preOrder(root.right)
中序遍历
inOrder(root) = inOrder(root.left) -> print root -> inOrder(root.right)
后续遍历
postOrder(root) = postOrder(root.left) -> postOrder(root.right) -> print root
下面看看代码
public void preOrder(Node root){
if(root == null) return;
System.out.println(root.data);
preOrder(root.left);
preOrder(root.right);
}
public void inOrder(Node root){
if(root == null) return;
inOrder(root.left);
System.out.println(root.data);
inOrder(root.right);
}
public void postOrder(Node root){
if(root == null) return;
postOrder(root.left);
postOrder(root.right);
System.out.println(root.data);
}
三种遍历操作的时间复杂度与节点的个数n成正比，时间复杂度为O(n)。
