关于动画:看动画学算法之二叉搜索树BST

5次阅读

共计 2585 个字符，预计需要花费 7 分钟才能阅读完成。

树是相似于链表的数据结构，和链表的线性构造不同的是，树是具备层次结构的非线性的数据结构。

树是由很多个节点组成的，每个节点能够指向很多个节点。

如果一个树中的每个节点都只有 0，1，2 个子节点的话，这颗树就被称为二叉树，如果咱们对二叉树进行肯定的排序。

比方，对于二叉树中的每个节点，如果左子树节点的元素都小于根节点，而右子树的节点的元素都大于根节点，那么这样的树被叫做二叉搜寻树（Binary Search Tree）简称 BST。

明天咱们来探讨一下 BST 的性质和对 BST 的基本操作。

刚刚咱们曾经讲过 BST 的基本特征了，当初咱们再来总结一下：

BST 中任意节点的左子树肯定要比该节点的值要小
BST 中任意节点的右子树肯定要比该节点的值要大
BST 中任意节点的左右子树肯定要是一个 BST。

看一张图直观的感受一下 BST：

怎么用代码来构建一个 BST 呢？

首先，BST 是由一个一个的节点 Node 组成的，Node 节点除了保留节点的数据之外，还须要指向左右两个子节点，这样咱们的 BST 齐全能够由 Node 连贯而成。

另外咱们还须要一个 root 节点来示意 BST 的根节点。

相应的代码如下：

public class BinarySearchTree {

    // 根节点
    Node root;

    class Node {
        int data;
        Node left;
        Node right;

        public Node(int data) {
            this.data = data;
            left = right = null;
        }
    }
}

先看下 BST 的搜寻，如果是下面的 BST，咱们想搜寻 32 这个节点应该是什么样的步骤呢？

先上图：

搜寻的根本步骤是：

从根节点 41 登程，比拟根节点和搜寻值的大小
如果搜寻值小于节点值，那么递归搜寻左侧树
如果搜寻值大于节点值，那么递归搜寻右侧树
如果节点匹配，则间接返回即可。

相应的 java 代码如下：

// 搜寻办法，默认从根节点搜寻
    public Node search(int data){return search(root,data);
    }

    // 递归搜寻节点
    private Node search(Node node, int data)
    {
        // 如果节点匹配，则返回节点
        if (node==null || node.data==data)
            return node;

        // 节点数据大于要搜寻的数据，则持续搜寻右边节点
        if (node.data > data)
            return search(node.left, data);

        // 如果节点数据小于要搜素的数据，则持续搜寻左边节点
        return search(node.right, data);
    }

搜寻讲完了，咱们再讲 BST 的插入。

先看一个动画：

上的例子中，咱们向 BST 中插入两个节点 30 和 55。

插入的逻辑是这样的：

从根节点登程，比拟节点数据和要插入的数据
如果要插入的数据小于节点数据，则递归左子树插入
如果要插入的数据大于节点数据，则递归右子树插入
如果根节点为空，则插入以后数据作为根节点

相应的 java 代码如下：

// 插入新节点，从根节点开始插入
    public void insert(int data) {root = insert(root, data);
    }

    // 递归插入新节点
    private Node insert(Node node, int data) {

        // 如果节点为空，则创立新的节点
        if (node == null) {node = new Node(data);
            return node;
        }

        // 节点不为空，则进行比拟，从而递归进行左侧插入或者右侧插入
        if (data < node.data)
            node.left = insert(node.left, data);
        else if (data > node.data)
            node.right = insert(node.right, data);

        // 返回插入后的节点
        return node;
    }

BST 的删除要比插入简单一点，因为插入总是插入到叶子节点，而删除可能删除的是非叶子节点。

咱们先看一个删除叶子节点的例子：

下面的例子中，咱们删除了 30 和 55 这两个节点。

能够看到，删除叶子节点是绝对简略的，找到之后删除即可。

咱们再来看一个比较复杂的例子，比方咱们要删除 65 这个节点：

能够看到须要找到 65 这个节点的右子树中最小的那个，替换掉 65 这个节点即可（当然也能够找到左子树中最大的那个）。

所以删除逻辑是这样的：

从根节点开始，比拟要删除节点和根节点的大小
如果要删除节点比根节点小，则递归删除左子树
如果要删除节点比根节点大，则递归删除右子树
如果节点匹配，又有两种状况
如果是单边节点，间接返回节点的另外一边
如果是双边节点，则先找出左边最小的值，作为根节点，而后将删除最小值过后的左边的节点，作为根节点的右节点

看下代码的实现：

 // 删除新节点，从根节点开始删除
    void delete(int data)
    {root = delete(root, data);
    }

    // 递归删除节点
    Node delete(Node node, int data)
    {
        // 如果节点为空，间接返回
        if (node == null)  return node;

        // 遍历左右两边的节点
        if (data < node.data)
            node.left = delete(node.left, data);
        else if (data > root.data)
            node.right = delete(node.right, data);

        // 如果节点匹配
        else
        {
            // 如果是单边节点，间接返回其上面的节点
            if (node.left == null)
                return node.right;
            else if (node.right == null)
                return node.left;

            // 如果是双边节点，则先找出左边最小的值，作为根节点，而后将删除最小值过后的左边的节点，作为根节点的右节点
            node.data = minValue(node.right);

            // 从左边删除最小的节点
            node.right = delete(node.right, node.data);
        }
        return node;
    }

这里咱们应用递归来实现的删除双边节点，大家能够考虑一下有没有其余的形式来删除呢？

本文的代码地址：

learn-algorithm