二叉查找树 Java实现
定义：
一棵二叉查找树是一棵二叉树，每个节点都含有一个Comparable的键（以及对应的值）。
每个节点的键都大于左子树中任意节点的键而小于右子树中任意节点的键。
树的术语：
| Name | Function |
|---|---|
| 路径 | 顺着连接点的边从一个节点走向另一个节点，所经过的节点的顺序排列就称为路径。 |
| 根 | 树顶端的节点就称为根，一棵树只有一个根，如果要把一个节点和边的集合定义为树，那么从根到其他任何一个节点都必须有一条路径。 |
| 父节点 | 每个节点（除了根）都恰好有一条边向上连接到另一个节点，上面的节点就称为下面节点的“父节点”。 |
| 子节点 | 每个节点都可能有一条或多条边向下连接其他节点，下面的这些节点就称为它的“子节点”。 |
| 叶节点 | 没有子节点的节点称为“叶子节点”或简称“叶节点”。树只能有一个根，但是可以有很多叶节点。 |
| 子树 | 每个节点都可以作为子树的根，它和它所有的子节点，子节点的子节点等都含在子树中。 |
| 访问 | 当程序控制流程到达某个节点的时候，就称为“访问”这个节点，通常是为了在这个节点处执行某种操作，例如查看节点某个数据字段的值或者显示节点。 |
| 遍历 | 遍历树意味着要遵循某种特定的顺序访问树中的所有节点。 |
| 层 | 一个节点的层数是指从根开始到这个节点有多少“代”。 |
| 关键字 | 可以看到，对象中通常会有一个数据域被指定为关键字值。这个值通常用于查询或者其他操作。 |
| 二叉树 | 如果树中的每个节点最多只能有两个子节点，这样的树就称为“二叉树”。 |
性质：
- 若它的左子树不为空，则左子树上的所有节点的值都小于它的根节点的值；
- 若它的右子树不为空，则右子树上所有节点的值都大于它的根节点的值；
- 其他的左右子树也分别为二叉查找树；
- 二叉查找树是动态查找表，在查找的过程中可见添加和删除相应的元素，在这些操作中需要保持二叉查找树的以上性质。
根据其二叉树的特性，节点类如下:
public class Node { public int index;//关键字段 public String data;//值 public Node leftNode;//左节点 public Node rightNode;//右节点 @Override public boolean equals(Object obj) { return EqualsBuilder.reflectionEquals(this, obj); } @Override public int hashCode() { return HashCodeBuilder.reflectionHashCode(this); } }其中引用了commons-lang3包中的内容，作为对象进行比较
查找某个节点，相当于二分查找，如果小于当前节点，则走左边，如果大于当前节点，则走右边。当最后叶子节点还没有找到，则没有找到
public Node findNode(int key){ Node current = root; while(current.index != key){ if(key < current.index){//左节点 current = current.leftNode; }else{//右节点 current = current.rightNode; } if(current == null){ return null; } } return current; }插入节点,按照插入的节点都不会出现重复关键字。每一次插入都将变为根节点的子节点，例如根节点关键字为1，接下来插入的节点则变为根节点的右子节点。