MyException - 我的异常网
当前位置:我的异常网» 编程 » 数据结构-二叉查找树的java实现

数据结构-二叉查找树的java实现

www.MyException.Cn  网友分享于:2015-03-15  浏览:0次
数据结构--二叉查找树的java实现
上代码:
package com.itany.erchachazhaoshu;

public class BinarySearchTree<T extends Comparable<? super T>>
{
    //定义二叉查找树的根节点  每一个查找二叉树都有一个自己的root  节点 root外界看不到
    private BinaryNode<T> root;
    public BinarySearchTree()
    {
        root=null;
    }
    //节点类
    private static class BinaryNode<T>
    {
        private T element;
        private BinaryNode<T> left;
        private BinaryNode<T> right;
        public BinaryNode(T element)
        {
            this(element, null, null);
        }
        public BinaryNode(T element,BinaryNode<T> left,BinaryNode<T> right)
        {
            this.element=element;
            this.left=left;
            this.right=right;
        }
    }
    public void makeEmpty()
    {
        root=null;
    }
    public boolean isEmpty()
    {
        return root==null;
    }
    public boolean contains(T t)
    {
        return contains(t,root);
    }
    //外界是不认识节点的  只会返回T 布尔 或者根本无返回值
    public T findMax() throws Exception
    {
        if(isEmpty())
            throw new Exception();
        return findMax(root).element;
    }
    public T findMin() throws Exception
    {
        if(isEmpty())
            throw new Exception();
        return findMin(root).element;
    }
    public void insert(T t)
    {
        root=insert(t,root);
    }
    public void remove(T t)
    {
        root=remove(t,root);
    }
    //此处使用的是尾递归
    private boolean contains(T t,BinaryNode<T> root)
    {
        //必须在一开始就判断是否为null 否则在调用方法或元素时 会产生空指针异常  也是一个基准条件
        if(root==null)
            return false;
        int compareRes=t.compareTo(root.element);
        if(compareRes==0)
            return true;
        else if(compareRes<0)
            return contains(t,root.left);//不会使栈频繁进出 只会覆盖当前栈
        else
            return contains(t,root.right);
    }
    // 方法二 使用循环代替尾递归找出最大 是返回对应的那个节点
    private BinaryNode<T> findMax(BinaryNode<T> root)
    {
        if(root==null)
            return null;
        else
        {
            while(root.right!=null)
            {
                root=root.right  ;
            }
        }
        return root;
    }
    //方法一 使用递归查找 返回最小节点的引用
    private BinaryNode<T> findMin(BinaryNode<T> root)
    {
        //必须在一开始就判断是否为null 否则在调用方法或元素时 会产生空指针异常
        if(root==null)
            return null;
        //基准条件
        else if(root.left==null)
            return root;
        else
            return findMin(root.left);
    }
    //返回一个插入了之后的整个节点 逐级返回
    private BinaryNode<T> insert(T t,BinaryNode<T> root)
    {
        if(root==null)
            return new BinaryNode<T>(t,null,null);
        else
        {
            int com=t.compareTo(root.element);
            if(com==0)
                ;
            else if(com<0)
                //不断更新当前root的left值 并返回root
                root.left=insert(t,root.left);
            else
                root.right=insert(t,root.right);
            return root;
        }
    }
    //删除和增加一样 都要返回修改之后的节点
    private BinaryNode<T> remove(T t,BinaryNode<T> root)
    {
        //没有找到删除的  什么也不做  直接返回该root
        if(root==null)
            return root;
        int com=t.compareTo(root.element);
        if(com<0)
        {
            root.left=remove(t,root.left);
        }
        else if(com>0)
        {
            root.right=remove(t,root.right);
        }
        else
        {
            //有两个儿子的情况 
            if(root.left!=null && root.right!=null)
            {
                root.element=findMin(root.right).element;
                root.right=remove(root.element,root.right);//更新删除之后
            }
            else//包括一个儿子都没有的情况 有一个儿子的情况
                return (root.left!=null)?root.left:root.right;
                
        }
        return root;
    }
}
package com.itany.erchachazhaoshu;

public class Test
{
    
    public static void main(String[] args)
    {
        BinarySearchTree bt=new BinarySearchTree();
        bt.insert(3);
        bt.insert(13);
        bt.insert(1);
        try
        {
            System.out.println("max:"+bt.findMax());
            System.out.println("max:"+bt.findMin());
            System.out.println(bt.contains(3)); 
            bt.remove(13);
            System.out.println(bt.contains(13));
        }
        catch (Exception e)
        {
            e.printStackTrace();
        }
    }
    
}


文章评论

旅行,写作,编程
旅行,写作,编程
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
代码女神横空出世
代码女神横空出世
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
程序员和编码员之间的区别
程序员和编码员之间的区别
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
为什么程序员都是夜猫子
为什么程序员都是夜猫子
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
那些争议最大的编程观点
那些争议最大的编程观点
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
中美印日四国程序员比较
中美印日四国程序员比较
编程语言是女人
编程语言是女人
程序员应该关注的一些事儿
程序员应该关注的一些事儿
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
 程序员的样子
程序员的样子
如何成为一名黑客
如何成为一名黑客
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
漫画:程序员的工作
漫画:程序员的工作
总结2014中国互联网十大段子
总结2014中国互联网十大段子
程序员必看的十大电影
程序员必看的十大电影
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
10个调试和排错的小建议
10个调试和排错的小建议
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
每天工作4小时的程序员
每天工作4小时的程序员
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
鲜为人知的编程真相
鲜为人知的编程真相
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
程序员都该阅读的书
程序员都该阅读的书
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有