五个主要搜索的算法08: 二进制排序树（BSTree）

作者: nnngu

GitHub:

博客公园:

简单的书:

知道:

上一篇文章总结了索引搜索. 本文将总结二进制排序树，也称为二进制搜索树或BSTree.

构造二进制排序树的目的不是排序，而是提高搜索，插入和删除的效率.

什么是二进制排序树？二进制排序树具有以下特征.

（1）如果根节点具有左子树，则左子树中的所有节点都小于根节点.

（2）如果根节点具有右子树，则右子树中的所有节点都大于根节点.

（3）根节点的左右子树也是二进制排序树.

下面是二进制排序树的说明，通过它您可以加深对二进制排序树的理解.

以下是二进制排序树的常见操作和思想.

思考: 例如，我们要将数字20插入此二进制排序树中. 然后二叉排序树查找 算法，步骤如下:

（1）首先将20与根节点进行比较，发现它小于根节点，因此继续与根节点的左子树30比较.

（2）发现20也小于30，因此继续与30的左子树进行比较.

（3）发现20大于10，因此我在20的右子树中插入了20.

此时的二进制排序树如下:

例如，如果我们要找到节点10，则想法如下:

（1）仍然相同. 首先将10与根节点50进行比较，发现它小于根节点二叉排序树查找 算法，因此继续与根节点的左子树30比较.

（2）发现10小于左子树30，因此继续与30的左子树10进行比较.

（3）如果两个值相等，则搜索成功，并返回10的位置.

删除节点的情况比较复杂，主要分为以下三种情况:

（1）删除叶节点（即，没有子节点）. 例如，删除20不会破坏最简单的原始树结构. 如图所示.

（2）单个子节点被删除. 例如，将90删除后，需要将其子节点与其父节点连接起来. 这种情况比第一种更为复杂.

（3）删除了具有左右子节点的节点. 例如，根节点50

这里的问题是删除后谁将成为根节点？二叉树的中阶遍历是右节点左子树的最左子级.

考虑之后，让我们开始编写代码以实现这些功能.

BSTreeNode.java

public class BSTreeNode {
    public int data;
    public BSTreeNode left;
    public BSTreeNode right;
    public BSTreeNode(int data) {
        this.data = data;
    }
}

BSTreeOperate.java

/**
 * 二叉排序树的常见操作
 */
public class BSTreeOperate {
    // 树的根节点
    public BSTreeNode root;
    // 记录树的节点个数
    public int size;
    /**
     * 创建二叉排序树
     *
     * @param list
     * @return
     */
    public BSTreeNode create(int[] list) {
        for (int i = 0; i < list.length; i++) {
            insert(list[i]);
        }
        return root;
    }
    /**
     * 插入一个值为data的节点
     *
     * @param data
     */
    public void insert(int data) {
        insert(new BSTreeNode(data));
    }
    /**
     * 插入一个节点
     *
     * @param bsTreeNode
     */
    public void insert(BSTreeNode bsTreeNode) {
        if (root == null) {
            root = bsTreeNode;
            size++;
            return;
        }
        BSTreeNode current = root;
        while (true) {
            if (bsTreeNode.data <= current.data) {
                // 如果插入节点的值小于当前节点的值，说明应该插入到当前节点左子树，而此时如果左子树为空，就直接设置当前节点的左子树为插入节点。
                if (current.left == null) {
                    current.left = bsTreeNode;
                    size++;
                    return;
                }
                current = current.left;
            } else {
                // 如果插入节点的值大于当前节点的值，说明应该插入到当前节点右子树，而此时如果右子树为空，就直接设置当前节点的右子树为插入节点。
                if (current.right == null) {
                    current.right = bsTreeNode;
                    size++;
                    return;
                }
                current = current.right;
            }
        }
    }
    /**
     * 中序遍历
     *
     * @param bsTreeNode
     */
    public void LDR(BSTreeNode bsTreeNode) {
        if (bsTreeNode != null) {
            // 遍历左子树
            LDR(bsTreeNode.left);
            // 输出节点数据
            System.out.print(bsTreeNode.data + " ");
            // 遍历右子树
            LDR(bsTreeNode.right);
        }
    }
    /**
     * 查找节点
     */
    public boolean search(BSTreeNode bsTreeNode, int key) {
        // 遍历完没有找到，查找失败
        if (bsTreeNode == null) {
            return false;
        }
        // 要查找的元素为当前节点，查找成功
        if (key == bsTreeNode.data) {
            return true;
        }
        // 继续去当前节点的左子树中查找，否则去当前节点的右子树中查找
        if (key < bsTreeNode.data) {
            return search(bsTreeNode.left, key);
        } else {
            return search(bsTreeNode.right, key);
        }
    }
}

BSTreeOperateTest.java

public class BSTreeOperateTest {
    public static void main(String[] args) {
        BSTreeOperate bsTreeOperate = new BSTreeOperate();
        int[] list = new int[]{50, 30, 70, 10, 40, 90, 80};
        System.out.println("*********创建二叉排序树*********");
        BSTreeNode bsTreeNode = bsTreeOperate.create(list);
        System.out.println("中序遍历原始的数据：");
        bsTreeOperate.LDR(bsTreeNode);
        System.out.println("");
        System.out.println("");
        System.out.println("********查找节点*******");
        System.out.println("元素20是否在树中：" + bsTreeOperate.search(bsTreeNode, 20));
        System.out.println("");
        System.out.println("********插入节点*******");
        System.out.println("将元素20插入到树中");
        bsTreeOperate.insert(20);
        System.out.println("中序遍历：");
        bsTreeOperate.LDR(bsTreeNode);
        System.out.println("");
        System.out.println("");
        System.out.println("********查找节点*******");
        System.out.println("元素20是否在树中：" + bsTreeOperate.search(bsTreeNode, 20));
        System.out.println("");
    }
}

运行结果:

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-182891-1.html