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

}
</pre>