- /**
- * 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;
- }
- }
来源: http://www.phpxs.com/code/1002372/