数据结构-二叉搜索树的实现

数据结构-二叉搜索树的实现二叉搜索树(Binary Search Tree,BST),也称为二叉排序树或二叉查找树。 树中没有键值相等的结点。 可以看到,二叉搜索树的性质很鲜明,这也使得二叉树也有了实际意义。 对于二叉搜索树,除了常规的4种遍历之外,还有如下一些关键的操作值得我们去关注。 对于二叉树,我…

定义

二叉搜索树(Binary Search Tree,BST),也称为二叉排序树或二叉查找树。

相较于普通的二叉树,非空的二叉搜索树有如下性质:

  1. 非空左子树的所有键值小于其根结点的键值;
  2. 非空右子树的所有键值大于其根结点的键值;
  3. 左右子树均为二叉搜索树
  4. 树中没有键值相等的结点

可以看到,二叉搜索树的性质很鲜明,这也使得二叉树也有了实际意义。

二叉搜索树的常用操作

对于二叉搜索树,除了常规的4种遍历之外,还有如下一些关键的操作值得我们去关注。

二叉搜索树ADT
二叉搜索树ADT

二叉树的存储结构实现

对于二叉树,我们还是习惯的选择采用链式存储结构实现。

二叉树结点定义

二叉搜索树最大的特点,就是他的元素是可以比较大小的。这一点是需要注意的地方。

/** * Created by engineer on 2017/10/26. * <p> * 二叉搜索树树结点定义 */

public class TreeNode<T extends Comparable<T>> {

    // 数据域
    private T data;
    // 左子树
    public TreeNode<T> leftChild;
    // 右子树
    public TreeNode<T> rightChild;


    public TreeNode(T data) {
        this(null, data, null);
    }

    public TreeNode(TreeNode leftChild, T data, TreeNode rightChild) {
        this.leftChild = leftChild;
        this.data = data;
        this.rightChild = rightChild;
    }

    public T getData() {
        return data;
    }

    public TreeNode<T> getLeftChild() {
        return leftChild;
    }

    public TreeNode<T> getRightChild() {
        return rightChild;
    }

    public void setData(T data) {
        this.data = data;
    }

}

二叉搜索树插入

有了根节点,我们就可以根据二叉树的性质,从根节点出发,构建出一颗二叉树。

/** * 树中插入元素 * * @param value */
    void insert(T value) {
        if (value == null) {
            return;
        }
        root = insert(root, value);
    }

    private TreeNode<T> insert(TreeNode<T> node, T value) {
        if (node == null) {
            // 树为空,则创建根节点
            return new TreeNode<>(value);
        } else {
            if (compare(node, value) < 0) { // 插入值比根节点小,在左子树继续创建二叉搜索树
                node.leftChild = insert(node.getLeftChild(), value);
            } else if (compare(node, value) > 0) { // 插入值比根节点大,在右子树继续创建二叉搜索树
                node.rightChild = insert(node.getRightChild(), value);
            }
        }

        return node;
    }
    private int compare(TreeNode<T> node, T value) {
        return value.compareTo(node.getData());
    }

根据二叉搜索树的特性,我们很容易使用递归实现二叉树的插入操作;总的来说,就是每次插入一个结点,从根节点出发作比较,小的就往左子树插,大的就往右子树插。这和二叉搜索树的定义时完全一致的。

我们可以简单测试一下,这个insert方法的正确性。

测试二叉搜索树插入操作

public class BinarySearchTreeTest {

    private static Integer[] arrays = new Integer[]{10, 8, 3, 12, 9, 4, 5, 7, 1,11, 17};

    public static void main(String[] args) {
        BinarySearchTree<Integer> mSearchTree = new BinarySearchTree<>();

        for (Integer data : arrays) {
            mSearchTree.insert(data);
        }
        // 打印二叉树的三种遍历顺序
        mSearchTree.printTree();

    }
}

关于树的遍历已在上文中详细分析,此处不再做深入探讨

这里定义了一个随机数组,这个将这个数组的按序插入到树中,并按照树的三种遍历结构打印树。按照这个数组我们将构建出如下所示的一颗二叉搜索树:

手绘二叉树
手绘二叉树

看一下程序输出的遍历结果。

前序遍历:10 8 3 1 4 5 7 9 12 11 17 
中序遍历:1 3 4 5 7 8 9 10 11 12 17 
后序遍历:1 7 5 4 3 9 8 11 17 12 10

