1.什么是二叉排序树呢？（Binary Sort Tree）
二叉排序树具有以下几个特点。
（1）若根节点有左子树，则左子树的所有节点都比根节点小（就是左子树结点要比双亲结点小）。
（2）若根节点有右子树，则右子树的所有节点都比根节点大（就是右子树结点要比双亲结点大）。
（3）根节点的左，右子树也分别为二叉排序树。
2.构造一棵二叉排序树的目的
其实并不是为了排序，而是为了提高查找和插入删除的效率。
下面是二叉排序树的图示，通过图可以加深对二叉排序树的理解。
可以看到，根结点50的左边所有的子结点都比它小，根结点50的右边所有的子结点都比它大
3.下面是二叉排序树常见的操作及思路。
（1）插入节点（要先进行查找，查找结束后，没有，就在那个位置进行插入）
思路：比如我们要插入数字20到这棵二叉排序树中。那么步骤如下：
1) 首先将20与根节点进行比较，发现比根节点小，所以继续与根节点的左子树30比较。
2) 发现20比30也要小，所以继续与30的左子树10进行比较。
3) 发现20比10要大，所以就将20插入到10的右子树中。
（2）查找节点（递归）
比如我们要查找节点10，那么思路如下：
1) 还是一样，首先将10与根节点50进行比较大小，发现比根节点要小，所以继续与根节点的左子树30进行比较。
2) 发现10比左子树30要小，所以继续与30的左子树10进行比较。
3) 发现两值相等，即查找成功，返回10的位置。
过程与插入相同，这里就不贴图了。
（3）删除节点（不能因为删除了结点，而让这棵树变得不满足二叉树的特性）
删除节点的情况相对复杂，主要分以下三种情形：
1) 删除的是叶节点(即没有孩子节点的)。比如20，删除它不会破坏原来树的结构，最简单。如图所示。
2) 删除的是单孩子节点。比如90，删除它后需要将它的孩子节点与自己的父节点相连。情形比第一种复杂一些。
3) 删除的是有左右孩子的节点。比如根节点50，这里有一个问题就是删除它后将谁做为根节点的问题？利用二叉树的中序遍历，就是右节点的左子树的最左孩子。
import java.util.Random;
/*
* 二叉排序树（又称二叉查找树）
* （1）可以是一颗空树
* （2）若左子树不空，则左子树上所有的结点的值均小于她的根节点的值
* （3）若右子树不空，则右子树上所有的结点的值均大于她的根节点的值
* （4）左、右子树也分别为二叉排序树
*
*
* 性能分析：
* 查找性能：
* 含有n个结点的二叉排序树的平均查找长度和树的形态有关，
* （最坏情况）当先后插入的关键字有序时，构成的二叉排序树蜕变为单枝树。查找性能为O(n)
* （最好情况）二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log2(n)成正比
*
*
* 插入、删除性能：
* 插入、删除操作间复杂度都O(log(n))级的，
* 即经过O(log(n))时间搜索到了需插入删除节点位置和删除节点的位置
* 经O(1)级的时间直接插入和删除
* 与顺序表相比，比序顺序表插入删除O(n)(查找时间O(log(n))移动节点时间O(n))要快
* 与无序顺序表插入时间O(1)，删除时间O(n)相比，因为是有序的，所查找速度要快很多
*
*/
public class BinarySortTree {
private Node root = null;
/*查找二叉排序树中是否有key值*/
public boolean searchBST(int key){
Node current = root;
while(current != null){
if(key == current.getValue())
return true;
else if(key < current.getValue())
current = current.getLeft();
else
current = current.getRight();
}
return false;
}
/*向二叉排序树中插入结点*/
public void insertBST(int key){
Node p = root;
/*记录查找结点的前一个结点*/
Node prev = null;
/*一直查找下去，直到到达满足条件的结点位置*/
while(p != null){
prev = p;
if(key < p.getValue())
p = p.getLeft();
else if(key > p.getValue())
p = p.getRight();
else
return;
}
/*prve是要安放结点的父节点，根据结点值得大小，放在相应的位置*/
if(root == null)
root = new Node(key);
else if(key < prev.getValue())
prev.setLeft(new Node(key));
else prev.setRight(new Node(key));
}
/*
* 删除二叉排序树中的结点
* 分为三种情况：（删除结点为*p ，其父结点为*f）
* （1）要删除的*p结点是叶子结点，只需要修改它的双亲结点的指针为空
* （2）若*p只有左子树或者只有右子树，直接让左子树/右子树代替*p
* （3）若*p既有左子树，又有右子树
* 用p左子树中最大的那个值（即最右端S）代替P，删除s，重接其左子树
*/
public void deleteBST(int key){
deleteBST(root, key);
}
private boolean deleteBST(Node node, int key) {
if(node == null) return false;
else{
if(key == node.getValue()){
return delete(node);
}
else if(key < node.getValue()){
return deleteBST(node.getLeft(), key);
}
else{
return deleteBST(node.getRight(), key);
}
}
}
private boolean delete(Node node) {
Node temp = null;
/*右子树空，只需要重接它的左子树
* 如果是叶子结点，在这里也把叶子结点删除了
*/
if(node.getRight() == null){
temp = node;
node = node.getLeft();
}
/*左子树空， 重接它的右子树*/
else if(node.getLeft() == null){
temp = node;
node = node.getRight();
}
/*左右子树均不为空*/
else{
temp = node;
Node s = node;
/*转向左子树，然后向右走到“尽头”*/
s = s.getLeft();
while(s.getRight() != null){
temp = s;
s = s.getRight();
}
node.setValue(s.getValue());
if(temp != node){
temp.setRight(s.getLeft());
}
else{
temp.setLeft(s.getLeft());
}
}
return true;
}
/*中序非递归遍历二叉树
* 获得有序序列
*/
public void nrInOrderTraverse(){
Stack<Node> stack = new Stack<Node>();
Node node = root;
while(node != null || !stack.isEmpty()){
while(node != null){
stack.push(node);
node = node.getLeft();
}
node = stack.pop();
System.out.println(node.getValue());
node = node.getRight();
}
}
public static void main(String[] args){
BinarySortTree bst = new BinarySortTree();
/*构建的二叉树没有相同元素*/
int[] num = {4,7,2,1,10,6,9,3,8,11,2, 0, -2};
for(int i = 0; i < num.length; i++){
bst.insertBST(num[i]);
}
bst.nrInOrderTraverse();
System.out.println(bst.searchBST(10));
bst.deleteBST(2);
bst.nrInOrderTraverse();
}
/*二叉树的结点定义*/
public class Node{
private int value;
private Node left;
private Node right;
public Node(){
}
public Node(Node left, Node right, int value){
this.left = left;
this.right = right;
this.value = value;
}
public Node(int value){
this(null, null, value);
}
public Node getLeft(){
return this.left;
}
public void setLeft(Node left){
this.left = left;
}
public Node getRight(){
return this.right;
}
public void setRight(Node right){
this.right = right;
}
public int getValue(){
return this.value;
}
public void setValue(int value){
this.value = value;
}
}
}
总结：
（1）二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入和删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需修改链接指针即可。
（2）二叉排序树的查找性能取决于二叉排序树的形状。
栗子：以下序列中不可能是一棵二叉查找树的后序遍历结构的是:B
A.1,2,3,4,5
B.3,5,1,4,2
C.1,2,5,4,3
D.5,4,3,2,1
解析：
题目给出的是后续遍历的序列，那么最后一个节点必定是根节点。 最后一个节点之前的所有节点必定是根节点的左右子树，根据二叉查找树的定义，其左子树和右子树中的节点， 是大于或者小于根节点的 选项中只有B 无法找到一个合理的划分点，来组成二叉查找树