十四、二叉搜索树--删除节点、clear和contains方法、

2022-01-24 本文已影响0人咸鱼Jay

删除节点 -- 叶子节点

当删除节点是叶子节点，则直接删除

删除节点 -- 叶子节点

当叶子节点是左子树(node == node.parent.left)
node.parent.left = null
当叶子节点是右子树(node == node.parent.right)
node.parent.right = null
当叶子节点是根节点(node.parent == null)
root = null

删除节点--度为1的节点

用 $\color{#00afef}{子节点} \color{#ed7d30}{替代}$ 原节点的位置
child是node.left或者child是node.right
用child替代node的位置
- 如果node是左子节点
  child.parent = node.parent
  node.parent.left = child
- 如果node是右子节点
  child.parent = node.parent
  node.parent.right = child
- 如果node是根节点
  root = child
  child.parent = null

删除节点--度为2的节点

举例：先删除 5、再删除 4
先用 $\color{#ed7d30}{前驱}$ 或者 $\color{#ed7d30}{后继}$ 节点的值 $\color{#ed7d30}{覆盖}$ 原节点的值
然后 $\color{#ed7d30}{删除}$ 相应的 $\color{#ed7d30}{前驱}$ 或者 $\color{#ed7d30}{后继}$ 节点
如果一个节点的度为 2，那么
它的 $\color{#ed7d30}{前驱}$ 、 $\color{#ed7d30}{后继}$ 节点的度只可能是1和0

代码实现：

public void remove(E element) {
    remove(findNode(element));
}

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;
        }
    } 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;
        }
    }
}

public Node<E> findNode(E element){
    Node<E> node = root;
    while(node != null) {
        int cmp = compare(element, node.element);
        if(cmp == 0) return node;
        if(cmp > 0) {
            node = node.right;
        }else {// cmp < 0
            node = node.left;
        }
    }
    return null;
}

clear和contains方法

public void clear() {
    root = null;
    size = 0;
}

public boolean contains(E element) {
    return findNode(element) != null;
}

代码重构--抽取BinaryTree类

我们把之前写的二叉搜索树(BinarySearchTree)一些方法抽到新定义的类BinaryTree里面。

BinaryTree类

import java.util.LinkedList;
import java.util.Queue;
import com.zxj.printer.BinaryTreeInfo;

@SuppressWarnings("unchecked")
public class BinaryTree<E> implements BinaryTreeInfo{
    protected Node<E> root;
    protected int size;
    
    // 元素的数量
    public int size() {
        return size;
    }
    
    // 是否为空
    public boolean isEmpty() {
        return size == 0; 
    }
    
    // 清空所有元素
    public void clear() {
        root = null;
        size = 0;
    }
    
    /**
     * 前序遍历
     */
    /*public void preorderTraversal() {
        preorderTraversal(root);
    }
    
    private void preorderTraversal(Node<E> node) {
        if(node == null) return;
        System.out.println(node.element);
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }*/
    
    public void preorder(Visitor<E> visitor) {
        if(visitor == null) return;
        preorder(root,visitor);
    }
    
