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