目录
基本概念
定义
前序、中序、后序遍历
前驱节点、后继节点（主要用于删除有两个孩子的节点）
代码实现（BST树的基本接口实现）
BST树的创建
插入（非递归、递归）
删除（递归、非递归）
查询（递归、非递归）
BST树的前序、中序、后序、层序遍历的递归实现
二叉搜索树(Tree)，(又:二叉搜索树，二叉排序树)它或者是一棵空树，或者是具有下列性质的二叉树: 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树 。
基本概念定义
二叉搜索树是一棵二叉树，如图所示 。这样一棵树可以使用一个链表结构表示，其中每个结点就是一个对象 。除了结点中的关键字外，每个结点还包含属性left、right、，它们分别指向结点的左孩子、右孩子和双亲 。如果某个孩子结点和父结点不存在，则相应属性的值为 。根结点是树中唯一父结点为nulll的结点 。
前序、中序、后序遍历
二叉搜索树中的关键字总数以满足二叉搜索树性质的方式来存储：设x是二叉搜索树中的一个结点 。如果y是x左子树中的一个结点，那么y.key≤x.key；如果y是x右子树中的一个结点，那么y.key≥x.key 。
二叉搜索树的性质允许通过简单的递归算法来输出树中所有的关键字，有三种方式：先序遍历（VLR）、中序遍历(LVR)、后序遍历(LRV) 。其中，前序遍历中输出根的关键字在其左右子树的关键字之前；中序遍历中输出根的关键词位于其左子树的关键字和右子树的关键字之间；后序遍历中输出根的关键字在左右子树的关键字之后 。
前中后序遍历始终保持左孩子在右孩子之前，改变的只是父节点的遍历顺序，层序遍历则是在二叉树的基础上逐层遍历 。下图二为上面二叉树前中后序遍历后的排序结果 。
遍历一棵有n个结点的二叉搜索树需要耗费Θ(n)时间 。
前驱节点、后继节点（主要用于删除有两个孩子的节点）
前驱节点：（待删除节点的左子树中，值最大的节点）
1.若一个节点有左子树，那么该节点的前驱节点是其左子树中val值最大的节点（也就是左子树中所谓的）
2.若一个节点没有左子树，那么判断该节点和其父节点的关系
2.1 若该节点是其父节点的右边孩子，那么该节点的前驱结点即为其父节点 。
2.2 若该节点是其父节点的左边孩子，那么需要沿着其父亲节点一直向树的顶端寻找，直到找到一个节点P，P节点是其父节点Q的右边孩子，那么Q就是该节点的后继节点
node = cur.left;while(cur.right != null)node = node.right;//node -> cur的前驱节点
后继节点：（待删除节点的右子树中，值最小的节点）
1.若一个节点有右子树，那么该节点的后继节点是其右子树中val值最小的节点（也就是右子树中所谓的）
2.若一个节点没有右子树，那么判断该节点和其父节点的关系
2.1 若该节点是其父节点的左边孩子，那么该节点的后继结点即为其父节点
2.2 若该节点是其父节点的右边孩子，那么需要沿着其父亲节点一直向树的顶端寻找，直到找到一个节点P，P节点是其父节点Q的左边孩子，那么Q就是该节点的后继节点
node = cur.right;while(cur.left != null)node = node.left;//node -> cur的后继节点
代码实现（BST树的基本接口实现）BST树的创建
/*** BST树的节点类型* @param */class BSTNode>{private T data; // 数据域private BSTNode left; // 左孩子域private BSTNode right; // 右孩子域public BSTNode(T data, BSTNode left, BSTNode right) {this.data = http://www.kingceram.com/post/data;this.left = left;this.right = right;}public T getData() {return data;}public void setData(T data) {this.data = data;}public BSTNode getLeft() {return left;}public void setLeft(BSTNode left) {this.left = left;}public BSTNode getRight() {return right;}public void setRight(BSTNode right) {this.right = right;}}