java 二叉查找树（增删改查操作）

[java]代码库
/**
 * java 二叉查找树（增删改查操作）
 */
public class Main
{
    public static void main ( String[] args )
    {
        BinarySearchTree btr = new BinarySearchTree();
        btr.insert ( 6 );
        btr.insert ( 2 );
        btr.insert ( 1 );
        btr.insert ( 3 );
        btr.insert ( 4 );
        btr.insert ( 8 );
        System.out.println ( btr.find ( 10 ) );
        System.out.println ( btr.findMin() );
        System.out.println ( btr.findMax() );
    }
}
 
// 定义树节点
class BinaryNode
{
    Comparable element; // 保存节点内容
    BinaryNode left; // 保存节点的左孩子
    BinaryNode right; // 保存节点的右孩子
 
    // 定义构造函数，初始化成员
    BinaryNode ( Comparable theElement )
    {
        this ( theElement, null, null );
    }
 
    BinaryNode ( Comparable theElement, BinaryNode lt, BinaryNode rt )
    {
        element = theElement;
        left = lt;
        right = rt;
    }
}
 
// 定义二叉查找树，将树节点封装成树并进行各种操作
class BinarySearchTree
{
    private BinaryNode root;
 
    public BinarySearchTree()
    {
        root = null;
    }
 
    // 判断树是否为空
    public boolean isEmpty()
    {
        return root == null;
    }
 
    // 查找树中是否存在某节点
    public Comparable find ( Comparable x )
    {
        return find2 ( x, root ).element;
    }
 
    // 查找树中最小的节点
    public Comparable findMin()
    {
        return findMin2 ( root ).element;
    }
 
    // 查找树中最大的节点
    public Comparable findMax()
    {
        return findMax2 ( root ).element;
    }
 
    // 向树中插入某节点
    public void insert ( Comparable x )
    {
        root = insert2 ( x, root );
    }
 
    // 删除树中某节点
    public void remove ( Comparable x )
    {
        root = remove2 ( x, root );
    }
 
    // 查找的具体操作,该操作对外是透明的,后面的操作同理
    private BinaryNode find2 ( Comparable x, BinaryNode t )
    {
        // 如果不存在，就新添加一个辅助树节点，并将其内容设为不存在
        if ( t == null )
        {
            BinaryNode s = new BinaryNode ( "不存在该元素！" );
            return s;
        }
 
        if ( x.compareTo ( t.element ) < 0 )   // 如果查找的元素比当前根节点小，则继续再该节点的左子树中查找，直至根节点为空
        {
            return find2 ( x, t.left );
        }
        else if ( x.compareTo ( t.element ) > 0 )   // 如果查找的元素比当前根节点大，则继续再该节点的右子树中查找，直至根节点为空
        {
            return find2 ( x, t.right );
        }
        else
            return t; // 如果查找的节点内容和当前根节点的内容相等，则返回当前根节点
    }
 
    // 找最小节点的具体过程
    private BinaryNode findMin2 ( BinaryNode t )
    {
        if ( t == null )
        {
            return null;
        }
        else if ( t.left == null )
        {
            return t;
        }
        return findMin2 ( t.left );
    }
 
    // 找最大节点的具体过程
    private BinaryNode findMax2 ( BinaryNode t )
    {
        if ( t != null )
        {
            while ( t.right != null )
            {
                t = t.right;
            }
        }
        return t;
    }
 
    // 构造二叉查找树的具体过程
    private BinaryNode insert2 ( Comparable x, BinaryNode t )
    {
        if ( t == null ) // 若树是空的，则构造一棵新的树，t为树的根
        {
            t = new BinaryNode ( x, null, null );
        }
        else if ( x.compareTo ( t.element ) < 0 )   // 如果要插入的元素小于当前节点，则插入在该节点的左边
        {
            t.left = insert2 ( x, t.left );
        }
        else if ( x.compareTo ( t.element ) > 0 )   // 如果要插入的元素大于当前节点，则插入在该节点的又边
        {
            t.right = insert2 ( x, t.right );
        }
        else
            ; // 否则什么也不做
        return t;
    }
 
    // 删除节点的具体操作过程
    private BinaryNode remove2 ( Comparable x, BinaryNode t )
    {
        if ( t == null )
        {
            return t;
        }
        if ( x.compareTo ( t.element ) < 0 )
        {
            t.left = remove2 ( x, t.left );
        }
        else if ( x.compareTo ( t.element ) > 0 )
        {
            t.right = remove2 ( x, t.right );
        }
        else if ( t.left != null && t.right != null )
        {
            t.element = findMin2 ( t.right ).element;
            t.right = remove2 ( x, t.right );
        }
        else
        {
            t = ( t.left != null ) ? t.left : t.right;
        }
        return t;
    }
}
用户注册

用户登录

发表随想

该用户最新代码

编程随想

[java]代码库

网友评论 (发表评论)

回复评论

发表评论：

评论须知：

扫码下载

输入口令后可复制整站源码
