个人学习笔记--数据结构与算法--二叉搜索树（五）

以下是学习恋上数据结构与算法的学习笔记，本篇主要内容是二叉搜索树

◼二叉搜索树（Binary Search Tree）
二叉搜索树是二叉树的一种，是应用非常广泛的一种二叉树，英文简称为BST，又被称为：二叉查找树、二叉排序树。

●任意一个节点的值都大于其左子树所有节点的值
●任意一个节点的值都小于其右子树所有节点的值
●它的左右子树也是一棵二叉搜索树
●二叉搜索树可以大大提高搜索数据的效率
●二叉搜索树存储的元素必须具备可比较性，比如int、double等
●如果是自定义类型，需要指定比较方式，不允许为null

◼二叉搜索树的接口设计
●int size()// 元素的数量
●boolean isEmpty()// 是否为空
●void clear()// 清空所有元素
●void add(E element)// 添加元素
●void remove(E element)// 删除元素
●boolean contains(E element)// 是否包含某元素
●需要注意的是，对于我们现在使用的二叉树来说，它的元素没有索引的概念

简单的继承结构

◼添加节点

按照：任意一个节点的值都大于其左子树所有节点的值
任意一个节点的值都小于其右子树所有节点的值的原则，进行添加节点。

// 添加元素
	public void add(E element) {
		//判断元素是否为null
		elementNotNullCheck(element);
		//添加是否是根节点 第一个节点
		if(root==null) {
			root = new Node<> (element,null); //创建根节点
			size++;
			return ;
		}
		// 添加的不是第一个节点
		// 找到父节点 
		Node<E> parent = root;
		Node<E> node = root;
		int cmp=0;
		while(node!=null) {
			cmp=compare(element,node.element);//比较
			parent = node;//父节点
			if(cmp>0) {
				node = node.right;
			}else if(cmp<0) {
				node = node.left;
			}else {//相等
				node.element = element;//覆盖旧值
				return;
			}
		}
		//创建新节点
		Node<E> newNode = new Node<E>(element,parent);
		//看看插入到父节点的哪个位置
		//parent.left=node 或者parent.right=node
		if(cmp>0) {
			parent.right=newNode;
		}else {
			parent.left=newNode;
		}
		size++;
	}
	private void elementNotNullCheck(E element) {
		if(element==null) {
			throw new IllegalArgumentException("element must not be null");
		}
	}

而想进行添加节点，就必须进行比较元素的大小，这也是上面提到的，二叉搜索树存储的元素必须具备可比较性，比如int、double等。
◼元素的比较方案设计
●1.允许外界传入一个Comparator 自定义比较方案
●2.如果没有传入Comparator，强制认定元素实现了Comparable 接口

      /*
       *构造方法
       */
     public BinarySearchTree() {
		this(null);
	}
	// 是否包含某元素
	public boolean contains(E element) {
		return node(element) != null;
	}
	public BinarySearchTree(Comparator<E> comparator) {
		this.comparator = comparator;//外界传递的自定义比较器
	}
     /**
	 * @return 返回值等于0，代表e1和e2相等；返回值大于0，代表e1大于e2；返回值小于于0，代表e1小于e2
	 */
	private int compare(E e1, E e2) {
		//先调用比较器
		if(comparator !=null) {
			return comparator.compare(e1, e2);
		}
		//若无比较器，则默认可以比较，强制转化，  因为二叉搜索树默认需要可比较性
		return ((Comparable<E>)e1).compareTo(e2);
	}

◼根据元素内容获取节点
采用遍历二叉树，比较其值，相等则有值获取返回

//节点node方法 利用元素寻找节点    
	private Node<E> node(E element){
		Node<E> node=root;
		while(node!=null) {
			int cmp = compare(element, node.element);
			if(cmp==0) {
				return node;
			}else if(cmp>0) {
				node=node.right;
			}else {
				//cmp<0
				node=node.left;
			}
		}
		return null;
	}

◼删除

◼删除节点–叶子节点
●直接删除：3，5，8，10，7

◼删除节点–度为1的节点
●用子节点替代原节点的位置
◼删除节点–度为2的节点

◼举例：先删除5、再删除4
●先用前驱或者后继节点的值覆盖原节点的值
●然后删除相应的前驱或者后继节点
●如果一个节点的度为2，那么它的前驱、后继节点的度只可能是1 和0
删除实现

    //删除
	private void remove(Node<E> node) {
		//节点为null
		if(node ==null) return ;
		size--;
		//节点度为2
		if(node.hasTwoChildren()) {
			// 找到后继节点或者前驱节点
			Node<E> s=successor(node);
			// 用后继节点的值覆盖度为2的节点的值
			node.element=s.element;
			// 删除后继节点
			node=s;
		}
		// 删除node节点（node的度必然是1或者0） 找到代替节点 左子树或者右子树
		Node<E> replacement = node.left != null ? node.left : node.right;
		if (replacement != null) { // node是度为1的节点
			// 更改parent
			replacement.parent=node.parent;
			// 更改parent的left、right的指向
			if (node.parent == null) { // node是度为1的节点并且是根节点
				root=replacement;
			}else if (node == node.parent.left) {//左节点
				node.parent.left = replacement;
			}else { // node == node.parent.right  父节点时右节点
				node.parent.right = replacement;
			}
		} else if (node.parent == null) { // node是叶子节点并且是根节点
			root = null;
		} else { // node是叶子节点，但不是根节点
			if (node == node.parent.left) {
				node.parent.left = null;
			} else { // node == node.parent.right
				node.parent.right = null;
			}
		}
	}