数据结构与算法（第一季）：二叉搜索树

一、二叉搜索树

• 二叉搜索树是二叉树的一种, 是应用非常广泛的一种二叉树, 英文简称为BST
  • 又被称为: 二叉查找树、二叉排序树
  • 任意一个节点的值都大于其左子树所有节点的值
  • 任意一个节点的值都小于其右子树所有节点的值
  • 它的左右子树也是一颗二叉搜索树

image

<figcaption></figcaption>

• 二叉树可以大大提高搜索数据的效率
• 二叉搜索树存储的元素必须具备可比较性
  • 比如int、double等
  • 如果是自定义类型, 需要指定比较方式
  • 不允许为null

二、二叉搜索树的接口设计

// 元素的数量
int size();
// 是否为空
boolean isEmpty();
// 清空所有元素
void clear();
// 添加元素
void add(E element);
// 删除元素
void remove(E element);
// 是否包含某元素
boolean contains(E element);
复制代码

注意: 二叉树的元素没有索引的概念

三、二叉搜索树的实现

1、类的设计

• 创建类BinarySearchTree, 并添加几个属性
  • size属性, 用来计算已保存元素个数
  • root属性, 用来保存根节点
• 创建私有类Node, 用来创建节点, 并添加几个属性
  • element: 用来保存元素
  • left: 保存左子节点
  • right: 保存右子节点
  • parent: 保存父节点

public class BinarySearchTree<E> {
    private int size;
    private Node<E> root;

    private static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        @SuppressWarnings("unused")
        Node<E> parent;
        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }
    }
}
复制代码

2、添加节点

• 首先, 要保证添加的节点不能为空, 所以需要对null进行处理

// 当element为null时, 抛出异常
private void elementNotNullElement(E element) {
    if (element == null) {
        throw new IllegalArgumentException("element must not be  null");
    }
}
复制代码

• 此时的add方法如下

public void add(E element) {
    // 当element为null, 抛出异常
    elementNotNullElement(element);
}
复制代码

• 当添加第一个元素, 即添加根节点时, 直接添加到root属性即可

public void add(E element) {
    // 当element为null, 抛出异常
    elementNotNullElement(element);
    if (root == null) {
        root = new Node<>(element, null);
        size++;
    }
}
复制代码

• 当添加的节点不是根节点时, 需要找到新节点的父节点, 然后再根据元素的大小判断出添加到父节点的left或者right
• 当新元素 > 节点元素时, 向右查找子节点, 当新元素 < 节点元素时, 向左查找子节点, 伪代码如下

if (新元素 > 节点元素值) {
    找到节点的右子节点
}else if (新元素 < 节点元素值) {
    找到节点的左子节点
}else {
    新元素覆盖旧元素
}
复制代码

• 首先创建一个方法, 用来返回两个元素的大小, compare方法中的实现, 根据个人的需要而定

/**
 * @return 0: e1等于e2, 整数: e1大于e2, 负数: e1小于e2
 */
private int compare(E e1, E e2) {
    // 此处判断e1和e2的大小
    return 0;
}
复制代码

• 实现代码如下, 可以找到root节点的下一个节点

Node<E> node = root;
int cmp = compare(element, node.element);
if (cmp > 0) {
    node = node.right;
}else if (cmp < 0) {
    node = node.left;
}else {
    node.element = element;
    return;
}
复制代码

• 通过循环, 就可以找到最终添加新节点的父节点, 我们使用parent记录最终的父节点, cmp记录最后一次比较的结果

public void add(E element) {
    // 当element为null, 抛出异常
    elementNotNullElement(element);
    if (root == null) {
        root = new Node<>(element, null);
        size++;
    }

    // 记录最终添加新节点的父节点
    Node<E> parent = root;
    // 需要查询的节点
    Node<E> node = root;
    // 记录最后一次比较结果
    int cmp = 0;
    while (node != null) {
        // 0: e1等于e2, 正数: e1大于e2, 负数: e1小于e2
        cmp = compare(element, node.element);
        parent = node;
        // cmp大于0, 说明element的值大于当前节点的值, 所以找到当前节点的右子节点
        if (cmp > 0) {
            node = node.right;
        }else if (cmp < 0) {
            // cmp大于0, 说明element的值小于当前节点的值, 所以找到当前节点的左子节点
            node = node.left;
        }else {  // 相等
            node.element = element;
            return;
        }
    }
    // cmp大于0, 说明element的值大于父节点的值, 需要放到右子节点
    if (cmp > 0) {
        parent.right = new Node<>(element, parent);
    }else {
        // cmp小于0, 说明element的值小于父节点的值, 需要放到左子节点
        parent.left = new Node<>(element, parent);
    }
    size++;
}
复制代码

