小码哥《恋上数据结构与算法》笔记(八):二叉搜索树

3,928 阅读9分钟

我的Github地址

小码哥《恋上数据结构与算法》笔记

极客时间《iOS开发高手课》笔记

iOS大厂面试高频算法题总结

iOS面试资料汇总

数据结构和算法动态可视化

小码哥二叉树可视化网页

一、二叉搜索树(Binary Search Tree)

  • 任意一个节点的值都大于左子树所有节点的值。
  • 任意一个节点的值都小于右子树所有节点的值。
  • 它的左右子树也是一颗二叉搜索树。
  • 二叉搜索树存储的元素必须具备可比较性
    • 比如intdouble等。
    • 如果是自定义类型,需要指定比较方式。
    • 不允许为null

二、二叉搜索树接口设计

public class BinarySearchTree<E>{
    private int size; // 元素的个数
    private Node<E> root; // 根节点
    private Comparator<E> comparator; // 比较器

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

三、二叉搜索树的实现

1、构造函数

  • 如果二叉树存储的是自定义类型,需要传入一个比较器,负责两个节点的大小。
  • 添加元素操作时,会调用compare私有函数。
public class BinarySearchTree<E> {
    // 比较器
    private Comparator<E> comparator;
    // 便利构造器
    public BinarySearchTree() {
        this(null);
    }
    // 构造函数
    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }
    
