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