    private void preorder(Node<E> node,Visitor<E> visitor) {
        if(node == null || visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        preorder(node.left,visitor);
        preorder(node.right,visitor);
    }
    
    /**
     * 中序遍历
     */
    /*public void inorderTraversal() {
        inorderTraversal(root);
    }
    
    private void inorderTraversal(Node<E> node) {
        if(node == null) return;
        inorderTraversal(node.left);
        System.out.println(node.element);
        inorderTraversal(node.right);
    }*/
    
    public void inorder(Visitor<E> visitor) {
        if(visitor == null) return;
        inorder(root,visitor);
    }
    
    private void inorder(Node<E> node,Visitor<E> visitor) {
        //这个visitor.stop是停止的递归遍历
        if(node == null || visitor.stop) return;
        inorder(node.left,visitor);
        //这个visitor.stop停止的是外界的打印
        if(visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        inorder(node.right,visitor);
    }
    
    /**
     * 后序遍历
     */
    /*public void postorderTraversal() {
        postorderTraversal(root);
    }
    
    private void postorderTraversal(Node<E> node) {
        if(node == null) return;
        postorderTraversal(node.left);
        postorderTraversal(node.right);
        System.out.println(node.element);
    }*/
    
    public void postorder(Visitor<E> visitor) {
        if(visitor == null) return;
        postorder(root,visitor);
    }
    
    private void postorder(Node<E> node,Visitor<E> visitor) {
        if(node == null || visitor.stop) return;
        postorder(node.left,visitor);
        postorder(node.right,visitor);
        if(visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
    }
    
    /**
     * 层序遍历
     */
    /*public void levelOrderTraversal() {
        if(root == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        
        while(!queue.isEmpty()) {
            Node<E> node = queue.poll();
            System.out.println(node.element);
            if(node.left != null) {
                queue.offer(node.left);
            }
            if(node.right != null) {
                queue.offer(node.right);
            }
        }
    }*/
    
    public void levelOrder(Visitor<E> visitor) {
        if(root == null || visitor == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        
        while(!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if(visitor.visit(node.element)) return;
            if(node.left != null) {
                queue.offer(node.left);
            }
            if(node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    
    /**
     * 是否是完全二叉树
     */
    public boolean isComplete() {
        if(root == null) return false;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        
        boolean leaf = false;
        while(!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if(leaf && !node.isLeaf()) {
                //如果要求你是叶子结点，但是你不是叶子结点
                return false;
            }
            
            if(node.left != null) {
                queue.offer(node.left);
            }else if(node.right != null) {
                // node.left == null && node.right != null
                return false;
            }
            
            if(node.right != null) {
                queue.offer(node.right);
            }else {// node.right == null
                leaf = true;
            }
        }
        return true;
    }
    
    /*public boolean isComplete() {
        if(root == null) return false;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        
        boolean leaf = false;
        while(!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if(leaf && !node.isLeaf()) {
                //如果要求你是叶子结点，但是你不是叶子结点
                return false;
            }
            
            if(node.hasTwoChildren()) {
                queue.offer(node.left);
                queue.offer(node.right);
            }else if (node.left == null && node.right != null) {
                return false;
            }else {// 后面遍历的结点都必须是叶子结点
                leaf = true;
                if(node.left != null) {
                    queue.offer(node.left);
                }
            }
        }
        return true;
    }*/
    
    public int height() {
        if(root == null) return 0;
        
        //树的高度
        int height = 0;
        // 存储着每一层的元素数量
        int levelSize = 1;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        
        while(!queue.isEmpty()) {
            Node<E> node = queue.poll();
            levelSize--;//levelSize减为0，代表这一层就访问完了。
            
            if(node.left != null) {
                queue.offer(node.left);
            }
            if(node.right != null) {
                queue.offer(node.right);
            }
            
            if(levelSize == 0) {//意味着即将要访问下一层
                levelSize = queue.size();
                height++;
            }
        }
        return height;
    }
    
    /**
     * 递归方法
     * @return
     */
    public int height2() {
        return height(root);
    }
    
    private int height(Node<E> node) {
        if(node == null) return 0;
        return 1 + Math.max(height(node.left),height(node.right));
    }
    
    /**
     * 前驱节点(predecessor)
     */
    protected Node<E> predecessor(Node<E> node){
        if(node == null) return null;
        
        // 前驱节点在左子树当中(left.right.right.right...)
        Node<E> p = node.left;
        if(p != null) {
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }
        
        // 从父节点、祖父节点中寻找前驱节点
        while(node.parent != null && node == node.parent.left) {
            //该节点的父节点不为空，并且该节点是父节点的左孩子
            node = node.parent;
        }
        // 第一种情况：node.parent == null
        // 第二种情况：node == node.parent.right
        return node.parent;
    }
    
    /**
     * 后继节点(successor)
     */
    protected Node<E> successor(Node<E> node){
        if(node == null) return null;
        
        // 后继节点在右子树当中(right.left.left.left...)
        Node<E> p = node.right;
        if(p != null) {
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }
        
        // 从父节点、祖父节点中寻找后继节点
        while(node.parent != null && node == node.parent.right) {
            //该节点的父节点不为空，并且该节点是父节点的右孩子
            node = node.parent;
        }
        // 第一种情况：node.parent == null
        // 第二种情况：node == node.parent.left
        return node.parent;
    }
    
    public static abstract class Visitor<E> {
        boolean stop;
        /**
         * @return 如果返回true，就代表停止遍历
         */
        public abstract boolean visit(E element);
    }
    
    protected static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;
        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }
        
        // 是否是叶子结点
        public boolean isLeaf() {
            return left == null && right == null;
        }
        
        // 是否有左右两个结点
        public boolean hasTwoChildren() {
            return left != null && right != null;
        }
    }
    
    @Override
    public Object root() {
        // 根节点是谁
        return root;
    }

    @Override
    public Object left(Object node) {
        // 如何查找左节点
        return ((Node<E>)node).left;
    }

    @Override
    public Object right(Object node) {
        // 如何查找右节点
        return ((Node<E>)node).right;
    }

    /*@Override
    public Object string(Object node) {
        // 如何打印每个节点
        return ((Node<E>)node).element;
    }*/
    
    @Override
    public Object string(Object node) {
        Node<E> myNode = (Node<E>)node;
        String parentString = null;
        if(myNode.parent != null) {
            parentString = myNode.parent.element.toString();
        }
        return myNode.element + "_p(" + parentString + ")";
    }
}

BST(BinarySearchTree)类

import java.util.Comparator;

/**
 * 二叉搜索树BST
 */
@SuppressWarnings("unchecked")
public class BST<E> extends BinaryTree<E> {
    
    
    private Comparator<E> comparator;
    
    public BST() {
        this(null);
    }
    
    public BST(Comparator<E> comparator){
        this.comparator = comparator;
    }
    
    // 添加元素
    public void add(E element) {
        elementNotNullCheck(element);
        
        // 添加第一个节点
        if(root == null) {
            root = new Node<>(element, null);
            size++;
            return;
        }
        
        // 添加的不是第一个节点
        Node<E> node = root;//找到父节点
        Node<E> parent = null;
        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<>(element,parent);
        if(cmp > 0) {
            parent.right = newNode;
        }else {
            parent.left = newNode;
        }
        size++;
    }

    // 删除元素
    public void remove(E element) {
        remove(findNode(element));
    }
    
    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;
            }
        } 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;
            }
        }
    }
    
    public Node<E> findNode(E element){
        Node<E> node = root;
        while(node != null) {
            int cmp = compare(element, node.element);
            if(cmp == 0) return node;
            if(cmp > 0) {
                node = node.right;
            }else {// cmp < 0
                node = node.left;
            }
        }
        return null;
    }

     // 是否包含某元素
    public boolean contains(E element) {
        return findNode(element) != null;
    }

    /**
     * 
     * @param e1
     * @param e2
     * @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);
    }
    
    private void elementNotNullCheck(E element) {
        if(element == null)
            throw new IllegalArgumentException("element must not be null !");
    }   
}

代码链接

十四、二叉搜索树--删除节点、clear和contains方法、

删除节点 -- 叶子节点

删除节点--度为1的节点

删除节点--度为2的节点

代码实现：

clear和contains方法

代码重构--抽取BinaryTree类

BinaryTree类

BST(BinarySearchTree)类

猜你喜欢

热点阅读