3、节点值的对比

• 上面定义了方法compare, 用于新添加元素和某个节点元素值的比较
• 因为二叉搜索树的值必须要有对比性, 所以compare的方法实现如下

/**
 * @return 0: e1等于e2, 整数: e1大于e2, 负数: e1小于e2
 */
private int compare(E e1, E e2) {
    return ((Comparable<E>)e1).compareTo(e2);
}
复制代码

• Comparable中定义了对比两个对象的方法compareTo, 可以由开发者实现如何对比两个对象

---

• 上面这种方法, 属于定义在二叉搜索树BinarySearchTree中默认的对比方式
• 但是在使用的时候, 可能会出现要自定义对比方式的情况
• 这时可以使用Comparator来实现外部定义对比方式, Comparator是专门用于实现两个对象对比的协议
• 定义一个属性Comparator<E> comparator, 并在BinarySearchTree初始化方法中传入外部创建的Comparator对象

public class BinarySearchTree<E> {
    private int size;
    private Node<E> root;
    private Comparator<E> comparator;

    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }
}
复制代码

• 此时compare方法的内部实现如下

/**
 * @return 0: e1等于e2, 整数: e1大于e2, 负数: e1小于e2
 */
private int compare(E e1, E e2) {
    if (comparator != null) {
        return comparator.compare(e1, e2);
    }
    return ((Comparable<E>)e1).compareTo(e2);
}
复制代码

• 此时在Main函数中可以如下使用二叉搜索树BinarySearchTree, 传入一个对象, 该对象实现了两个元素的对比

public class Main {
    public static void main(String[] args) {
        BinarySearchTree<Integer> tree = new BinarySearchTree<>(new Comparator<Integer>() {
            // 两个值的对比结果
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
    }
}
复制代码

四、二叉树的遍历

• 二叉树常见的遍历有四种
  • 前序遍历(Preorder Traversal)
  • 中序遍历(Inorder Traversal)
  • 后序遍历(Postorder Traversal)
  • 层序遍历(Level Order Traversal)

1、代码准备

• 在Main函数中使用二叉搜索树保存一串元素, 用来遍历使用

public class Main {
    public static void main(String[] args) {
        int[] data = new int[] {7, 4, 9, 2, 5, 8, 11, 1, 3, 10, 12};

        BinarySearchTree<Integer> tree = new BinarySearchTree<>();

        for (int i = 0; i < data.length; i++) {
            tree.add(data[I]);
        }
    }
}
复制代码

2、前序遍历

• 遍历顺序: 根节点、前序遍历左子树、前序遍历右子树

image

<figcaption></figcaption>

• 遍历顺序: 7、4、2、1、3、5、9、8、11、10、12

• 代码如下

public void preorder() {
    preorder(root);
}
// 通过递归遍历所有的元素
public void preorder(Node<E> node) {
    if (node == null) return;
    // 先查看根节点
    System.out.println(node.element);
    // 再遍历左子树
    preorder(node.left);
    // 最后遍历右子树
    preorder(node.right);
}
复制代码

3、中序遍历

• 访问书序: 中序遍历左子树、根节点、中序遍历右子树

image

<figcaption></figcaption>

遍历顺序: 1、2、3、4、5、8、9、10、11、12

• 代码如下

public void inorder() {
    inorder(root);
}

public void inorder(Node<E> node) {
    if (node == null) return;
    // 先中序遍历左子树
    inorder(node.left);
    // 再访问根节点
    System.out.println(node.element);
    // 最后遍历右子树
    inorder(node.right);
}
复制代码

4、后序遍历

• 访问顺序: 后序遍历左子树, 后序遍历右子树

image

<figcaption></figcaption>

• 遍历顺序: 1、3、2、5、4、8、10、12、11、9、7

• 代码如下

public void postorder () {
    postorder(root);
}
public void postorder(Node<E> node) {
    if (node == null) return;
    // 先遍历左子树
    postorder(node.left);
    // 再遍历右子树
    postorder(node.right);
    // 最后访问根节点
    System.out.println(node.element);
}
复制代码

5、层序遍历

• 访问顺序: 从上到下, 从左到右依次访问每一个节点

image

<figcaption></figcaption>

• 遍历顺序: 7、4、9、2、5、8、11、1、3、10、12

• 实现思路: 使用队列

  • 将根节点入队
  • 循环执行一下操作, 知道队列为空
    • 将对头节点A出队, 进行访问
    • 将A的左子点入队
    • 将A的有节点入队

• 代码如下

public void levelOrder() {
    if (root == null) return;
    Queue<Node<E>> queue = new LinkedList<>();
    // 根节点入队
    queue.offer(root);
    // 当queue为空时停止遍历
    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);
        }
    }
}
复制代码

