java 二叉查找树（增删改查操作），,/** * java 二

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 &amp;&amp; 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;    }}