对于树这个数据结构，第一次看到这个树肯定是一脸蒙逼，玛德，树？种树的那个树么？哈哈哈，当然不是，前面我们说过数组添加、删除数据很慢，查询数据很快；而链表添加、删除数据很快，但是查找数据很慢，我们就想啊，有没有一种数据结构取二者之精华，那不就是一个添加，删除，查询都很快的数据结构吗？那用起来多舒服啊！
这个取二者之精华的数据结构就是树（tree）,而且随着各种大佬对树这种结构的改进，就有了很多种树，常见的有二叉树，红黑树，2-3-4树等各种树，我们就一起看看这几种简单树到底是什么鬼！
1.树的基本概念
树的基本结构就是由一个个的节点组成，如下图所示，然后每一个节点都通过边相连，那么有人要问了，这些节点是什么啊？emmm...上篇博客实现了链表，就是类似链表的那个节点一样的东西，本质上就是一个Node的实例，在这个实例中，有几个属性，分别保存几个子节点的引用和保存的数据；
这里注意一下，任意一个节点的父节点只能有一个，子节点可肯能有多个；这很好理解，现实中，你可以有多个孩子，但是你能有多个亲爹吗？？？
比如对于B节点来说，A是父节点，D，E，F都是子节点，而对于没有子节点的那种节点，叫做叶节点，这里的D、E、F、G、H都是叶节点；由于一切节点都是从A出发的，所以A叫做根节点
注：第一次看这个图是不是不觉得像一棵树啊，其实你要把这个图旋转180度，倒过来看就比较像一棵树了，哈哈哈！话说用过linux操作系统的人应该知道linux的根目录"http://www.likecs.com/"就是树结构。。。
那么什么是二叉树呢？这很简单，每个节点最多只能两个子节点，我们看看下图，这就是一个二叉树的基本结构
根据上图，我们说一下树的基本术语：
路径：从任意一个节点到另外任意一个节点所经过的节点的顺序排列就是路径；
根节点：一棵树只有一个根节点，要保证根到任意一个节点只有一条路径，否则就不是树了，比如下图这个就不是树
父节点：与当前节点连接的上一层节点就是父节点
子节点：与当前节点连接的下一层节点就是子节点
叶节点：没有子节点的节点就是叶结点
子树：上图中在树中随便找一个节点B当作根节点，然后B的所有子节点，子节点的子节点等等就构成了一个子树；
左/右子节点：由于二叉树的每一个节点都只有两个节点，于是左边的子节点叫做左子节点，右边的就叫做右子节点；
2.二叉搜索树
什么是二叉搜索树呢？其实就是一种特殊的二叉树，只是我们向其中添加数据的时候定义了一种规则，比如下图B中存了数据20，现在我们要添加数据10和30，应该怎么放呢？我们将小于20的数据放在左子节点，大于20的数据放在右子节点，这就是二叉搜索树，树如其名，搜索起来特别快；
顺便提一下平衡树和非平衡树，数据在左右子节点中分布比较平均就是平衡树，不怎么平均的就是非平衡树，下图所示，76这个节点只有一个右子节点，而且还连着这么多数据，有点不平衡....
下面我们简单用java代码来表示树的节点（还是用静态内部类的形式）：
2.1.添加节点
添加节点的时候要准备两个指针，parentNode=null和current=root,首先我们要判断root是不是为null，如果是的话直接将我们要添加的节点newNode放到第一个节点就ok了；