开发者社区> 微流> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

Java实现二叉查找树

简介: 二叉查找树 基本性质:对任何节点x,其左子树的任意key不大于x.key,其右子树的任意节点不小于x.key 实现集合操作 search,minimum,maximum,predecessor,successor,...
+关注继续查看

二叉查找树

  1. 基本性质:对任何节点x,其左子树的任意key不大于x.key,其右子树的任意节点不小于x.key
  2. 实现集合操作 search,minimum,maximum,predecessor,successor,insert,delete
  3. 以上操作的最坏运行时间与树的高度成正比,平均时间复杂度O(h),其中h为树的高度
  4. 树的中序遍历是有序序列
  5. 可以用其实现有序字典,优先队列,实现时间复杂度O(h)

树的基本节点

每个节点除了key和卫星数据外,还有left,right,p表示左右孩子和父节点

public class TreeNode {
    public int key;
    public TreeNode left;
    public TreeNode right;
    public TreeNode p;
    public TreeNode(int key){
        this.key=key;
    }
    @Override
    public String toString() {
        return key+"";
    }

}  

基本操作实现

实现操作:求最大 ,最小,查找,插入,删除,前驱,后继

public class BinarySearchTree {
    private TreeNode root;

    public TreeNode minimum(){
        return minimum(root);
    }

    public TreeNode maximum(){
        return maximum(root);
    }
    //如果存在右孩子,右子树最小值即为后继,否则,后继为向祖先回溯过程中的第一个做为祖先左孩子的节点的父节点
    public TreeNode successor(TreeNode x){
        if (x == null){
            return null;
        }
        if (x.right != null){
            return minimum(x.right);
        }else{
            TreeNode y = x.p;
            while(y!=null && x == y.right){
                x = y;
                y = y.p;
            }
            return y;
        }
    }
    //如果存在左子树,前驱为左子树的最大节点,否则前驱为向其祖先回溯过程中第一个为其祖先的右孩子的节点的父节点
    public TreeNode predecessor(TreeNode x){
        if(x==null){
            return null;
        }
        if(x.left != null){
            return maximum(x.left);
        }else{
            TreeNode y = x.p;
            while(y!=null && x == y.left){
                x = y;
                y = y.p;
            }
            return y;
        }
    }
    // 中序遍历为有序序列
    public void walk(){
        inOrderTraversal(root);
    }
    // 查找值小于当前节点就到当前节点左子树,大于当前节点就到右子树,否则返回当前节点
    public TreeNode search(int key){
        TreeNode node = root;
        while(node!=null){
            if(key < node.key){
                node = node.left;
            }else if(key>node.key){
                node = node.right;
            }else{
                return node;
            }
        }
        return null;
    }

    public TreeNode recursiveSearch(TreeNode root, int key){
        if(root==null || root.key==key){
            return root;
        }else if(key>root.key){
            return recursiveSearch(root.right,key);
        }else{
            return recursiveSearch(root.left,key);
        }
    }
    // 待插入值小于当前节点就到当前节点左子树,否则跳就到右子树,直到叶子节点,根据最后的比较情况将当前节点作为该叶子节点的左孩子或者右孩子
    public void insert(TreeNode node){
        TreeNode p = null;
        TreeNode t = root;
        while(t != null){
            p = t;
            if(node.key < t.key){
                t = t.left;
            }else{
                t = t.right;
            }
        }
        node.p = p;
        if(p == null){
            root = node;
        }else if(node.key > p.key){
            p.right = node;
        }else{
            p.left = node;
        }
    }
    //分三种情况:1. 如果节点没有左子树或者右子树就直接将右孩子或左孩子替换当前节点    2. 如果既有左孩子,又有右孩子,且右孩子为当前节点的直接后继(右孩子没有左孩子),将节点右孩子替换当前节点并将当前节点左孩子连接到当前节点右孩子上    3. 否则,假设右子树的最小节点s(没有左孩子),首先将s的右孩子替换s,再用s替换当前节点,并将当前节点的左右孩子赋值给s的左右孩子
    public void delete(TreeNode node){
        if(node.left == null){
            transplant(node, node.right);
        }else if(node.right == null){
            transplant(node, node.left);
        }else{
            TreeNode s = minimum(node.right);
            if(s.p != node){
                transplant(s,s.right);
                s.right = node.right;
                s.right.p = s;
            }
            transplant(node,s);
            s.left = node.left;
            s.left.p = s;
        }
    }

    private void transplant(TreeNode u,TreeNode v){
        if(u.p == null){
            root = v;
        }else if(u == u.p.left){
            u.p.left = v;
        }else{
            u.p.right = v;
        }
        if(v != null){
            v.p = u.p;
        }
    }