五、外界获取遍历结果

• 上面的遍历只是在方法内部打印而已, 但是在实际开发中, 是需要使用者能够获取到遍历结果
• 所以需要对外抛出遍历的元素

1、定义接口, 用于抛出结果

• 定义接口, 用来向外界抛出遍历结果

public static interface Visitor<E> {
    void visit(E element);
}
复制代码

2、将Visitor作为遍历方法的参数

public static interface Visitor<E> {
    void visit(E element);
}
// 前序遍历
public void preorder(Visitor<E> visitor) {
    preorder(root, visitor);
}
// 通过递归遍历所有的元素
public void preorder(Node<E> node, Visitor<E> visitor) {
    if (node == null) return;
    // 先处理根节点
    visitor.visit(node.element);
    // 再遍历左子树
    preorder(node.left, visitor);
    // 最后遍历右子树
    preorder(node.right, visitor);
}

// 中序遍历
public void inorder(Visitor<E> visitor) {
    inorder(root, visitor);
}
public void inorder(Node<E> node, Visitor<E> visitor) {
    if (node == null) return;
    // 先中序遍历左子树
    inorder(node.left, visitor);
    // 再处理根节点
    visitor.visit(node.element);
    // 最后遍历右子树
    inorder(node.right, visitor);
}

// 后序遍历
public void postorder (Visitor<E> visitor) {
    postorder(root, visitor);
}
public void postorder(Node<E> node, Visitor<E> visitor) {
    if (node == null) return;
    // 先遍历左子树
    postorder(node.left, visitor);
    // 再遍历右子树
    postorder(node.right, visitor);
    // 最后处理根节点
    visitor.visit(node.element);
}

