Algorithms_二叉树&二分搜索树初探

class Node {
	E e;
	Node left ;  // 左孩子 
    Node right ; // 右孩子
}

/**
 * 
 * 
 * @ClassName: BinarySearchTree
 * 
 * @Description: 二分搜索树 --> 元素必须可以比较
 * 
 * @author: Mr.Yang
 * 
 * @date: 2020年2月8日 下午12:59:02
 * 
 * @param 
 */
public class BinarySearchTree<E extends Comparable<E>> {

	/**
	 * 
	 * @ClassName: Node
	 * 
	 * @Description: 数据节点类
	 * 
	 * @date: 2020年2月8日 下午12:58:44
	 */
	private class Node {
		private E e;// 数据
		private Node left; // 左孩子
		private Node right;// 右孩子

		public Node(E e) {
			this.e = e;
			this.left = null;
			this.right = null;
		}
	}

	private Node root;// 根节点
	private int size; // 当前数据量

	/**
	 * 
	 * 
	 * @Title:BinarySearchTree
	 * 
	 * @Description:默认构造函数
	 */
	public BinarySearchTree() {
		this.root = null;
		this.size = 0;
	}

	public int getSize() {
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	/**
	 * 
	 * 
	 * @Title: add
	 * 
	 * @Description: 向二分搜索树中添加新的元素e
	 * 
	 * @param e
	 * 
	 * @return: void
	 */
	public void add(E e) {
        // 根节点的非空判断
		if (root == null) {
			root = new Node(e);
			size++;
		} else
			add(root, e);
	}

	/**
	 * 
	 * 
	 * @Title: add
	 * 
	 * @Description: 向以node为根的二分搜索树中插入元素e，递归算法
	 * 
	 * @param node
	 * @param e
	 * 
	 * @return: void
	 */
	private void add(Node node, E e) {
		if (e.equals(node.e))
			return;
		else if (e.compareTo(node.e) < 0 && node.left == null) { // 插入到左子树
			node.left = new Node(e);
			size++;
			return;
		} else if (e.compareTo(node.e) > 0 && node.right == null) {// 插入到右子树
			node.right = new Node(e);
			size++;
			return;
		}
	    // 递归调用
		if (e.compareTo(node.e) < 0)
			add(node.left, e);
		else // e.compareTo(node.e) > 0
			add(node.right, e);
	}
}

/**
	 * 
	 * 
	 * @Title: add public 属性供外部调用
	 * 
	 * @Description: 向二分搜索树中添加新的元素e
	 * 
	 * @param e
	 * 
	 * @return: void
	 */
	public void add(E e) {
		root = add(root, e);
	}

	/**
	 * 
	 * 
	 * @Title: add 内部调用 私有 递归函数
	 * 
	 * @Description: 返回插入新节点后的二分搜索树的根
	 * 
	 * @param node
	 * @param e
	 * 
	 * @return: void
	 */
	private Node add(Node node, E e) {

		if (node == null) {
			size++;
			return new Node(e);
		}

		// 相等，不做任何操作
		if (e.compareTo(node.e) < 0) {
			node.left = add(node.left, e);
		} else if (e.compareTo(node.e) > 0) {
			node.right = add(node.right, e);
		}

		return node;
	}

/**
	 * 
	 * 
	 * @Title: contains 供外部调用
	 * 
	 * @Description: 判断元素e是否存二分搜索树中
	 * 
	 * @param e
	 * 
	 * @return: boolean
	 */
	public boolean contains(E e) {
		return contains(root, e);
	}

	/**
	 * 
	 * 
	 * @Title: contains 内部调用
	 * 
	 * @Description: 判断e是否存在于以node为根的二分搜索树中 递归算法
	 * 
	 * @param node
	 * @param e
	 * 
	 * @return: boolean
	 */
	private boolean contains(Node node, E e) {

		if (node == null) { // node为空 返回false
			return false;
		}

		if (e.compareTo(node.e) == 0) { // 相等 返回true
			return true;
		} else if (e.compareTo(node.e) < 0) { // 小, 继续递归左子树
			return contains(node.left, e);
		} else { // e.compareTo(node.e) > 0 大, 继续递归右子树
			return contains(node.right, e);
		}

	}