前提：已经理解了树的基本概念
- 定义
树是一种数据结构，是一个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树；
二叉搜索树
树结构本身是一种天然的组织结构，比如文件系统的目录、公司的组织架构等。
二分搜索树是一种特殊的二叉树，总的来说在二叉树中每个节点都最多有两个子树，而它的孩子同样也是一颗二叉树。二叉树的具体结构如下所示，二叉树的每个节点包含三个部分：数据域和指向左右孩子的指针。
class Node{
E e;
Node left;
Node right;
}
除此之外，二叉搜索树还包含以下性质：
（1）二叉搜索树的节点的值一定大于其左子节点的值。
（2）二叉搜索树的节点的值一定小于其右子节点的值。
（3）存储的类型一定得具有可比较性。
- 使用
（1）向二叉树添加节点，实际上就是重新构建树的过程，使用二叉搜索树的性追，根据新节点和当前树的根节点的值来寻找新节点的插入位置，重新构建子树并连接到父节点中。具体流程如下：
插入流程
//向二分搜索树中添加元素（递归）
private Node addNode(Node root, E e){
// root 为 null，说明寻找到了合适的位置，则以 e 创建节点
if(root == null) {
size ++;
return new Node(e);
}
// 根据二叉搜索树的性质，决定 e 的插入位置
if(root.e.compareTo(e) < 0){
root.right = addNode(root.right, e);
}else if(root.e.compareTo(e) > 0){
root.left = addNode(root.left, e);
}
// 构建完成之后，将重构之后的树返回
return root;
}
（2）搜索节点，同样利用二叉搜索树的性质，通过递归方式寻找树中是否包含该节点。
private boolean searchNode(Node root, E e){
if(root == null) return false;
if(root.e.compareTo(e) > 0){
return searchNode(root.left, e);
}else if(root.e.compareTo(e) < 0){
return searchNode(root.right, e);
}
return root.e.equals(e);
}
- 遍历
树的三种遍历方式分别为先序遍历、中序遍历和后序遍历。遍历规则分别为根左右、左根右和左右根。在遍历过程中，树的每一个节点实际上都会经过三次，根据遍历方式的不同，决定了在哪次会对节点进行真正的访问，在先序遍历过程中，在第一次经过时，就完成了节点的真正访问；在中序遍历时，真正访问的过程是在第二次；同理，后续遍历是第三次。
访问过程
以先序遍历为例，看一下树的遍历方式。在二叉树的遍历时，每个节点实际上都会被访问三次，
（1）先序遍历（递归实现，对于其他遍历方式以及非递归的实现，请自取）
//先序遍历的递归实现
private void preOrderRecursion(Node root){
if(root == null) return;
System.out.print(root.e + " ");
preOrderRecursion(root.left);
preOrderRecursion(root.right);
}
（2）层次遍历
树的层次遍历，就是从上往下、一层一层的从左往右遍历。比如在本文的第一章配图中，层次遍历的结果为 12，5，18，2，9，15，19，17，16，可以使用广度优先搜索算法完成对图的层次遍历，这要使用之前学过的队列，具体流程是当某节点访问完成之后，将其的左右孩子入队等待访问。
//树的层次遍历
public void levelOrder(){
if(root == null) return;
Node ret = root;
LinkedList<Node> queue = new LinkedList<>();
queue.addLast(ret);
while(!queue.isEmpty()){
Node node = queue.removeFirst();
System.out.print(node.e + " ");
if(node.left != null) queue.addLast(node.left);
if(node.right != null) queue.addLast(node.right);
}
}