// 层序遍历 
public void levelOrder(Visitor<E> visitor) {
    if (root == null) return;
    Queue<Node<E>> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        Node<E> node = queue.poll();
        // 处理节点的元素
        visitor.visit(node.element);
        if (node.left != null) {
        queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}
复制代码

3、外界使用

public class Main {
    public static void main(String[] args) {
        int[] data = new int[] {7, 4, 9, 2, 5, 8, 11, 1, 3, 10, 12};

        BinarySearchTree<Integer> tree = new BinarySearchTree<>();

        for (int i = 0; i < data.length; i++) {
            tree.add(data[I]);
        }
        // 前序遍历
        tree.preorder(new Visitor<Integer>() {
            public void visit(Integer element) {
                System.out.println(element);
            }
        });
        // 中序遍历
        tree.inorder(new Visitor<Integer>() {
            public void visit(Integer element) {
                System.out.println(element);
            }
        });
        // 后序遍历
        tree.postorder(new Visitor<Integer>() {
            public void visit(Integer element) {
                System.out.println(element);
            }
        });
        // 层序遍历
        tree.levelOrder(new Visitor<Integer>() {
            public void visit(Integer element) {
                System.out.println(element);
            }
        });
    }
}
复制代码

六、树状打印二叉树

• 可以使用前序遍历、中序遍历、后序遍历来树状打印二叉树
• 以中序遍历为例

public String toString() {
    StringBuffer sb = new StringBuffer();
    stringBufferTree(sb, root, "");
    return sb.toString(); 
}

private void stringBufferTree(StringBuffer sb, Node<E> node, String prefix) {
    if (node == null) return;
    stringBufferTree(sb, node.left, prefix + "L-");
    sb.append(prefix).append(node.element).append("\n");
    stringBufferTree(sb, node.right, prefix +  "R-");
}
复制代码

• 执行代码

public class Main {
    public static void main(String[] args) {
        Integer data[] = new Integer[] {
            7, 4, 9, 2, 1, 3, 5, 9, 8, 11, 10, 12
        };
        BinarySearchTree<Integer> tree = new BinarySearchTree<>();
        for (int i = 0; i < data.length; i++) {
            tree.add(data[I]);
        }
        System.out.println(tree);
    }
}
复制代码

• 打印结果如下

L-L-L-1
L-L-2
L-L-R-3
L-4
L-R-5
7
R-L-8
R-9
R-R-L-10
R-R-11
R-R-R-12
复制代码

七、计算二叉树的高度

1、递归

• 二叉树高度 = 根节点高度 = MAX(左子节点高度, 右子节点高度) + 1
• 以此类推, 可以使用递归计算二叉树的高度

public int height() {
    return height(root);
}

public int height(Node<E> node) {
    if (node == null) return 0;
    // 左子节点或右子节点中高度最高的值 + 1
    return 1 + Math.max(height(node.left), height(node.right));
}
复制代码

2、迭代

• 可以使用层序循环遍历的方式, 计算树的高度
• 层序循环遍历, 使用了队列的方式
  • 首先将根节点入队
  • 根节点出队, 根节点的左右子节点入队, 既第二层的所有节点入队
  • 每一个节点出队, 都会将它的左右子节点入队, 以此类推
  • 当第二层所有节点出队后, 第三层所有节点都已经入队
  • 一开始就用变量elementCount记录每一层的节点个数, 初始值是1, 即根节点入队
  • 根节点出队, elementCount--, 第二层节点入队, 此时队列中保存所有第二层节点, 使用elementCount记录第二层节点数量
  • 第二层开始出队, 每出队一个节点, elementCount--, 当elementCount == 0时, 说明第二层节点全部出队, 此时第三层节点已经全部入队, 再用elementCount记录第三层所有节点个数
  • 以此类推, 当最后队列为空时, 经历过几次elementCount == 0, 就说明二叉树有几层

/**
 * 使用层序遍历的方式, 计算树的高度
 */
public int height() {
    Queue<Node<E>> queue = new LinkedList<>();
    queue.offer(root);
    // 当前队列中节点个数
    int elementCount = 1;
    // 树的高度
    int height = 0;
    while (!queue.isEmpty()) {
        // 取出节点
        Node<E> node = queue.poll();
        // 队列中节点个数-1
        elementCount--;
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
        // 当 elementCount = 0, 说明当前层的节点遍历编程
        if (elementCount == 0) {
            // 记录下一层节点个数
            elementCount = queue.size();
            // 高度+1
            height++;
        }
    }
    return height;
}
复制代码

八、判断一棵树是否为完全二叉树

image

<figcaption></figcaption>

• 使用队列进行层次循环, 进行判断
• 如果树为空, 返回false
• 如果树不为空，开始层序遍历二叉树(用队列)
  • 如果 node.left != null，将 node.left 入队
  • 如果 node.left == null && node.right != null，返回 false
  • 如果 node.right != null，将 node.right 入队
  • 如果 node.right == null
    • 那么后面遍历的节点应该都为叶子节点，才是完全二叉树
    • 否则返回 false
  • 遍历结束，返回 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();

        // 当leaf == true时, 后面的所有节点都必须是叶子节点, 否则返回false
        if (leaf && (node.left != null || node.right != null)) return false;

        if (node.left != null) {
            // node.left != null && node.right == null
            // node.left != null && node.right != null
            queue.offer(node.left);
        }else if (node.right != null) {
            // node.left == null && node.right != null
            return false;
        }

        if (node.right != null) {
            // node.left != null && node.right != null
            queue.offer(node.right);
        }else {
            // node.left == null && node.right == null
            // node.left != null && node.right == null
            leaf = true;
        }
    }
    return true;
}
复制代码

九、翻转二叉树

• 示例

输入:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出:

     4
   /   \
  7     2
 / \   / \
9   6 3   1
复制代码

• 二叉树TreeNode如下

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x; 
    }
}
复制代码

1、前序遍历实现翻转二叉树

public TreeNode invertTree(TreeNode root) {
    if (root == null) return root;

    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;

    invertTree(root.left);
    invertTree(root.right);
    return root;
}
复制代码

2、中序遍历实现翻转二叉树

public TreeNode invertTree(TreeNode root) {
    if (root == null) return root;

    invertTree(root.left);
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;

    invertTree(root.left);
    return root;
}
复制代码

3、后序遍历实现翻转二叉树

public TreeNode invertTree(TreeNode root) {
    if (root == null) return root;

    invertTree(root.left);
    invertTree(root.right);

    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;

    return root;
}
复制代码

4、层序遍历实现翻转二叉树

public TreeNode invertTree(TreeNode root) {
    if (root == null) return root;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();

        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;

        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
    return root;
}
复制代码

十、前驱节点和后继节点

1、前驱节点

