今天我们介绍一种新的数据结构二叉树，数组和链表这两种线性数据结构都有其不足之处，数组一经创建大小固定，且插入，删除都很慢，链表查询一定要从链表头开始遍历，链表的查找很慢，不管我们要找什么数据，都要从链表头开始遍历，我们就希望有那么一种数据结构，兼顾查找，插入，删除三种操作，于是二叉树应运而生。
树是一种抽象数据类型，有节点和边组成，节点一般代表一种实体，边就是连接节点的线，java中用引用表示，树有很多种，如下图是二叉树，二叉树每个节点最多有两个子节点，当然还有多路数(2-3-4树，后续讲解)
下面是树种常用概念：
①、路径：顺着节点的边从一个节点走到另一个节点，所经过的节点的顺序排列就称为“路径”。
②、根：树顶端的节点称为根。一棵树只有一个根，如果要把一个节点和边的集合称为树，那么从根到其他任何一个节点都必须有且只有一条路径。A是根节点。
③、父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；B是D的父节点。
④、子节点：一个节点含有的子树的根节点称为该节点的子节点；D是B的子节点。
⑤、兄弟节点：具有相同父节点的节点互称为兄弟节点；比如上图的D和E就互称为兄弟节点。
⑥、叶节点：没有子节点的节点称为叶节点，也叫叶子节点，比如上图的H、E、F、G都是叶子节点。
⑦、子树：每个节点都可以作为子树的根，它和它所有的子节点、子节点的子节点等都包含在子树中。
⑧、节点的层次：从根开始定义，根为第一层，根的子节点为第二层，以此类推。
⑨、深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；
⑩、高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；
2 二叉树
二叉树种每个节点最多有两个子节点，二叉树的子节点分为左右子节点，如上图节点D是节点B的左子节点，节点E是节点B的右子节点；如果节点在二叉树种是按节点data大小排序插入的，并且左边节点值永远小于父节点，而右子节点的值永远大于父节点，这样的二叉树我们称之二叉搜索树(binary search tree)
二叉搜索树有着广泛的应用，下面我们介绍二叉搜索树是怎样查找、插入，删除节点的；
2.1查找节点
查找某个节点，我们必须从根节点开始遍历。
①、查找值比当前节点值大，则搜索右子树；
②、查找值等于当前节点值，停止搜索（终止条件）；
③、查找值小于当前节点值，则搜索左子树；
用变量current来保存当前查找的节点，参数value是要查找的值，刚开始查找将根节点赋值到current。接在在while循环中，将要查找的值和current保存的节点进行对比。如果value小于当前节点，则搜索当前节点的左子节点，如果大于，则搜索右子节点，如果等于，则直接返回节点信息。当整个树遍历完全，即current == null，那么说明没找到查找值，返回null。
2.2 插入节点
要插入节点，必须先找到插入的位置。与查找操作相似，由于二叉搜索树的特殊性，待插入的节点也需要从根节点开始进行比较，小于根节点则与根节点左子树比较，反之则与右子树比较，直到左子树为空或右子树为空，则插入到相应为空的位置，在比较的过程中要注意保存父节点的信息 及 待插入的位置是父节点的左子树还是右子树，才能插入到正确的位置。
2.3 遍历二叉树
遍历树是根据一种特定的顺序访问树的每一个节点。比较常用的有前序遍历，中序遍历和后序遍历。而二叉搜索树用的是中序遍历。遍历上图代码样例:
//中序遍历 public void infixOrder(Node current){ if(current != null){ infixOrder(current.leftChild); System.out.print(current.data+" "); infixOrder(current.rightChild); } } //前序遍历 public void preOrder(Node current){ if(current != null){ System.out.print(current.data+" "); preOrder(current.leftChild); preOrder(current.rightChild); } } //后序遍历 public void postOrder(Node current){ if(current != null){ postOrder(current.leftChild); postOrder(current.rightChild); System.out.print(current.data+" "); } }