最新消息:深度思考

二叉搜索(排序)树实现-Java泛型版

算法 liuxuecheng 2815浏览 0评论

二叉查找树(Binary Search Tree),又叫二叉排序数(Binary Sort Tree),网上的实现都是假定元素是整型,这里使用泛型搞一个,实现插入、查找、删除、查找最小值这四个操作。

public class BST<T extends Comparable> {

    public static void main(String args[])throws Exception{
        BST bst = new BST();
        BSTNode<Integer> root = new BSTNode<Integer>(10);
        bst.insert(root,33);
        bst.insert(root,2);
        bst.insert(root,1);
        bst.insert(root,3);
        bst.insert(root,55);
        bst.insert(root,7);

        bst.remove(root,2);
        bst.findMin(root);
        bst.contains(root,7);
    }

    /**
     * bst删除其中一个节点
     * @param node
     * @param value
     * @return
     */
    public BSTNode<T> remove(BSTNode<T> node,T value){
        if(node==null){
            return null;
        }

        //值比较,给定值小于节点值递归遍历左子树,反之遍历右子树
        int result = value.compareTo(node.value);
        if(result<0){
            node.left = remove(node.left,value);
        }else if(result>0){
            node.right = remove(node.right,value);
        }else {
            //找到要删除的节点
            //如果要删除的节点有左右子树,则节点的值变为右子树的最小值,并递归的删除右子树中的这个最小值
            //之所以这样做是因为右子树中的最小值肯定比相邻的左子树值大,
            // 而且小于右子树任何值,可以作为当前左右子树的父节点
            if(node.left!=null && node.right!=null){
                node.value = findMin(node.right);
                node.right = remove(node.right,node.value);
            }else{
                //只有左子树或者右子树或者为树叶的情况一样
                node = (node.left!=null) ? node.left:node.right;
            }
        }
        return node;
    }
    /**
     * 查找最小值
     * @param node
     * @return
     */
    public T findMin(BSTNode<T> node){
        if(node==null){
            return null;
            //节点没有左子树,自己就是最小值
        }else if(node.left==null){
            return node.value;
        }else {
            //递归查找左子树,BST的性质就是最小的值在左子树
            return findMin(node.left);
        }
    }
    /**
     * bst查找
     * @param node
     * @param value
     * @return
     */
    public boolean contains(BSTNode node,T value){
        if(node==null){
            return false;
        }
        int result = value.compareTo(node.value);
        //小于则搜索左子树,大于则搜索右子树
        if(result<0){
            return contains(node.left,value);
        }else if(result>0){
            return contains(node.right,value);
        }else{
            return true;
        }
    }
    /**
     * 插入
     * @param node
     * @param value
     * @return
     * @throws Exception
     */
    public BSTNode<T> insert(BSTNode<T> node,T value) throws Exception{
        if(node==null){
            node = new BSTNode<T>(value);
            node.left = null;
            node.right = null;
            return node;
        }

        int result = value.compareTo(node.value);
        if(result<0){
            node.left=insert(node.left,value);
        }else if(result>0){
            node.right=insert(node.right,value);
        }else {
            throw new Exception("the element has been inserted");
        }
        return  node;
    }
}

class BSTNode<T>{
    T value;
    BSTNode<T> left;
    BSTNode<T> right;
    public BSTNode(T value){
        this.value = value;
    }
}

转载请注明:大数据随笔 » 二叉搜索(排序)树实现-Java泛型版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址