    private TreeNode minimum(TreeNode x){
        if(root == null){
            return null;
        }
        while(x.left != null){
            x = x.left;
        }
        return x;
    }

    private TreeNode maximum(TreeNode x){
        if(x==null){
            return null;
        }
        while(x.right!=null){
            x = x.right;
        }
        return x;
    }

    private void inOrderTraversal(TreeNode root){
        if(root == null){
            return;
        }
        Stack<TreeNode> s = new Stack<TreeNode>();
        while(true){
            while(root!=null){
                s.push(root);
                root = root.left;
            }
            if(s.isEmpty()){
                return;
            }
            TreeNode node = s.pop();
            System.out.println(node.key);
            root = node.right;
        }
    }

验证

public class BinarySearchTreeDemo {    
    // 层序遍历打印一棵树,其中#代表null节点,为方便阅读去掉了代表叶子节点的null孩子的#符号
    public static void printTree(TreeNode root){
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        StringBuilder sb = new StringBuilder();
        q.offer(root);
        while(!q.isEmpty() ){
            TreeNode node = q.poll();
            if(node == null){
                sb.append("#");
                continue;
            }else{
                sb.append(node.key);
                q.offer(node.left);
                q.offer(node.right);
            }
        }
        int p=sb.length();
        while(p>0){
            if(sb.charAt(p-1)!='#'){
                break;
            }
            p--;
        }
        System.out.println(sb.substring(0,p).toString());
    }    
    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        TreeNode one = new TreeNode(1);
        TreeNode two = new TreeNode(2);
        TreeNode three = new TreeNode(3);
        TreeNode four = new TreeNode(4);
        TreeNode five = new TreeNode(5);
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(one);
        bst.insert(three);
        bst.insert(root);
        bst.insert(four);
        bst.insert(five);
        bst.insert(two);
        bst.walk();
        System.out.println(bst.minimum());
        System.out.println(bst.maximum());
        bst.delete(one);
        bst.walk();
        printTree(two);
        System.out.println(bst.search(1));
        System.out.println(bst.search(4));
        System.out.println(bst.predecessor(two));
        System.out.println(bst.successor(root));
    }
}  

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Java实现单词计数MapReduce
本文分享实现单词计数MapReduce的方法
0 0
JAVA 实现上传图片添加水印(详细版)(上)
JAVA 实现上传图片添加水印(详细版)
0 0
Java 实现汉字按照首字母分组排序
Java 实现汉字按照首字母分组排序
0 0
Java实现图书管理系统
本篇文章是对目前Java专栏已有内容的一个总结练习,希望各位小主们在学习完面向对象的知识后,可以阅览本篇文章后,自己也动手实现一个这样的demo来加深总结应用已经学到知识并进行巩固。
0 0
java实现spring boot项目启动时,重启Windows进程
java实现spring boot项目启动时,重启Windows进程
0 0
Java实现拼图小游戏(1)—— JFrame的认识及界面搭建
如果要在某一个界面里面添加功能的话,都在一个类中,会显得代码难以阅读,而且修改起来也会很困难,所以我们将游戏主界面、登录界面、以及注册界面都单独编成一个类,每一个类都继承JFrame父类,并且在类中创建方法来来实现页面
0 0
Java网络编程:UDP/TCP实现实时聊天、上传图片、下载资源等
ip地址的分类: 1、ipv4、ipv6 127.0.0.1:4个字节组成,0-255,42亿;30亿都在北美,亚洲就只有4亿 2011年就用尽了。
0 0
Java实现拼图小游戏(7)—— 计步功能及菜单业务的实现
注意由于我们计步功能的步数要在重写方法中用到,所以不能将初始化语句写在方法体内,而是要写在成员位置。在其名字的时候也要做到“见名知意”,所以我们给它起名字为step
0 0
Java实现拼图小游戏(7)—— 作弊码和判断胜利
当我们好不容易把拼图复原了,但是一点提示也没有,完全看不出来是成功了,那么我们就需要有判断胜利的功能去弹出“成功”类的图片,以便于玩家选择是重新开始还是退出小游戏
0 0
Java实现拼图小游戏(7)——查看完整图片(键盘监听实例2)
由于在移动和图片中我们已经添加了键盘监听,也继承了键盘监听的接口,那么我们只需要在重写方法内输入我们的代码即可
0 0
+关注
文章
问答
文章排行榜
最热
最新
相关电子书
更多
JAVA 应用排查全景图
立即下载
Java工程师必读手册
立即下载
Java应用提速(速度与激情)
立即下载