2-1、二叉查找树
废话少说，直接上代码
package 二叉查找树;/** * 二叉搜索树的实现，因为涉及到节点比较，所以节点元素需要实现Comparable接口，查找二叉树的特点是如果一个节点拥有左孩子和右孩子，那么左孩子一定小于它 * ，右孩子一定大于它，在这里，我们简单起见，不考虑节点元素相等的情况。 * * @author 梅东 * * @param <E> */public class BinarySearchTree<E extends Comparable<? super E>> {// 根节点private BinaryNode<E> root;/** * 构造函数，初始化为一颗空树 */public BinarySearchTree() {this.root = null;}/** * 将树清空 */public void makeEmpty() {this.root = null;}/** * 判断树是否为空 * * @return */public boolean isEmpty() {return this.root == null;}/** * 判断树是否包含某个元素 * * @param e * @return */public boolean contains(E e) {return contains(e, root);}/** * 查找最小的元素 * * @return */public E findMin() {if (isEmpty())throw new TreeEmptyException();return findMin(root).element;}/** * 查找最大的元素 * * @return */public E findMax() {if (isEmpty())throw new TreeEmptyException();return findMax(root).element;}/** * 插入某个元素 * * @param e */public void insert(E e) {this.root = insert(e, this.root);}/** * 删除某个元素 * * @return */public void remove(E e) {this.root = remove(e, this.root);}/** * 查找是否包含此元素，采用递归比较法 * * @param e * @param root * @return */private boolean contains(E e, BinaryNode<E> root) {// 空树，返回falseif (root == null)return false;// 比较结果int compareResult = e.compareTo(root.element);// 小于则继续和该节点的左孩子节点比较if (compareResult < 0)return contains(e, root.leftChild);// 大于则和右孩子节点比较else if (compareResult > 0)return contains(e, root.rightChild);else// 相等，返回truereturn true;}/** * 查找最大的节点元素 * <p> * 考虑到查找二叉树的特点，如果树不为空，并且根节点拥有左子树， * <p> * 那么最小节点元素肯定是在左子树中， 所以可以采取递归查找左子树的方式来实现 * * @param root * @return */private BinaryNode<E> findMin(BinaryNode<E> root) {// 空树，说明不存在最小元素，返回Nullif (root == null)return null;// 根节点没有左子树，那么根肯定是最小元素，将其返回else if (root.leftChild == null)return root;// 左子树不为空，那么就去左子树中递归查找最小元素elsereturn findMin(root.leftChild);}/** * 查找最大元素 * <p> * 其实最大元素可以顺着右孩子往下搜索，查找最小元素也是同样原理， * <p> * 上例我采用了递归，是为了演示递归的用法， 查找最大元素我采用循环查找右孩子节点的实现 * * @param root * @return */private BinaryNode<E> findMax(BinaryNode<E> root) {if (root != null)while (root.rightChild != null)root = root.rightChild;return root;}/** * 插入节点元素 * <p> * 考虑到查找二叉树的特性，插入的新节点肯定是作为叶子插入的，所以插入是很简单的， * <p> * 关键点是找到插入位置，其实很简单， 对于某个特定根节点来说，要插入的节点元素如果小于该节点， * <p> * 则将其插入到左子树中，并将根节点的左子树设为插入节点元素后的左子树， * <p> * 否则插入到该节点右子树中，因此，我们可以递归的实现这个插入过程。 * * @param e * @param root * @return */private BinaryNode<E> insert(E e, BinaryNode<E> root) {// 树为空，则以该节点为根创建一个新树返回if (root == null)return new BinaryNode<E>(e);int compareResult = e.compareTo(root.element);// 插入到左子树中if (compareResult < 0)root.leftChild = insert(e, root.leftChild);// 插入到右子树中else if (compareResult > 0)root.rightChild = insert(e, root.rightChild);// 将插入节点元素的新树返回return root;}/** * <p> * 删除某个节点元素 * <p> * 删除元素有点复杂，倘若要删除的元素是叶子，则很简单，直接将其父节点指向该节点的引用设为null * <p> * 如果要删除的节点只有一课子树，那么只需将父节点指向该节点的引用直接指向该节点的子树就行了 * <p> * 如果有两棵子树，情况略微复杂。要满足二叉查找树的特性，即左孩子小于根节点，右孩子大于根节点 * <p> * 则需将右子树中最小的节点移到要删除的节点位置上，也就是将该节点的元素设为右子树中最小节点的元素 * <p> * 并将那个最小节点删除，显而易见，最小节点本来就是右子树中的叶子，对其删除很容易。 * * @param e * @param root * @return */private BinaryNode<E> remove(E e, BinaryNode<E> root) {// 空树无需删除if (root == null)return null;int compareResult = e.compareTo(root.element);// 小于根节点，则到左子树中去删除，并将完成删除工作的左子树的根节点重新赋值给该节点的的左孩子if (compareResult < 0)root.leftChild = remove(e, root.leftChild);// 大于根节点，则到右子树中去删除，过程和上面类似else if (compareResult > 0)root.rightChild = remove(e, root.rightChild);// 和根节点相等，说明根节点就是要删除的节点，此时考虑左右孩子都存在的情况else if (root.leftChild != null && root.rightChild != null) {root.element = findMin(root.rightChild).element;root.rightChild = remove(root.element, root.rightChild);} else {// 只有单个孩子的情况root = root.leftChild != null ? root.leftChild : root.rightChild;}return root;}/** * 静态内部类，树节点的实现 * * @author 梅东 * * @param <E> */private static class BinaryNode<E> {// 节点元素E element;// 左孩子节点BinaryNode<E> leftChild;// 右孩子节点BinaryNode<E> rightChild;public BinaryNode(E element) {this(element, null, null);}public BinaryNode(E element, BinaryNode<E> leftChild, BinaryNode<E> rightChild) {this.element = element;this.leftChild = leftChild;this.rightChild = rightChild;}}}