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

二叉查找树(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;
    }
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