二叉搜索树

1、思考

• 在n个动态的整数中搜索某个整数？即查看是否存在。

如果使用动态数组存储元素，从第0个元素开始遍历搜索，那么平均时间复杂度为O(n)。
如果动态数组中存储的是有序元素，那么使用二分法查找，最坏时间复杂度为O(logn)。但是添加、删除的平均时间复杂度为O(n)。

• 针对这个需求有没有更好的方案呢？

使用二叉搜索树，添加、删除、搜索的最坏时间复杂度可以优化至O(logn)。

2、二叉搜索树（Binary Search Tree）

二叉搜索树是二叉树的一种，应用比较广泛，又被称为二叉查找树、二叉排序树。
二叉搜索树的特点：

1、任意一个节点的值都大于其左子树所有节点的值。
2、任意一个节点的值都小于其右子树所有节点的值。
3、它的左右子树同样是一个二叉搜索树。
4、二叉搜索树中存储的元素必须具有可比较性。
- a、比如int、double类型数据（其包装类内部已经实现了Comparable接口使其具有可比较性）。如果是自定义的类型，需要自己指定比较方式。
- b、元素不能为null。null不能进行比较。
5、二叉搜索树可以大大提高搜索的效率。
下图中表示的就是一个二叉搜索树：

image.png

2.1、接口设计

//元素的数量
public int size() {}

//元素是否为空
public boolean isEmpty() {}

//清空元素
public void clear() {}

//添加元素
public void add(E element) {}

//删除元素
public void remove(E element) {}

//是否包含某个元素
public boolean contains(E element) {}

注意：对于我们现在使用的二叉树中，并不存在索引的概念。这又是为什么呢？
比如将如下数据添加到二叉搜索树中

8,3,10，1,6,14，4,7,13

效果如下图

image.png

然后我们再添加一个9，此时二叉搜索树如下图

image.png
新添加的元素在第三层，而正常来说应该在最后添加元素的后面，即在最后一层节点13的右边，所以索引对二叉树来说并没有什么意义。

2.2、添加元素add(E element)

添加的步骤：

• 1、找到parent节点。
• 2、新建node节点。
• 3、新建的节点可能在parent的左边，也可能在parent的右边。代码表示为parent.left=node或parent.right=node。
  从上可知：一个节点需要包含元素的值、left节点、right节点、parent节点。增加一个内部类：

private static class Node<E> {
    E element;
    Node<E> left;
    Node<E> right;
    Node<E> parent;

    public Node(Node<E> left, E element, Node<E> right) {
        this.element = element;
        this.left = left;
        this.right = right;
    }
}

• 1、由于二叉搜索树中的元素不能为null，在添加前需要进行判断。
• 2、添加的第一个节点为根节点root。
• 3、如果添加的不是第一个节点，则需要找到要添加节点的父节点。从根节点开始查找，根据二叉搜索树的特性，如果要添加的节点元素的值大于根节点的值，则在根节点的右子树中去查找。然后再和右子树的根节点进行判断，在右子树的左子树或右子树中去查找，直到节点的left或者right等于null。具体实现如下：

// 添加元素
public void add(E element) {
    // 由于二叉搜索树中不能添加null元素，需要进行判断
    elementNotNullCheck(element);

    // 添加第一个节点
    if (root == null) {
        root = new Node<>(element, null);
        size++;
        return;
    }
    // 不是第一个节点
    // 找到parent节点
    Node<E> node = root;
    Node<E> parent = 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节点
    Node<E> newNode = new Node<>(element, parent);
    if (cmp > 0) {
        parent.right=newNode;
    }else if(cmp<0) {
        parent.left=newNode;
    }
    // paent.left=node或parent.right=node
    size++;
}

其中compare()方法我们还没有去实现，下面看下如何实现。
二叉搜索树中可以存入任何类型的元素，比如int，其包装类的内部已经实现了Comparable接口，它是可比较的。如果元素类型为自定义的，比如Person类型的，此时就需要让Person类实现Comparable接口。

public class Person implements Comparable<Person> {
    private int age;

    public Person(int age) {
        this.age = age;
    }

    public int getAge() {
        return age;
    }

    @Override
    public int compareTo(Person person) {
        return this.age - person.age;
    }
}