    /**
    * @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);
    }
}

2、节点

  • 二叉树的元素是存放在节点中的,所以需要创建私有节点类。
  • 节点还需记录自己的左节点右节点父节点
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;
    }
}

3、添加元素

  • 首先找到父节点parent,然后创建新节点node,最后比较parentnode的大小。
  • 如果node小于parent,将parent.left赋值给parent
  • 如果node大于parent,将parent.right赋值给parent
  • 循环比较操作,直到parent.leftparent.right为空,将node赋值给parent.leftparent.right即可。
  • 添加元素前,首先需要检查节点的值是否为
private void elementNotNullCheck(E element) {
    if (element == null) {
    throw new IllegalArgumentException("element must not be null");
    }
}
  • 另外,还需要特殊处理添加元素到首节点
public void add(E element) {
    // 判断节点的值是否为空。
    elementNotNullCheck(element);
		
    // 添加第一个节点
    if (root == null) {
        root = new Node<>(element, null);
        size++;
        return;
    }
    // 添加的不是第一个节点
    Node<E> parent = root;
    Node<E> node = root;
    // 比较结果
    int cmp = 0;
    while (node != null) {
        // 在之前定义的比较函数
        cmp = compare(element, node.element);
        //保存node的父节点
        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++;
}

4、删除元素

  • tips:删除元素会使用前驱后继的知识,可以先阅读:
    • 五、二叉搜索树(Binary Search Tree)的前驱和后继
  • 删除节点分为删除叶子节点删除度为1的节点删除度为2的节点
  • 删除叶子节点,直接删除即可。
    • 如果node == node.parent.left
      • node.parent.left = null
    • 如果node == node.parent.right
      • node.parent.right = null
    • 如果node.parent == null
      • root = null

  • 删除度为1的节点,用子节点替代原节点的位置。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

  • 删除度为2的节点,先用前驱或后继节点的值覆盖原节点的值,然后删除相应的前驱或者后继节点。(如果这个节点的度为2,那么它的前驱,后继节点的度只能是1和0)
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;
        }
    }
}

四、二叉搜索树的遍历

  • 根据节点访问顺序的不同,二叉树的常见遍历方法有4种。
  • 所谓前中后序遍历,指的是根节点遍历顺序。

1、前序遍历

  • 访问顺序: 根节点 -> 前序遍历左子树 -> 前序遍历右子树
// 递归实现前序遍历
private void preorderTraversal(Node<E> node) {
    // 退出条件
    if (node == null) return;
    // 打印节点值	
    System.out.println(node.element);
    // 前序遍历左子树
    reorderTraversal(node.left);
    // 前序遍历右子树
    preorderTraversal(node.right);
}

2、中序遍历

  • 当需要按升序降序获取节点时,使用中序遍历
  • 访问顺序:中序遍历左子树 -> 根节点 -> 中序遍历右子树
  • 遍历结果:1、2、3、4、5、7、8、9、10、11、12
  • 如果是一颗二叉搜索树,遍历的结果按从小到大排序。
  • 另一种访问顺序:中序遍右左子树 -> 根节点 -> 中序遍历左子树
  • 遍历结果:12、11、10、9、8、7、5、4、3、2、1
  • 二叉搜索树的中序遍历结果是升序降序的。
// 递归实现中序遍历
private void inorderTraversal(Node<E> node) {
    // 退出条件
    if (node == null) return;
    // 中序遍历左子树	
    inorderTraversal(node.left);
    // 打印节点值
    System.out.println(node.element);
    // 中序遍历右子树
    inorderTraversal(node.right);
}

3、后序遍历

  • 当需要先子后父操作时,可以使用后序遍历
  • 访问顺序:后序遍历左子树 -> 后序遍历右子树 -> 根节点
// 递归实现后序遍历
private void postorderTraversal(Node<E> node) {
    // 退出条件
    if (node == null) return;
    // 后序遍历左子树
    postorderTraversal(node.left);
    // 后序遍历右子树
    postorderTraversal(node.right);
    // 打印节点值
    System.out.println(node.element);
}

4、层序遍历

  • 需要计算二叉树高度判断是否为完全二叉树时,可使用层序遍历

  • 访问顺序:从上到下从左到右依次访问节点。

  • 遍历思路:

    1. 使用队列存储节点。
    2. 根节点入队列。
    3. 将队列头节点A出队列,进行访问。
    4. 将节点A的左子节点入队列。
    5. 将节点A的右子节点入队列。
    6. 循环执行2-4步骤。
public void levelOrderTranversal() {
    // 如果根节点为空,直接返回
    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);
        }
    }
}

五、二叉搜索的前驱和后继

1、前驱节点(predecessor)

  • 中序遍历时的前一个节点。
  • 如果是二叉搜索树,前驱节点就是前一个比它小的节点。
  • 寻找前驱节点分三种情况:
  1. 左子树不为空
    • 举例:6,13,8
    • predecessor = node.left.right.right.right...
    • 终结条件:right = null
  2. 左子树为空,父节点不为空
    • 举例:7,11,9,1
    • predecessor = node.parent.parent.parent...
    • 终结条件:nodeparent右子树中。
  3. 左子树为空且父节点为空
    • 那就没有前驱节点
    • 举例:没有左子树的根节点。
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;
}

2、后继节点(successor)

  • 中序遍历时的后一个节点。
  • 如果是二叉搜索树,后继节点就是前一个比它大的节点。
  • 寻找后继节点分三种情况:
  1. 右子树不为空
    • 举例:1,4,4
    • successor = node.right.left.left.left...
    • 终结条件:left = null
  2. 右子树为空,父节点不为空
    • 举例:7,6,3,11
    • successor = node.parent.parent.parent...
    • 终结条件:nodeparent左子树中。
  3. 右子树为空且父节点为空
    • 那就没有前驱节点
    • 举例:没有右子树的根节点。
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;
}

六、leetcode算法题

1、二叉树的最大深度

  • 树的高度 = 子节点高度 + 1
  • 子节点高度 = Max(左子树,右子树)
// 递归实现
private int height(Node<E> node) {
    if (node == null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}
  • 也可以通过层序遍历求得最大深度:
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();
            //即将访问下一层,树的高度+1
            height++;
        }
    }
    return height;
}

2、二叉树的完全性检验

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 (left != null && right != null) {
	        queue.offer(node.left);
	        queue.offer(node.right);
	    } else if (node.left == null && node.right != null) {
	        return false;
        } else { // 后面遍历的节点都必须是叶子节点
            leaf = true;
            if (node.left != nill){
                queue.offer(node.left)
            }
        }
    }
    return true;
}

3、翻转二叉树

  • 只要能够遍历二叉树,就可以完成二叉树的翻转。

//前序遍历
public TreeNode invertTree(TreeNode root) {
    if (root == null) return root;
    //翻转
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
	   
    invertTree(root.left);
    invertTree(root.right);
    return root;
}
	
//后序遍历
public TreeNode invertTree(TreeNode root) {
    if (root == null) return root;
	   
    invertTree(root.left);
    invertTree(root.right);
    //翻转
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
      
    return root;
}
	
//中序遍历
public TreeNode invertTree(TreeNode root) {
    if (root == null) return root;
	   
    invertTree(root.left);
    //翻转
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
    // 这里放入的left其实是之前的right
    invertTree(root.left);
      
    return root;
}

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

4、根据遍历结果重构二叉树

从中序与后序遍历序列构造二叉树

从前序与中序遍历序列构造二叉树

根据前序和后序遍历构造二叉树

  • 以下结果可以保证重构出唯一的一颗二叉树
    • 前序遍历 + 中序遍历
    • 后序遍历 + 中序遍历
  • 如果是前序遍历 + 后序遍历
    • 如果它是一颗真二叉树,结果是唯一的。
    • 否则结果不唯一。

5、删除二叉搜索树中的节点

6、二叉搜索树中的搜索

7、二叉搜索树中的插入操作

8、验证二叉搜索树

9、二叉搜索树的最小绝对差

10、二叉搜索树结点最小距离

11、将有序数组转换为二叉搜索树

12、二叉搜索树的范围和

13、二叉搜索树的最近公共祖先

14、二叉搜索树中第K小的元素

15、二叉搜索树迭代器

16、恢复二叉搜索树

六、二叉搜索树的复杂度

  • 如果是按照7,4,9,2,5,8,11的顺序添加节点。
    • 搜索元素复杂度:O(h) == O(logn)
  • 如果是从小到大添加节点。
    • 搜索元素复杂度:O(h) == O(n)
  • 总结:
    • 当n比较大时,两者的性能差异比较大。
    • 比如n = 1000000时,二叉搜索树的最低高度是20,即最多搜索20次,而退化成链表的二叉搜索树,最多搜索1000000次。