加载中…
个人资料
诗意地歪歪
诗意地歪歪
  • 博客等级:
  • 博客积分:0
  • 博客访问:14,763
  • 关注人气:3
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
正文 字体大小:

二叉查找树--查找、删除、插入(Java实现)

(2013-05-06 23:02:17)
标签:

java

查找

删除

插入

二叉树

it

二叉查找树

                 二叉查找树(Binary Search Tree),或者是一颗空树,或者是具有下列性质的二叉树:

                       1、若它的左子树不空,则其左子树上的所有结点的值均小于它根结点的值;

                       2、若它的右子树不空,则其右子树上的所有结点的值均大于它根结点的值;

                       3、它的左、右子树也分别为二叉查找树。

                                                  

                 二叉查找树是基于二叉树的,其结点数据结构定义为如下:

[java] view plaincopy
  1.   
  2. static class BinaryNode  
  3.  
  4.     data;  
  5.     BinaryNode left;  
  6.     BinaryNode right;  
  7.     public BinaryNode(T data)  
  8.         this(data,null,null);  
  9.      
  10.     public BinaryNode( data, BinaryNode left, BinaryNode right)  
  11.         this.data =data;  
  12.         this.left left;  
  13.         this.right =right;  
  14.      
  15.     public BinaryNode()  
  16.      
  17.         data =null 
  18.         this.left left;  
  19.         this.right =right;  
  20.      
  21.  

 

                 现在明白了什么是二叉查找树,那么二叉查找书的基本操作又是如何来实现的呢?                

          查找操作

                       在二叉查找树中查找x的过程如下:

                             1、若二叉树是空树,则查找失败。

                             2、若x等于根结点的数据,则查找成功,否则。

                             3、若x小于根结点的数据,则递归查找其左子树,否则。

                             4、递归查找其右子树。

                     根据上述的步骤,写出其查找操作的代码: 

 

[java] view plaincopy
  1.   
  2.    public boolean contains(T t)  
  3.     
  4.       return contains(t, rootTree);  
  5.          
  6.     
  7.    
  8.    public boolean contains(T t, BinaryNode node)  
  9.     
  10.       if(node==null 
  11.         return false;//结点为空,查找失败  
  12.       int result t.compareTo(node.data);  
  13.        if(result>0 
  14.           return contains(t,node.right);//递归查询右子树  
  15.       else if(result<</SPAN>0 
  16.           return contains(t, node.left);//递归查询左子树    
  17.       else  
  18.           return true 
  19.     
  20.       
  21.    
  22.   
  23.    
  24.    public findMin()  
  25.     
  26.       if(isEmpty())  
  27.        
  28.           System.out.println("二叉树为空");  
  29.           return null 
  30.       }else  
  31.        return findMin(rootTree).data;  
  32.          
  33.     
  34.      
  35.    public findMax()  
  36.     
  37.        if(isEmpty())  
  38.            
  39.               System.out.println("二叉树为空");  
  40.               return null 
  41.           }else  
  42.            return findMax(rootTree).data;  
  43.     
  44.   
  45.   
  46.    public BinaryNode findMin(BinaryNode node)  
  47.     
  48.        if(node==null 
  49.            return null 
  50.        else if(node.left==null 
  51.            return node;  
  52.        return findMin(node.left);//递归查找  
  53.     
  54.      
  55.    public BinaryNode findMax(BinaryNode node)  
  56.     
  57.        if(node!=null 
  58.         
  59.            while(node.right!=null 
  60.                node=node.right;  
  61.         
  62.        return node;         
  63.     

 

           插入操作

                     二叉树查找树b插入操作x的过程如下:

                        1、若b是空树,则直接将插入的结点作为根结点插入。

                        2、x等于b的根结点的数据的值,则直接返回,否则。

                        3、若x小于b的根结点的数据的值,则将x要插入的结点的位置改变为b的左子树,否则。

                        4、将x要出入的结点的位置改变为b的右子树。

               代码实现如下:

 

[java] view plaincopy
  1.   
  2.    public void insert(T t)  
  3.     
  4.        rootTree insert(t, rootTree);  
  5.     
  6.   
  7.    public BinaryNode insert(T t,BinaryNode node)  
  8.     
  9.        if(node==null 
  10.         
  11.            //新构造一个二叉查找树  
  12.            return new BinaryNode(t, nullnull);  
  13.         
  14.        int result t.compareTo(node.data);  
  15.        if(result<</SPAN>0 
  16.           node.left= insert(t,node.left);  
  17.        else if(result>0 
  18.           node.right= insert(t,node.right);  
  19.        else  
  20.            ;//doNothing  
  21.        return node;  
  22.     

 

          删除操作

                         对于二叉查找树的删除操作(这里根据值删除,而非结点)分三种情况:

                   不过在此之前,我们应该确保根据给定的值找到了要删除的结点,如若没找到该结点

                   不会执行删除操作!

                      下面三种情况假设已经找到了要删除的结点。

                        1、如果结点为叶子结点(没有左、右子树),此时删除该结点不会玻化树的结构

                             直接删除即可,并修改其父结点指向它的引用为null.如下图:

                

                       2、如果其结点只包含左子树,或者右子树的话,此时直接删除该结点,并将其左子树

                              或者右子树设置为其父结点的左子树或者右子树即可,此操作不会破坏树结构。
                 
                           

                       3、 当结点的左右子树都不空的时候,一般的删除策略是用其右子树的最小数据

                            (容易找到)代替要删除的结点数据并递归删除该结点(此时为null),因为

                              右子树的最小结点不可能有左孩子,所以第二次删除较为容易。

                               z的左子树和右子树均不空。找到z的后继y,因为y一定没有左子树,所以可以删除y,

                              并让y的父亲节点成为y的右子树的父亲节点,并用y的值代替z的值.如图:

                    

                  删除操作源码:

 

[java] view plaincopy
  1.   
  2.    public void remove(T t)  
  3.     
  4.        rootTree remove(t,rootTree);  
  5.      
  6.    public BinaryNode remove(T t,BinaryNode node)  
  7.     
  8.        if(node == null 
  9.            return node;//没有找到,doNothing  
  10.        int result t.compareTo(node.data);  
  11.        if(result>0 
  12.            node.right remove(t,node.right);  
  13.        else if(result<</SPAN>0 
  14.            node.left remove(t,node.left);  
  15.        else if(node.left!=null&&node.right!=null 
  16.         
  17.            node.data findMin(node.right).data;  
  18.            node.right remove(node.data,node.right);  
  19.         
  20.        else  
  21.            node (node.left!=null)?node.left:node.right;  
  22.        return node;  
  23.              
  24.     

 

             完整源码

[java] view plaincopy
  1. "code" class="java">package com.kiritor;  
  2.   
  3. public class BinarySearchTreeextends Comparable

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有