二叉搜索树

一、添加

• 步骤
  1、找到父节点 parentNode
  2、创建新节点node
  3、parentNode.left = node 或者parentNode.right = node

    public void add(E element) {
        //验证添加的节点里数据是否为空
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
        
        // 添加第一个节点
        if (root == null) {
            //createNode() 是根据 要添加的数据 和父节点null 创建一个新节点
            root = createNode(element, null);
            size++; //维护二叉树的size
            // 新添加节点之后的处理
            afterAdd(root);
            return;
        }
        
        // 添加的不是第一个节点
        // 找到父节点
        Node<E> parent = root;
        Node<E> node = root;
        int cmp = 0;
        do {
            //compare() 返回值等于0，代表e1和e2相等；返回值大于0，代表e1大于e2；返回值小于于0，代表e1小于e2
            //compare()  方法可以用自己在创建二叉搜索树时传入的比较器 也可以用默认的比较器
            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;
            }
        } while (node != null);

        // 看看插入到父节点的哪个位置
        Node<E> newNode = createNode(element, parent);
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        // 新添加节点之后的处理
        afterAdd(newNode);
        size++;
    }

二、删除

1、前驱

• node节点的前驱节点为 中序遍历中node的前一个节点

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

        return node.parent;
    }

2、后继

• node节点的后继节点为 中序遍历中node的后一个节点

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

        return node.parent;
    }

3、删除操作

    private void remove(Node<E> node) {
        
        if (node == null) return;
        //维护size
        size--;

        // 度为2的节点 
        if (node.hasTwoChildren()) { 
            // 找到后继节点
            Node<E> s = successor(node);
            // 用后继节点的值覆盖度为2的节点的值
            node.element = s.element;
            // 删除后继节点  删除的节点是后继节点 后继节点必是度为1或0 
            // 所以这里之后 都为处理度为1或0 的节点删除
            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(replacement);
        } 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);
        }
    }

• 删除语言描述
  1、 先处理删除度为2的节点。找到度为2节点的前驱或者后继 覆盖删除节点的内容、删除前驱或者后继节点。
  2、删除度为1 并且不是根节点的节点 该节点的父节点直接指向该节点的子节点
  3、删除叶子节点并且是根节点的节点 root = null
  4、删除叶子节点但不是根节点 判断该叶子节点在父节点的左还是右 parent.left = null 或者 parent.right = null。
  注意
  1、删除度为2的节点 真正删除的是该节点的前驱或者后继节点
  2、度为2 的节点的前驱或者后继节点 必是度为0 或 1 的节点
  3、删处节点之后的处理afterRemove(node); 这代码是以后平衡二叉树做准备的

三、 遍历

1、二叉搜索树的 前序遍历

前序遍历就是把父节点先打出来 父 左 右

private void preorderTraversal(Node<E> node) {
    if (node == null) return;
    System.out.println(node.element);
    preorderTraversal(node.left);
    preorderTraversal(node.right);
}

2、二叉搜索树的 中序遍历

中序遍历就是 左 父 右

private void inorderTraversal(Node<E> node) {
    if (node == null) return;
    preorderTraversal(node.left);
    System.out.println(node.element);
    preorderTraversal(node.right);
}

3、二叉搜索树的 后续遍历

中序遍历就是 左 父 右

private void postorderTraversal(Node<E> node) {
    if (node == null) return;
    preorderTraversal(node.left);
    preorderTraversal(node.right);
    System.out.println(node.element);
}

前中后序遍历总结
1、递归调用没一个节点 在不同的实际 打印节点的内容 就可得到三种遍历的结果
2、如果二叉搜索树里面存的是 int 类型数据 二叉搜索树的比较器是左边放小的 右边放大的 的话 中序遍历就是 整棵树所存的数据 从小到大排序

4、二叉搜索树的 层序遍历

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

4、二叉搜索树的 高度

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