/**
* 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
{
BinaryNode left; // 保存节点的左孩子
BinaryNode right; // 保存节点的右孩子
// 定义构造函数，初始化成员
{
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;
}
// 查找树中是否存在某节点
{
return find2 ( x, root ).element;
}
// 查找树中最小的节点
{
return findMin2 ( root ).element;
}
// 查找树中最大的节点
{
return findMax2 ( root ).element;
}
// 向树中插入某节点
{
root = insert2 ( x, root );
}
// 删除树中某节点
{
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;
}
}