二叉排序树

二叉排序树又称二叉查找树，它或者是一颗空树，或者是具有以下性质的二叉树

• 若左子树非空，则左子树上所有结点的值均小于根结点的值
• 若右子树非空，则右子树上所有结点的值均大于根结点的值
• 左、右子树本身是二叉排序树

如下为一颗二叉排序树：

代码实现

树的结点定义

Node.java 省略get(),set()方法

 public class Node {
  
   //结点值
    private int value;
    //双亲结点
    private Node parent;
    //左右结点
    private Node left;
    private Node right;
    
    public Node() {
    }

    public Node(int value, Node parent, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
        this.parent = parent;
    }

    public Node(int value,Node parent) {
        this(value,parent,null,null);
    }
}  

二叉排序树算法实现

BinarySortTree.Java

 public class BinarySortTree {

    private Node root = null;

    /**二叉排序树中的查找算法*/
    public boolean searchBST(int key){
        Node current = root;
        while (current != null){
            //等于当前值，返回true
            if(key == current.getValue())
                return true;
            //小于当前值，进入左节点
            else if (key < current.getValue())
                current = current.getLeft();
            //进入右节点
            else
                current = current.getRight();
        }
        //没找到结果返回false
        return false;
    }

    /**二叉排序树中插入结点*/
    public boolean insertBST(int newKey){
        Node p = root;
        Node parent = null;
        //记录插入结点位置（prev为要插入结点的父节点）
        Node prev = null;
        //在树中寻找插入位置
        while (p != null){
            parent = p;
            prev = p;
            if(newKey > p.getValue())
                p = p.getRight();
            else if (newKey < p.getValue())
                p = p.getLeft();
            //键值为newKey的结点已在树中，不再插入
            else
                return false;
        }
        //若为空树，键值为newKey的结点为树根
        if (root == null)
            root = new Node(newKey,parent);
        //作为左结点插入
        else if (newKey < prev.getValue())
            prev.setLeft(new Node(newKey,parent));
        //作为右结点插入
        else
            prev.setRight(new Node(newKey,parent));
        return true;
    }

    /**删除结点，有三种情况：
     * 1.被删除结点P为叶子结点，直接删除
     * 2.被删除结点P只有左子树或只有右子树，将被删除结点P的左子树或右子树接成其双亲结点的左/右子树
     * 3.被删除结点P有左子树和右子树，
     * 用被删除结点P左子树中最大的值（即最右端结点S）代替被删除结点P，并删除左子树中最大值（最右端结点S）
     */
    public boolean deleteBST(int key){
        return deleteBST(root,key);
    }
    public boolean deleteBST(Node node,int key){
        if (node == null)
            return false;
        else {
            if (key == node.getValue())
                return deleteNode(node);
            else if (key < node.getValue())
                return deleteBST(node.getLeft(),key);
            else
                return deleteBST(node.getRight(),key);
        }
    }

    private boolean deleteNode(Node node) {
        Node temp = null;
        //被删除结点为叶子结点,直接删除
        if(node.getLeft() == null && node.getRight() == null){
            //被删除结点是根结点
            if(node == root)
                root = null;
            else{
                if(node.getValue() == node.getParent().getLeft().getValue())
                    node.getParent().setLeft(null);
                else
                    node.getParent().setRight(null);
            }
        }
        //被删除结点P只有左子树或只有右子树，将被删除结点P的左子树或右子树接成其双亲结点的左/右子树
        else if (node.getLeft() == null){
            if(node.getValue() == node.getParent().getLeft().getValue())
                node.getParent().setLeft(node.getRight());
            else
                node.getParent().setRight(node.getRight());
        }
        else if (node.getRight() == null){
            if(node.getValue() == node.getParent().getLeft().getValue())
                node.getParent().setLeft(node.getLeft());
            else
                node.getParent().setRight(node.getLeft());
        }
        //被删除结点P有左子树和右子树，
        //用被删除结点P左子树中最大的值（即最右端结点S）代替被删除结点P，并删除左子树中最大值（最右端结点S）
        else {
            temp = node;
            Node s = node;
            /**在左子树中获取最右端结点S*/
            s = s.getLeft();
            while(s.getRight() != null){
                temp = s;
                s = s.getRight();
            }
            //S替代P
            node.setValue(s.getValue());
            //删除S
            if(temp != node){
                temp.setRight(s.getLeft());
            }
            else{
                temp.setLeft(s.getLeft());
            }
        }
        return true;
    }
	//测试
    public static void main(String[] args) {
        BinarySortTree binarySortTree  = new BinarySortTree();
        int num[] = {38,25,45,15,30,40};
        for(int i=0;i<num.length;i++){
            binarySortTree.insertBST(num[i]);
        }
        boolean result = binarySortTree.searchBST(15);
        boolean delete = binarySortTree.deleteBST(25);
    }
}