可以看到,遍历结果和我们画出来二叉树是一致的,因此可以验证插入方法是正确的。

查找

通过插入操作,我们已经实现了一颗二叉搜索树,下面就来看看如何从树中查找元素。

  • 查找最大值与最小值

根据二叉搜索树的特点,我们知道在一颗二叉搜索树上,最小的值一定在最最左边的结点上,而最大值一定在最最右边的结点上。因此,查找二叉树最值就变得非常容易了。


/** * 查找最大值 * * @return */
    public T findMax() {
        if (isEmpty()) return null;
        return findMax(root);
    }

    /** * 从特定结点开始寻找最大值 * * @param node * @return */
    private T findMax(TreeNode<T> node) {
        TreeNode<T> temp = node;
        while (temp.getRightChild() != null) {
            temp = temp.getRightChild();
        }
        return temp.getData();
    }


    /** * 查找最小值 * * @return */
    public T findMin() {
        if (isEmpty()) return null;
        return findMin(root);
    }

    /** * 从特定结点开始寻找最小值 * * @param node * @return */
    private T findMin(TreeNode<T> node) {
        TreeNode<T> temp = node;
        while (temp.getLeftChild() != null) {
            temp = temp.getLeftChild();
        }
        return temp.getData();
    }

可以看到,算法实现非常简单,就是不断后移结点找到没有子树的结点,就是最边界位置的结点了。

  • 查找特定值

在二叉搜索树中,怎样快速找到一个值为特定元素的结点呢?想想我们是怎样实现结点插入的?这个问题就很简单了。

递归实现,查找特定结点

**
/** * find 特定值 递归实现 * * @param value * @return */
    public TreeNode<T> find(T value) {
        if (isEmpty()) {
            return null;
        } else {
            return find(root, value);
        }
    }

    private TreeNode<T> find(TreeNode<T> node, T value) {
        if (node == null) {
            // 当查找一个不在树中元素时,抛出异常
            throw  new RuntimeException("the value must not in the tree");
        }

        if (compare(node, value) < 0) {
            // 小于根节点时,从去左子树找
            return find(node.getLeftChild(), value);
        } else if (compare(node, value) > 0) {
            // 大于根节点时,从右子树找
            return find(node.getRightChild(), value);
        } else {
            // 刚好等于,找到了
            return node;

            // 剩下还有一种情况,就是不等于,也就是所查找的元素不在树中
        }
    }

查找的实现思路,总体上和插入是一致的;无非就是做不同的操作;这里需要注意的是,为了程序的健壮性,我们还得考虑如果查找的元素不在树中这种情况。

迭代实现,查找特定值

有了前面查找最大值、最小值的经验,我们也可以考虑使用迭代算法实现查找指定元素的算法。


/** * 查找特定值-非递归实现 * * @param value * @return 结点 */
    public TreeNode<T> findIter(T value) {
        TreeNode<T> current = root;
        while (current != null) {
            if (compare(current, value) < 0) {
                current = current.getLeftChild();
            } else if (compare(current, value) > 0) {
                current = current.getRightChild();
            } else {
                return current;
            }
        }
        // current为null,说明所查找的元素不在tree里
        return null;
    }

这里同样测试一下,查找方法的正确性:

        System.out.printf("\nfind value %d in mSearchTree \n", 12);
        TreeNode mTreeNode = mSearchTree.find(12);
        TreeNode mTreeNode_1 = mSearchTree.findIter(12);
        System.out.println("递归实现结点 = :" + mTreeNode + ", value=" + mTreeNode.getData());
        System.out.println("非递归实现结点= :" + mTreeNode_1 + ", value=" + mTreeNode_1.getData());

        System.out.println("\nfind the max value in mSearchTree = " + mSearchTree.findMax());
        System.out.println("find the min value in mSearchTree = " + mSearchTree.findMin());

输出:

find value 12 in mSearchTree 
递归实现结点  = :com.avaj.datastruct.tree.bst.TreeNode@4b67cf4d, value=12
非递归实现结点= :com.avaj.datastruct.tree.bst.TreeNode@4b67cf4d, value=12

find the max value in mSearchTree = 17
find the min value in mSearchTree = 1