• 前驱节点: 中序遍历时的前一个节点

image

<figcaption></figcaption>

private Node<E> predecessor(Node<E> node) {
    if (node == null) return node;

    if (node.left != null) {
        Node<E> p = node.left;
        // predecessor = node.left.right.right.right...
        while (p.right != null) {
            p = p.right;
        }
        // p.right == null
        return p;
    }

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

    // node.parent == null, 说明没有前驱节点
    // node == node.parent.right, 说明node的前驱节点是node.parent
    return node.parent;
}
复制代码

2、后继节点

• 后继节点: 中序遍历时的后一个节点

image

<figcaption></figcaption>

private Node<E> successor(Node<E> node) {
    if (node == null) return node;

    if (node.right != null) {
        Node<E> p = node.right;
        // predecessor = node.right.left.left.left...
        while (p.left != null) {
            p = p.left;
        }
        // p.left == null
        return p;
    }

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

    // node.parent == null, 说明没有后继节点
    // node == node.parent.left, 说明node的后继节点是node.parent
    return node.parent;
}
复制代码

十一、删除节点

1、删除节点-叶子节点

• 当删除叶子节点时, 这个节点有三种可能
  • 父节点的左子节点
  • 父节点的右子节点
  • 根节点
• 所以删除叶子节点时, 在判断是那种节点后, 直接删除即可

image

<figcaption></figcaption>

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

• 当需要删除的节点的度为1时, 将该节点的子节点代替需要删除的节点即可
• 也可要区分三种可能
  • 父节点的左子节点
  • 父节点的右子节点
  • 根节点

image

<figcaption></figcaption>

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

• 删除度为2的节点, 分为两步即可
  • 先用前驱或后继节点的值覆盖原节点的值
  • 然后删除相应的前驱或者后继节点
• 注意: 一个节点的度为2, 那么它的前驱或者后继节点的度只可能是1和0, 所以也就是删除度为1的节点或者删除叶子节点

image

<figcaption></figcaption>

4、删除节点-代码实现

• 查找element对应的节点, 代码如下

private Node<E> node(E element) {
    Node<E> node = root;
    while (node != null) {
        // 返回值等于0, e1 == e2, 返回正数, e1 > e2, 返回负数, e1 < e2
        int cmp = compare(element, node.element);
        // element == node.element, 返回node
        if (cmp == 0) return node;
        if (cmp > 0) {
            // element > node.element, node = node.right
            node = node.right;
        }else {
            // element > node.element, node = node.left
            node = node.left;
        }
    }
    return null;
}
复制代码

• 删除element对应的节点

public void remove(E element) {
    // 找到element对应的节点
    Node<E> node = node(element);

    // 数量-1
    size--;

    // 判断node的度, 如果为2, 将node的element赋值为后继节点的element, 并删除后继节点
    // 注意: node的后继节点的度必然是1或者0, 不会是2
    if (node.left != null && node.right != null) {
        // 找到后继节点
        Node<E> s = successor(node);
        // 将node的element赋值为后继节点的element
        node.element = s.element;
        // node指向后继节点, 这样只需要删除node即可
        node = s;
    }
    // 走到这里, node的度只能是1或者是0
    // 找到node的子节点, 左子节点或者右子节点, 或者null
    // 这个子节点会代替node的位置
    Node<E> replacement = node.left != null ? node.left : node.right;
    if (replacement != null) {  // node是度为1的节点
        // 更改replacement的父节点
        replacement.parent = node.parent;

        if (node.parent == null) {  // node是度为1的节点, 并且是根节点
            root = replacement;
        }else if (node == node.parent.left) {   // node是node.parent的左子节点
            node.parent.left = replacement;
        }else { // node == node.parent.right, node是node.parent的右子节点
            node.parent.right = replacement;
        }
    }else if (node.parent == null) {    // node是度为0的节点, 并且是根节点
        root = null;
    }else { // node是度为0的节点, 并且是叶子节点
        if (node == node.parent.left) {
            // node是node.parent的左子节点
            node.parent.left = null;
        }else {
            // node是node.parent的右子节点
            node.parent.right = null;
        }
    }
}
复制代码

十二、清空二叉树

• 清空二叉树, 只需要将root置为null即可

public void clear() {
    root = null;    // 清空root
}
复制代码

十三、查找元素是否存在

• 在删除节点中, 已经实现了根据element查找对应节点的方法
• 只要根据能否找到node, 即可判断元素是否存在

public boolean contains(E element) {
    return node(element) != null;
}
复制代码