数据结构~基础2~树【《二叉树、二叉搜索树、AVL树、B树、红黑树》的设计】~二叉搜索树
一、 二叉搜索树：
| ❀ 二叉搜索树的特点： ● 整个二叉搜索树非常有特点，根大于左子树， 小于右子树 ● 二叉搜索数的中序遍历是有序的~升序的 |
■ 继承了二叉树，在其基础上有了增删功能：
❀ 二叉搜索树的通用接口：二叉树的通用接口 + 增加、删掉
■ 二叉搜索树增加和删除：
□ 从二叉搜索树的特点可以看出来，它是需要有比较机制的。
设计：内部是有一个比较器对象属性【用于接收用户传进来的比较器对象，当用户没有传入比较器时，使用强转，同理，让用户实现比较接口】：
//比较接口 private int compare(E e1, E e2) { // 如果外界传入了一个比较器 if (comparator != null) { // 使用比较器 return comparator.compare(e1, e2); } return ((Comparable<E>) e1).compareTo(e2); }
//二叉搜索树public class BST<E> extends BT<E> { // 比较器对象 private Comparator<E> comparator = null; //构造方法 public BST() { }; public BST(Comparator<E> comparator) { this.comparator = comparator; } }
■ 二叉搜索树增加接口：
□ 插入（添加）结点逻辑：从根结点开始，不断地比较【比根小，考虑左子树，比根大，考虑右子树，直到找到空位置【用于插入结点】
~~~插入时，判断是要添加到左结点还是右结点】
// 先找到父结点 Node<E> parent = root; Node<E> node = root; // 比较情况 int cmp = 0; while (node != null) { cmp = compare(element, node.elmement); //更新待插入结点的父结点 parent = node; if (cmp > 0) { node = node.right; } else if (cmp < 0) { node = node.left; } else { // 相等时，进行覆盖（因为如果是某个类对象进行比较的话，咱一般只用其某些属性进行比较，例如年龄相同的学生类：新传入的小虹可以覆盖掉小明） node.elmement = element; return; } } // node = new Node<E>(element, parent); Node<E> newNode = new Node<E>(element, parent); if (cmp > 0) { parent.right = newNode; } else { parent.left = newNode; }
■ 二叉搜索树删除接口：
□ 删除结点逻辑：【 删除本质上删除的是叶子结点 】
● 分类：
（1）删除度为2的结点：本质上删除的是它的前驱或者后驱【位置还是在叶子上】，
覆盖法，将前驱或者后驱的值直接覆盖到待删除的结点位置的值，然后删除前驱或后驱
前驱或者后驱结点【可能度为1，也可能度为0】（直接留给后边的情况（2、3）统一处理即可）。
（2）删除度为1的结点：说明度为1的那个左结点或者右结点是叶子结点啦，找到删除结点的父结点，
让父结点指向待删除结点的左结点【当待删除结点拥有的是左结点】或者右结点【当待删除结点拥有的是右结点】。
（3）删除度为0的叶子结点：直接让待删除结点的父节点指向空。
if(node.hasTwoChildren()) { //度为2 Node<E> s = sucessor(node); node.elmement = s.elmement; node = s; } //来到这里就是开始删除度为 1 或者为 0 的结点 //先考虑度为 1时 (要记得更改父结点) //用来替换的结点可能是待删除结点的左结点，也可能是右结点 Node<E> replaceNode = node.left != null ? node.left : node.right; if(replaceNode != null) { //度为 1 // (要记得更改父结点) replaceNode.parent = node.parent; //考虑特殊情况（根的情况）： if(replaceNode.parent == null) { root = replaceNode; }else if(node == node.parent.left) { //度为1是其左孩子 node.parent.left = replaceNode; }else { node.parent.right = replaceNode; } }else { //度为 0 //考虑特殊情况（根的情况）： if(node.parent == null) { root = null; }else if(node.parent.left == node) { //是叶子结点（是左边叶子） node.parent.left = null; }else { node.parent.right = null; } }