但是这样的话，如果我们想修改比较方式，就需要修改Person中compareTo()的具体实现，可是其他地方还想使用Person的原有的比较方式呢？我们可以让外部决定比较方式，具体实现如下：

public BinarySearchTree() {
    this(null);
}

public BinarySearchTree(Comparator<E> comparator) {
    this.comparator = comparator;
}

private int compare(E e1, E e2) {
    if (comparator != null)
        return comparator.compare(e1, e2);
    return ((Comparable<E>) e1).compareTo(e2);
}

注意：如果遇到相同的值，我们这里直接将值进行了覆盖，如果二叉搜索树中传入的基本类型的值，覆盖和不覆盖并没有什么意义，但是如果传入的是自定义类型的话，比如Person，如果传入的两个Person年龄相同，但是其他属性不同的话，建议进行覆盖。

2.3、打印二叉树

工具：打印二叉树
将BinarySearchTree实现接口BinaryTreeInfo，并实现方法

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

然后调用BinaryTrees.println(bst)

BinarySearchTree<Person> bst = new BinarySearchTree<Person>();
int[] array = { 8, 3, 10, 1, 6, 14, 4, 7, 13, 9 };
String[] nameArray = { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J" };
for (int i = 0; i < array.length; i++) {
    bst.add(new Person(array[i], nameArray[i]));
}
BinaryTrees.println(bst);

效果如下图

image.png

2.4、删除节点

2.4.1、删除叶子节点

删除叶子节点，直接删除即可。
下图中的节点3 5 8 10以及节点7都是叶子节点。

image.png
下面看下如何删除叶子节点：

• 1、node.parent ! = null
  如果node==node.parent.left，则node.parent.left==null;
  如果node==node.parent.right，则node.parent.right.right=null;
• 2、node.parent==null，node是根节点
  root=null;

2.4.2、删除度为1的节点

用子节点代替原节点的位置
下图中的**4、9、9 **都是要删除的度为1的节点

image.png

• 1、child是node.left或者child是node.right。
• 2、用child来替代node的位置。
• 3、如果node.parent != null
  - 1、如果node是node.parent左子节点
  - a、child.parent=node.parent;
  - b、node.parent.left = child;
  -2 、如果node是node.parent的右子节点
  - a、child.parent=node.parent;
  - b、node.parent.right=child;
• 4、如果node.parent==null，node是根节点
  - a、child.parent=null;
  - b、root=child;

2.4.3、删除度为2的节点

比如删除下图中节点5

image.png

• 1、先用前驱或者后继节点的值，覆盖要删除的节点的值
• 2、然后再删除相应的前驱或后继节点。
• 3、如果要删除的节点度为2，那么它的前驱或后继节点的度只能为1或0。
  所以删除度为2的节点，其实最终删除的是度为1或0的节点。

2.4.4、删除的具体实现

我们知道删除度为2的节点，其实最终会转化成删除度为1的节点或者删除叶子节点，所以为了避免重复判断，可以将删除度为2的节点逻辑写在最前面。

private void remove(Node<E> node) {
    if (node == null)
        return;
    // 删除度为2的节点
    if (node.hasTwoChildren()) {
        // 找到前驱节点
        Node<E> precurNode = precursor(node);
        // 用前驱节点的值覆盖要删除节点的值
        node.element = precurNode.element;
        // 删除前驱节点
        node = precurNode;
    }

    // 删除的node节点的度为1或0
    Node<E> child = node.left != null ? node.left : node.right;
    if (child != null) { // 度为1的节点
        // 使用子节点替代要删除节点的位置
        child.parent = node.parent;
        if (node.parent == null)
            root = child;
        else if (node == node.parent.left)
            node.parent.left = child;
        else if (node == node.parent.right)
            node.parent.right = child;
    } // 删除叶子节点
    else if (node.parent == null)
        root = null;
    else if (node == node.parent.left)
        node.parent.left = null;
    else if (node == node.parent.right)
        node.parent.right = null;
    size--;
}

完整代码如下

public class BinarySearchTree<E> implements BinaryTreeInfo {

    private int size;
    // 根节点
    private Node<E> root;

    private Comparator<E> comparator;

    public static abstract class Visitor<E> {
        public boolean stop;

        public abstract boolean visit(E e);
    }

    public BinarySearchTree() {
        this(null);
    }

    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    // 元素的数量
    public int size() {
        return size;
    }

    // 元素是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 清空元素
    public void clear() {
        size = 0;
        root = null;
    }

    public void levelorderTraserval() {
        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 add(E element) {
        // 由于二叉搜索树添加的元素不能为null
        elementNotNullCheck(element);

        // root等于null 第一次添加
        if (root == null) {
            root = new Node<>(element, null);
            size++;
            return;
        }
        // 非第一次添加 元素添加的步骤
        // 1、找到要添加节点的parent节点
        Node<E> node = root;
        Node<E> parent = 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;
            }
        }
        // 2、创建新的节点
        Node<E> newNode = new Node<>(element, parent);
        // 3、该节点是parent的左子节点还是右子节点
        if (cmp > 0) {
            parent.right = newNode;
        } else if (cmp < 0) {
            parent.left = newNode;
        }
        size++;
    }

    public void preorder(Visitor<E> visitor) {
        if (visitor == null)
            return;
        preorder(root, visitor);
//      preorder2();
    }

    // 前序遍历---递归方式
    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);
    }

    // 前序遍历---迭代方式：使用栈来实现
    /**
     * 1、将root入栈 2、弹出栈顶元素 3、将栈顶元素的右子节点入栈 4、将栈顶元素的左子节点入栈 5、栈为空则结束遍历
     */
    private void preorder2() {
        if (root == null)
            return;
        Stack<Node<E>> stack = new Stack<>();
        Node<E> node = root;
        stack.add(node);
        while (!stack.isEmpty()) {
            node = stack.pop();
            System.out.println(node.element);
            if (node.right != null)
                stack.add(node.right);
            if (node.left != null)
                stack.add(node.left);
        }
    }

    public void inorder(Visitor<E> visitor) {
        if (visitor == null)
            return;
        inorder(root, visitor);
//      inorder2();
    }

    // 中序遍历--递归方式实现
    private void inorder(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop)
            return;
        inorder(node.left, visitor);
        // 在遍历左子树时visitor.stop可能已经为true，所以需要在此处加上判断
        if (visitor.stop)
            return;
        visitor.stop = visitor.visit(node.element);
        inorder(node.right, visitor);
    }

    /**
     * 中序遍历--使用迭代方式实现--使用栈来实现 1、设置node=root 2、进行如下循环操作： 1、如果node！=null a、将node入栈
     * b、设置node=node.left 2、如果node==null a、如果栈为空则结束循环 b、将栈顶元素出栈，并赋值给node c、对node进行访问
     * d、设置node=node.right
     */
    private void inorder2() {
        if (root == null)
            return;
        Stack<Node<E>> stack = new Stack<>();
        // 设置node=root
        Node<E> node = root;
        while (true) {
            /**
             * 如果node不为空，将node加入到栈中 设置node=node.left
             */
            if (node != null) {
                stack.add(node);
                node = node.left;
            } else {
                /**
                 * 如果node==null 此时如果栈为空，则退出循环 将栈顶元素出栈，并赋值给node 访问node 设置node=node.right
                 */
                if (stack.isEmpty())
                    break;
                node = stack.pop();
                System.out.println(node.element);
                node = node.right;
            }

        }

    }

    // 后序遍历
    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);
    }

    /**
     * 后序遍历---使用迭代方式实现
     * 
     */
    private void postorder2() {

    }

    // 层序遍历
    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))
                break;
            if (node.left != null)
                queue.offer(node.left);
            if (node.right != null)
                queue.offer(node.right);
        }
    }

    public int height(E element) {
        return height(node(element));
//      return height2(node(element));
    }

    // 通过元素查找节点
    public Node<E> node(E element) {
        if (root == null)
            return null;
        Node<E> node = root;
        int cmp = 0;
        while (node != null) {
            cmp = compare(element, node.element);
            if (cmp == 0)
                return node;
            if (cmp > 0)
                node = node.right;
            else
                node = node.left;
        }
        return null;
    }

    private int height;// 树的高度
    private int levelCount = 1;// 一层的元素数量
    // 计算二叉树的高度 使用层序遍历的方式

    private int height(Node<E> node) {
        if (node == null)
            return 0;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            Node<E> newNode = queue.poll();
            levelCount--;
            if (newNode.left != null)
                queue.offer(newNode.left);
            if (newNode.right != null)
                queue.offer(newNode.right);
            if (levelCount == 0) {
                levelCount = queue.size();
                height++;
            }
        }
        return height;
    }

    private int height2(Node<E> node) {
        if (node == null)
            return 0;
        return 1 + Math.max(height2(node.left), height2(node.right));
    }

    public boolean isCompleteTree() {
        if (root == null)
            return false;
        boolean leaf = false;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (leaf && !node.isLeaf())
                return false;

            // 如果node.left!=null就入队
            if (node.left != null)
                queue.offer(node.left);
            else { //
                if (node.right != null)
                    return false;
//              和下面叶子节点判断重复，可去掉
//              else if (node.right == null)
//                  leaf = true;
            }

            if (node.right != null)
                queue.offer(node.right);
            else {
//              if(node.left!=null) {
//                  leaf = true;
//              }else if(node.left==null) { //重复
//                  leaf = true;
//              }
                // 上面判断重复,简化为
                leaf = true;
            }
        }

        return true;
    }

    public E precursor(E element) {
        Node<E> node = precursor(node(element));
        return node == null ? null : node.element;
    }

    // 获取指定节点的前驱结点
    private Node<E> precursor(Node<E> node) {
        if (node == null)
            return node;
        Node<E> leftNode = node.left;
        // node.left.right.right....
        if (leftNode != null) {
            while (leftNode.right != null) {
                leftNode = leftNode.right;
            }
            return leftNode;
        }

        // node.parent.parent....
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }

        // 走到这里条件 node.parent===null || node == node.parent.right
        // 这两种情况下都会返回node.parent
        return node.parent;
    }

    public E successor(E element) {
        Node<E> node = successor(node(element));
        return node == null ? null : node.element;
    }

    // 后继节点
    private Node<E> successor(Node<E> node) {
        if (node == null)
            return null;
        Node<E> rightNode = node.right;
        // node.right.left.left....
        if (rightNode != null) {
            while (rightNode.left != null) {
                rightNode = rightNode.left;
            }
            return rightNode;
        }

        // node.parent.parent...
        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }
        return node.parent;
    }

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

    // 删除元素
    public void remove(E element) {
        remove(node(element));
    }

    private void remove(Node<E> node) {
        if (node == null)
            return;
        // 删除度为2的节点
        if (node.hasTwoChildren()) {
            // 找到前驱节点
            Node<E> precurNode = precursor(node);
            // 用前驱节点的值覆盖要删除节点的值
            node.element = precurNode.element;
            // 删除前驱节点
            node = precurNode;
        }

        // 删除的node节点的度为1或0
        Node<E> child = node.left != null ? node.left : node.right;
        if (child != null) { // 度为1的节点
            // 使用子节点替代要删除节点的位置
            child.parent = node.parent;
            if (node.parent == null)
                root = child;
            else if (node == node.parent.left)
                node.parent.left = child;
            else if (node == node.parent.right)
                node.parent.right = child;
        } // 删除叶子节点
        else if (node.parent == null)
            root = null;
        else if (node == node.parent.left)
            node.parent.left = null;
        else if (node == node.parent.right)
            node.parent.right = null;
        size--;
    }

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

    private 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 String toString() {
        StringBuilder sb = new StringBuilder();
        toString(sb, root, "");
        return sb.toString();
    }

    // 使用前序遍历方式打印二叉树
    private void toString(StringBuilder sb, Node<E> node, String prefix) {
        if (node == null)
            return;
        sb.append(prefix).append("【").append(node.element).append("】").append("\n");
        toString(sb, node.left, prefix + "〖L〗");
        toString(sb, node.right, prefix + "〖R〗");
    }

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        // TODO Auto-generated method stub
        return ((Node<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        // TODO Auto-generated method stub
        return ((Node<E>) node).right;
    }

    @Override
    public Object string(Object node) {
        // TODO Auto-generated method stub
        Node<E> newNode = (Node<E>) node;
        return newNode.element + "_p_" + (newNode.parent == null ? "null" : newNode.parent.element);
    }

}