我们分别用递归和迭代两种方式去查找 12,可以看到两次找到是同一个对象,这个对象的值为12;找到的最大值和最小值也是正确的;因此查找功能的实现是正确的。

删除结点

从二叉搜索树中,删除一个结点可以算是最复杂的操作了,主要是因为所要删除的结点,所处的位置被删除后,依然需要保持整棵树依然为二叉树,因此需要就不同的情况就像分析。

手绘二叉树
手绘二叉树

就拿我们上面创建的这颗二叉树来说,如果要删除的结点是1,7,11,17 这样的叶子结点,就很容易了;让其父结点指向为null即可;而如果是4,5 这样包含一颗子树的结点,换个角度来说,这其实就是单向链表,从单向链表中间位置删除一个结点也比较容易;最麻烦的就是如果要删除的结点是10,8,3,12 这类结点包含左右子树,我们就需要从左子树中找一个最大值,或者是右子树中的最小值来替代这个值。总结一下删除结点的操作:

  • 叶子结点:直接删除,其父结点指向null
  • 包含一个孩子的结点 :父结点指向要删除结点的自结点(相当于链表中间删除一个元素);
  • 包含左右子树的结点:右子树最小值或左子树最大值替换此结点

结合以上分析,得出从二叉搜索树中删除结点的实现。

/** * 从树中删除值为value 的特定结点 * * @param value */
    public void delete(T value) {
        if (value == null || isEmpty()) {
            return;
        }

        root = delete(root, value);
    }


    private TreeNode<T> delete(TreeNode<T> node, T value) {

        // 结点为空,要出删除的元素不在树中
        if (node == null) {
            return node;
        }

        if (compare(node, value) < 0) { // 去左子树删除
            node.leftChild = delete(node.getLeftChild(), value);
        } else if (compare(node, value) > 0) { // 去右子树删除
            node.rightChild = delete(node.getRightChild(), value);
        } else { // 要删除的就是当前结点
            if (node.getLeftChild() != null && node.getRightChild() != null) {// 被删除的结点,包含左右子树
                T temp = findMin(node.getRightChild()); // 得到右子树的最小值
                node.setData(temp); //右子树最小值替换当前结点
                node.rightChild = delete(node.getRightChild(), temp); // 从右子树删除这个最小值的结点
            } else {// 被删除的结点,包含一个子树或没有子树
                if (node.getLeftChild() != null) {
                    node = node.getLeftChild();
                } else {
                    node = node.getRightChild();
                }
            }
        }

        return node;
    }

这里选择使用右子树的最小值替换,是因为删除这个最小值的结点会比较容易,因为他一定是不会是一个包含左右子树的结点。

同样,这里测试一下删除结点的功能:

        // 删除只带一个子树的结点
        mSearchTree.delete(4);
        mSearchTree.printTree();
        System.out.println();
        // 删除带左右子树的根节点
        mSearchTree.delete(10);
        mSearchTree.printTree();

输出:

前序遍历:10 8 3 1 5 7 9 12 11 17 
中序遍历:1 3 5 7 8 9 10 11 12 17 
后序遍历:1 7 5 3 9 8 11 17 12 10 

前序遍历:11 8 3 1 5 7 9 12 17 
中序遍历:1 3 5 7 8 9 11 12 17 
后序遍历:1 7 5 3 9 8 17 12 11

通过和我们一开始画出来的树相比较,发现是对应的。

二叉搜索树的高度

最后,再来看看如何计算一颗二叉搜素树的度。

public int getTreeHeight() {
        if (isEmpty()) {
            return 0;
        }

        return getTreeHeight(root);

    }

    private int getTreeHeight(TreeNode<T> node) {
        if (node == null) {
            return 0;
        }
        int leftHeight = getTreeHeight(node.getLeftChild());
        int rightHeight = getTreeHeight(node.getRightChild());
        int max = leftHeight > rightHeight ? leftHeight : rightHeight;
        // 得到左右子树中较大的返回.
        return max + 1;
    }

顺便来算一算,到最后我们创建的树,经过插入删除操作高度变成了多少。

System.out.println("\n\nTree's height =" + mSearchTree.getTreeHeight());

输出:

Tree's height =5

可以看到,由于结点4被删除,树由原来的6层变成了5层,结果是正确的!


好了,二叉搜索树的分析就是这些了!文中所有源码地址.

今天的文章数据结构-二叉搜索树的实现分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/19800.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注