java 二分查找树

 

查询二叉树是平衡树->红黑树的基础，红黑树是TreeMap和TreeSet实现的基础。

深度：根到任意节点的唯一路径长，根节点的深度是零

高度：从节点到一片树叶的最长路径长，树叶的高度是零

二叉树：每个节点都不能有多余两个的儿子

public class BinarySearchTree<T extends Comparable<? super T>> {
	// 树的每个节点都是一个Node
	private static class Node<T> {
		/**
		 * 构造方法
		 */
		Node(T element) {
			this(element, null, null);
		}

		/**
		 * 构造方法
		 */
		Node(T element, Node<T> lt, Node<T> rt) {
			this.element = element;
			this.left = lt;
			this.right = rt;
		}

		// 每个节点的3个属性
		T element; // 要存储的值
		Node<T> left; // 左节点
		Node<T> right; // 右节点
	}

	/**
	 * 根节点
	 */
	private Node<T> root;

	/**
	 * 构造方法
	 */
	public BinarySearchTree() {
		root = null;
	}

	/**
	 * 设置树为空树
	 */
	public void makeEmpty() {
		root = null;
	}

	/**
	 * 判断树是否是空树
	 */
	public boolean isEmpty() {
		return root == null;
	}

	/**
	 * 判断当前树中是否包含元素为t的节点
	 */
	public boolean contains(T t) {
		return contains(root, t);
	}

	private boolean contains(Node<T> root, T t) {
		if (root == null)
			return false;// 空树返回false
		int i = t.compareTo(root.element);
		if (i > 0) // 比较节点右儿子
			return contains(root.right, t);
		else if (i < 0)// 比较节点左儿子
			return contains(root.left, t);
		else
			return true;
	}

	/**
	 * 查找最小值
	 */
	public T findMin() {
		if (isEmpty()) {
			throw new NullPointerException();
		}
		return findMin(root).element;
	}

	/**
	 * 递归 ：比较耗资源
	 */
	private Node<T> findMin(Node<T> root) {

		if (root.left == null)
			return root;
		return findMin(root.left);
	}

	/**
	 * 查找最大值
	 */
	public T findMax() {
		if (isEmpty()) {
			throw new NullPointerException();
		}
		return findMax(root).element;
	}

	/**
	 * 建议方式
	 */
	private Node<T> findMax(Node<T> root) {

		while (root.right != null) {
			root = root.right;
		}
		return root;
	}

	/**
	 * 添加元素
	 */
	public void add(T t) {
		root = add(root, t);
	}

	/**
	 * 过程
	 * 这里不考虑重复元素
	 * 重复元素，可以在Node<T>中加一个计数的域来处理，节省空间
	 * 还可以保存在一个辅助数据结构中，树||表？
	 */
	private Node<T> add(Node<T> node, T t) {
		if (node == null) {
			return new Node<T>(t);
		}
		int i = t.compareTo(node.element);
		if (i > 0)
			node.right = add(node.right, t);
		else if (i < 0)
			node.left = add(node.left, t);
		else
			; // 相等的不考虑
		return node;
	}

	/**
	 * 删除元素
	 */
	public void remove(T t) {
		remove(root, t);
	}

	/**
	 * 过程 删除节点只有一个儿子，直接删除节点， 用其儿子替换 
	 * 删除节点有两个儿子，取右儿子节点下的最小值 替换删除节点
	 */
	private Node<T> remove(Node<T> node, T t) {
		if (node == null) {
			return node;
		}
		int i = t.compareTo(node.element);

		if (i > 0) {
			node.right = remove(node.right, t);
		} else if (i < 0) {
			node.left = remove(node.left, t);
		} else if (node.right != null && node.left != null) {// 删除节点有两个儿子
			node.element = findMin(node.right).element;
			node.right = remove(node.right, node.element);
		} else {// 删除节点有一个儿子，或者没有儿子
			node = node.left == null ? node.right : node.left;
		}
		return node;
	}

	/**
	 * 打印
	 */
	public void printTree() {
		printTree(root);
	}

	/**
	 * 中序遍历：从小到大
	 */
	private void printTree(Node<T> node) {
		if (node != null) {
			printTree(node.left);// 先打印小的
			System.out.println(node.element); // 打印自己
			printTree(node.right);// 打印大的
		}
	}

	public static void main(String[] args) {

		BinarySearchTree<Integer> inter = new BinarySearchTree<Integer>();
		System.err.println(inter.isEmpty());
		inter.add(7);
		inter.add(4);
		inter.add(11);
		inter.add(2);
		inter.add(1);
		inter.add(3);
		inter.add(6);
		inter.add(5);
		inter.add(9);
		inter.add(10);
		inter.add(8);
		System.err.println(inter.isEmpty());
		System.err.println(inter.contains(4));
		System.err.println(inter.findMax());
		System.err.println(inter.findMin());
		inter.remove(7);
		inter.printTree();

	}
}

  输出：true
            false
            true
            11
            1
            1
            2
            3
            4
            5
            6
            8
            9
            10
            11

后续遍历：1、3、2、5、6、4 、8、10、9、11、7

先序便利：7、4、2、1、3、6、5、11、9、8、10

 

       如果删除次数不多，通常使用懒删除，即删除元素时它仍然留在树中，只是被标记删除。这特别在重复的时候特别有用，可以对计数域 -1

      如果树中实际节点和删除节点一样多，那么树的深度预计只上升一个小的常数。

      如果被删除的项是重新插入的，那么分配一个新单元的开销就避免了。