DS05.2:二叉搜索树

定义

二叉搜索树（Binary Search Tree），即对任意节点，其值大于其左子树中任意一个节点的值，而小于其右子树中任意一个节点的值。

是一种特殊的二叉树，因此继承了二叉树的所有特性

二叉搜索树的相关分析见：https://www.jianshu.com/p/ff4b93b088eb

操作实现

插入元素

题目来源：https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/

利用二叉树的递归特性可以很简单的构造出相应的递归函数。

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null) {
            root = new TreeNode(val);
            return root;
        }
        if(val<root.val) {
            root.left = insertIntoBST(root.left, val);
        }
        else {
            root.right = insertIntoBST(root.right, val);
        }
        return root;
    }
}

查找某元素是否存在

使用递归进行判断，如果待判断元素比当前节点值小，则向左递归，否则向右递归。

private boolean contains(Node node, E e) {
    if(node==null) return false;
    if(e.compareTo(node.e) == 0) return true;
    else if(e.compareTo(node.e) < 0) return contains(node.left, e);
    else return contains(node.right, e);
}

最大最小值

这个思路很简单，使用递归与迭代都可以，就是向左或右一直搜索即可。

// 寻找二分搜索树最小值
public E minimum() {
    if(size == 0) {
        throw new IllegalArgumentException("BST is empty");
    }
    return minimun(root).e;
}

private Node minimun(Node node) {
    if(node.left == null) return node;
    return minimun(node.left);
}

其中若要删除最小值或最大值，就可以对应以下“删除元素”中的第一或者第二种情况，十分方便。

删除元素

图片来源：https://www.jianshu.com/p/ff4b93b088eb

对二叉搜索树进行删除主要要考虑以下三种情况。

1、要删除的是叶子节点

这种情况只需要直接将其设置为空即可

2、要删除的节点有左节点但没有右节点，或有右节点但没有左节点

这种情况下只需要将其右（左）节点放置在要删除的节点的位置上即可。

3、要删除的节点既有左节点又有右节点

这种情况下，只需要找到待删节点的右子树中最小的节点（或左子树最大的节点），将其删除并将其值赋给待删节点即可（直接操作相应的指针也行）

删除二叉搜索树的代码：来源于https://leetcode-cn.com/problems/delete-node-in-a-bst/submissions/

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null) return root;
        if(key > root.val) {
            root.right = deleteNode(root.right, key);
        }
        else if(key < root.val) {
            root.left = deleteNode(root.left, key);
        }
        else {
            if(root.left==null || root.right==null) {
                root = (root.left==null) ? root.right : root.left;
            }
            else {
                TreeNode temp = root.right;
                while(temp.left != null) {
                    temp = root.left;
                }
                root.val = temp.val;
                root.right = deleteNode(root.right, temp.val);
            }
        }
        return root;
    }
}

其中可见：

若是上述第一种和第二种情况，则直接对二叉树节点进行赋值操作即可。

若是第三种情况，则将找到的节点的val值赋给对应“根”节点，之后对其子树进行递归，删除对应的节点即可（此时需要删除的节点必满足一二两种情况）

Donate