添加元素
注意添加元素后是否符合二叉搜索树的特性
- public void add(E element) {
- elementNotNullCheck(element); // 不能传入空节点
- // 传入第一个节点
- if(root == null){
- root = createNode(element, null);
- size++;
- // 新添加节点之后的处理
- afterAdd(root);
- return;
- }
- // 添加的不是第一个节点
- // 找到父节点
- Node<E> parent = root;
- Node<E> node = root;
- int cmp = 0;
- do {
- cmp = compareTo(node.element, element); // 方向
- parent = node; // 父节点
- if(cmp <0){
- node = node.right;
- }else if(cmp> 0){
- node = node.left;
- }else{ // 相等, 最好是覆盖掉, 也可以采取其他操作, 看具体需求
- node.element = element;
- return;
- }
- } while (node != null);
- // 插入到父节点的哪个位置
- Node<E> newNode = createNode(element, parent);
- if(cmp <0){
- parent.right = newNode;
- }else{
- parent.left = newNode;
- }
- size++;
- // 新添加节点之后的处理
- afterAdd(newNode);
- }
删除节点
删除的节点的度为 2
找到前驱节点或者后驱节点用代替被删除的节点
删除前驱或者后继节点
删除的节点的度为 1
判断 1. 是根节点 2. 节点的子树是左子树还是右子树
删除的节点的度为 0
是根节点 1. 直接使根节点为空
是叶子节点 2. 让看节点是父节点的左子树还是右子树是左或右为空
- private void remove(Node<E> node) {
- if (node == null) return;
- size--;
- if (node.hasTwoChildren()) { // 度为 2 的节点
- // 找到后继节点
- 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;
- }
- // 删除节点后的调整
- afterRemove(node);
- } else if (node.parent == null) { // node 是叶子节点并且是根节点
- root = null;
- // 删除节点后的调整
- afterRemove(node);
- } else { // node 是叶子节点, 但不是根节点
- if (node == node.parent.left) {
- node.parent.left = null;
- } else { // node == node.parent.right
- node.parent.right = null;
- }
- // 删除节点后的调整
- afterRemove(node);
- }
- }
取得元素的节点 (删除节点要用到的)
- private Node<E> node(E element){
- elementNotNullCheck(element);
- Node<E> node = root;
- while(node != null){
- int cmp = compareTo(element, node.element);
- if(cmp <0){
- node = node.left;
- }else if (cmp> 0){
- node = node.right;
- }else{ // cmp == 0
- return node;
- }
- }
- return null;
- }
根据传入的值删除元素
- public void remove(E element) {
- remove(node(element));
- }
来源: http://www.bubuko.com/infodetail-3641550.html