1.定义

   它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值

   均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

2.插入规则

    向一个二叉排序树b中插入一个结点s的算法，过程为：若b是空树，则将s所指结点作为根结点插入，否则：若s->data等于b的根结点的数据域之值，则返回，否则：

    若s->data小于b的根结点的数据域之值，则把s所指结点插入到左子树中，否则：把s所指结点插入到右子树中。

3.删除规则

    若D结点为叶子结点，即L(左子树)和R(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。

　　

    若D结点只有左子树L或右子树R，此时只要令L或R直接成为其双亲结点P的左子树或右子树即可，作此修改也不破坏二叉排序树的特性。

　　

    若D结点的左子树和右子树均不空。在删去D之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，可以有两种做法：其一是令D的左子树为P的

    左子树，S为P左子树的最右下的结点，而D的右子树为S的右子树；其二是令D的直接前驱（或直接后继）替代D，然后再从二叉排序树中删去它的直接前驱（或

    直接后继）。

　　

4.查找

    若b是空树，则搜索失败，否则：若x等于b的根结点的数据域之值，则查找成功；否则：若x小于b的根结点的数据域之值，则搜索左子树；否则：查找右子树。

5.Java实现

　　1).Node类

　　　

public class Node{    private int value;    private Node leftNode;    private Node rightNode;    public int getValue() {        return value;    }    public void setValue(int value) {        this.value = value;    }    public Node getLeftNode() {        return leftNode;    }    public void setLeftNode(Node leftNode) {        this.leftNode = leftNode;    }    public Node getRightNode() {        return rightNode;    }    public void setRightNode(Node rightNode) {        this.rightNode = rightNode;    }    public Node(){    }    public Node(int value){        this.value = value;    }}

 

　　2).Tree类

public class Serach2Tree {    private Node rootNode;        //加入节点    public void addNode(int value){        if(rootNode==null){            rootNode = new Node(value);        }else{            addNode(rootNode,value);        }    }    //递归遍历加入    private void addNode(Node node,int value){        if(node==null){            node = new Node(value);        }else{            if(node.getValue()>value){                if(node.getLeftNode()!=null){                    addNode(node.getLeftNode(),value);                }else{                    node.setLeftNode(new Node(value));                }            }else if(node.getValue()
              
               ");        if(node.getValue()==value){            return node;        }else {            Node n = null;            if(node.getValue()>value){                n = findNode(node.getLeftNode(),value);            }            if(node.getValue()
               
                value){            if(node.getLeftNode()==null){                return;            }else{                if(node.getLeftNode().getValue()==value){                    if(node.getLeftNode().getLeftNode()==null&&node.getLeftNode().getRightNode()==null){                        node.setLeftNode(null);                    }else if(node.getLeftNode().getLeftNode()==null&&node.getLeftNode().getRightNode()!=null){                        node.setLeftNode(node.getLeftNode().getRightNode());                    }else if(node.getLeftNode().getLeftNode()!=null&&node.getLeftNode().getRightNode()==null){                        node.setLeftNode(node.getLeftNode().getLeftNode());                    }else if(node.getLeftNode().getLeftNode()!=null&&node.getLeftNode().getRightNode()!=null){                        Node p = node;                        Node d = node.getLeftNode();                        Node l = node.getLeftNode().getLeftNode();                        Node r = node.getLeftNode().getRightNode();                        if(r.getLeftNode()==null){                            p.setLeftNode(r);                            r.setLeftNode(l);                        }else{                            Node sp = getRL(r);                            Node s = sp.getLeftNode();                            sp.setLeftNode(s.getRightNode());                            s.setLeftNode(l);                            s.setRightNode(r);                            p.setLeftNode(s);                        }                    }                }else{                    delete(node.getLeftNode(),value);                }            }        }        if(node.getValue()