用一个图书库实例搞懂二分搜索树的底层原理

智慧zhuhuix

发布于 2020-08-14 16:36:13

8640

发布于 2020-08-14 16:36:13

文章被收录于专栏：智慧zhuhuix的开发专栏

一、背景

二叉树是一种常用的数据结构，更是实现众多算法的一把利器。本文将通过建立一个图书库的实例对二叉树中的常用类型：二分搜索树（Binary Search Tree）进行底层原理的深入理解。

二、概念

1、定义

1 二分搜索树是一颗二叉树 2 二分搜索树每个节点的左子树的值都小于该节点的值，每个节点右子树的值都大于该节点的值 3 任意一个节点的每棵子树都满足二分搜索树的定义

2、动画示例

三、图书库实例

3.1、项目需求

创建一个图书类：图书类中需包含ISBN号，书名，作者，定价，出版社、出版日期等
用二分搜索树的数据结构创建一个图书库，每种图书需有当前数量
图书库需实现添加图书，遍历整个图书库，及可根据ISBN号进行快速查找

3.2、代码结构

3.3、图书类

在图书类的定义中，重写compareTo方法：通过比较ISBN(国际标准书号)的大小表示图书在二叉树的结点顺序。

/**
 - 用二分搜索树实现图书库--图书类
 -  - @author zhuhuix
 - @date 2020-06-23
 */
public class Books implements Serializable, Comparable {
    // ISBN
    private Long bookId;
    // 作者
    private String author;
    // 分类
    private String category;
    // 书名
    private String bookName;
    // 定价
    private BigDecimal bookPrice;
    // 出版社
    private String bookPublisher;
    // 出版时间
    private LocalDate bookDate;
    // 当前数量
    private Integer bookCount;

    public Books(Long bookId, String bookName, String category, String author, BigDecimal bookPrice, String bookPublisher, LocalDate bookDate, Integer bookCount) {
        this.bookId = bookId;
        this.author = author;
        this.category = category;
        this.bookName = bookName;
        this.bookPrice = bookPrice;
        this.bookPublisher = bookPublisher;
        this.bookDate = bookDate;
        this.bookCount = bookCount;
    }

    public Books(Long bookId){
        this.bookId= bookId;
    }

    // 通过ISBN号进行比较大小
    @Override
    public int compareTo(Object o) {
        if (o instanceof Books) {
            return this.getBookId().compareTo(((Books) o).getBookId());
        } else {
            return -1;
        }
    }

    public Long getBookId() {
        return bookId;
    }


    public Integer getBookCount() {
        return bookCount;
    }

    public void setBookCount(Integer bookCount) {
        this.bookCount += bookCount;
    }

    @Override
    public String toString() {
        return "{" +
                "ISBN=" + bookId +
                ", 书名='" + bookName + '\'' +
                ", 作者='" + author + '\'' +
                ", 分类='" + category + '\'' +
                ", 价格=" + bookPrice +
                ", 出版社='" + bookPublisher + '\'' +
                ", 出版时间=" + bookDate +
                ", 当前数量=" + bookCount +
                '}';
    }
}

3.4、二分搜索树的底层实现

底层创建内部结点类(class Node)：元素，左子树，右子树
add方法：使用递归方法增加结点： -- 如果图书种类不存在，则创建新结点。 -- 如果图书种类存在，则对数量进行累加。
traverse方法：使用递归方法对所有结点进行遍历
search方法：根据ISBN码查找结点

/**
 * 用二分搜索树实现图书库--二分搜索树
 *
 * @author zhuhuix
 * @date 2020-06-23
 */
public class BinarySearchTree {

    // 结点
    private Node root;
    // 书的种类
    private int bookSize;
    // 书的总数量
    private int bookCount;

    public BinarySearchTree() {
        this.root = null;
        this.bookSize = 0;
        this.bookCount = 0;
    }

    // 增加元素
    public void add(Books data) {
        this.root = addNode(this.root, data);
    }

    // 用递归方法实现结点的添加
    private Node addNode(Node node, Books data) {
        // 递归退出条件 书不存在拉加结点，并将结点数量加1
        if (node == null) {
            this.bookSize++;
            this.bookCount += data.getBookCount();
            return new Node(data);
        }

        if (node.data.compareTo(data) < 0) {
            node.right = addNode(node.right, data);
        } else if (node.data.compareTo(data) > 0) {
            node.left = addNode(node.left, data);
        } else if (node.data.compareTo(data) == 0) {
            // 如果结点已存在，则将书的数量累加
            this.bookCount += data.getBookCount();
            node.getData().setBookCount(data.getBookCount());
        }
        return node;
    }

    // 用递归方法实现结点前序遍历
    public void traverse(Node node) {
        if (node == null) {
            return;
        }
        System.out.println(node.getData().toString());
        traverse(node.left);
        traverse(node.right);
    }

    // 用递归方法实现通过isbn查找图书
    public Books search(Long isbn) {
        Node node = nodeSearch(this.root, new Books(isbn));
        if (node != null) {
            return node.getData();
        } else {
            return null;
        }
    }

    private Node nodeSearch(Node node, Books books) {
        if (node == null) {
            return null;
        }
        if (books.compareTo(node.getData()) == 0) {
            return node;
        } else if (books.compareTo(node.getData()) < 0) {
            return nodeSearch(node.left, books);
        } else {
            return nodeSearch(node.right, books);
        }
    }

    public Node getRoot() {
        return root;
    }

    // 返回书的种类数
    public int getBookSize() {
        return bookSize;
    }

    // 返回书的总数量
    public int getBookCount() {
        return bookCount;
    }

    // 私有内部类-树结点
    private class Node {
        Books data;
        Node left, right;

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

        Books getData() {
            return data;
        }
    }
}

3.5、图书库的构建

构建一棵二分搜索树;
将京东十大畅销图书加入二分搜索树；
统计图书种类及数量，并遍历输出；
加入3种已经进入图书库的图书；
再次统计图书种类及数量，并遍历输出；
根据某个ISBN号查找图书。

/**
 * 用二分搜索树实现图书库
 *
 * @author zhuhuix
 * @date 2020-06-23
 */
public class BookStore {
    public static void main(String[] args) {

        // 构建一棵二分搜索树
        BinarySearchTree bst = new BinarySearchTree();

        // 将十大畅销图书加入二分搜索树
        bst.add(new Books(9787115428028L,"Python编程 从入门到实践",
                "编程语言与程序设计","埃里克·马瑟斯",
                BigDecimal.valueOf(61.40),"人民邮电出版社",
                LocalDate.of(2017,07,01),1));

        bst.add(new Books(9787115525963L,"说服力 工作型PPT该这样做",
                "办公软件","秦阳",
                BigDecimal.valueOf(66.30),"人民邮电出版社",
                LocalDate.of(2020,05,01),1));

        bst.add(new Books(9787569222258L,"零基础学Python（全彩版）",
                "编程语言与程序设计","明日科技",
                BigDecimal.valueOf(67.00),"吉林大学出版社",
                LocalDate.of(2018,04,01),1));

        bst.add(new Books(9787121388361L,"PS之光：一看就懂的Photoshop攻略（全彩）",
                "图形图像/多媒体","冯注龙",
                BigDecimal.valueOf(60.70),"电子工业出版社",
                LocalDate.of(2020,06,01),1));

        bst.add(new Books(9787302423287L,"机器学习",
                "人工智能","周志华",
                BigDecimal.valueOf(64.80),"清华大学出版社",
                LocalDate.of(2016,01,01),1));

        bst.add(new Books(9787111641247L,"深入理解Java虚拟机：JVM高级特性与最佳实践（第3版）",
                "编程语言与程序设计","周志明",
                BigDecimal.valueOf(106.40),"机械工业出版社",
                LocalDate.of(2019,12,01),1));

        bst.add(new Books(9787115472588L,"鸟哥的Linux私房菜 基础学习篇 第四版",
                "操作系统","鸟哥",
                BigDecimal.valueOf(93.00),"人民邮电出版社",
                LocalDate.of(2018,10,01),1));

        bst.add(new Books(9787115293800L,"算法(第4版)",
                "编程语言与程序设计","Robert Sedgewick，Kevin Wayne",
                BigDecimal.valueOf(66.30),"人民邮电出版社",
                LocalDate.of(2012,10,01),1));

        bst.add(new Books(9787115537973L,"数学之美 第三版",
                "计算机理论、基础知识","吴军",
                BigDecimal.valueOf(54.40),"人民邮电出版社",
                LocalDate.of(2020,05,01),1));

        bst.add(new Books(9787302255659L,"大话数据结构",
                "编程语言与程序设计","程杰",
                BigDecimal.valueOf(47.20),"清华大学出版社",
                LocalDate.of(2011,06,01),1));

        // 遍历图书库
        System.out.println("图书库新建：");
        System.out.println("书的种类数："+bst.getBookSize());
        System.out.println("书的总数量："+bst.getBookCount());
        bst.traverse(bst.getRoot());

        // 再次增加相同的书
        bst.add(new Books(9787302255659L,"大话数据结构",
                "编程语言与程序设计","程杰",
                BigDecimal.valueOf(47.20),"清华大学出版社",
                LocalDate.of(2011,06,01),1));

        bst.add(new Books(9787115472588L,"鸟哥的Linux私房菜 基础学习篇 第四版",
                "操作系统","鸟哥",
                BigDecimal.valueOf(93.00),"人民邮电出版社",
                LocalDate.of(2018,10,01),1));

        bst.add(new Books(9787115293800L,"算法(第4版)",
                "编程语言与程序设计","Robert Sedgewick，Kevin Wayne",
                BigDecimal.valueOf(66.30),"人民邮电出版社",
                LocalDate.of(2012,10,01),1));

        // 再次遍历图书库
        System.out.println("图书库同种图书加入：");
        System.out.println("书的种类数："+bst.getBookSize());
        System.out.println("书的总数量："+bst.getBookCount());
        bst.traverse(bst.getRoot());

        // 根据ISBN号查找图书
        Books books =bst.search(9787115472588L);
        if (books!=null) {
            System.out.println("已找到该图书：");
            System.out.println(books.toString());
        }
    }
}

程序输出如下：

图书库新建：
书的种类数：10
书的总数量：10
{ISBN=9787115428028, 书名='Python编程 从入门到实践', 作者='埃里克·马瑟斯', 分类='编程语言与程序设计', 价格=61.4, 出版社='人民邮电出版社', 出版时间=2017-07-01, 当前数量=1}
{ISBN=9787111641247, 书名='深入理解Java虚拟机：JVM高级特性与最佳实践（第3版）', 作者='周志明', 分类='编程语言与程序设计', 价格=106.4, 出版社='机械工业出版社', 出版时间=2019-12-01, 当前数量=1}
{ISBN=9787115293800, 书名='算法(第4版)', 作者='Robert Sedgewick，Kevin Wayne', 分类='编程语言与程序设计', 价格=66.3, 出版社='人民邮电出版社', 出版时间=2012-10-01, 当前数量=1}
{ISBN=9787115525963, 书名='说服力 工作型PPT该这样做', 作者='秦阳', 分类='办公软件', 价格=66.3, 出版社='人民邮电出版社', 出版时间=2020-05-01, 当前数量=1}
{ISBN=9787115472588, 书名='鸟哥的Linux私房菜 基础学习篇 第四版', 作者='鸟哥', 分类='操作系统', 价格=93.0, 出版社='人民邮电出版社', 出版时间=2018-10-01, 当前数量=1}
{ISBN=9787569222258, 书名='零基础学Python（全彩版）', 作者='明日科技', 分类='编程语言与程序设计', 价格=67.0, 出版社='吉林大学出版社', 出版时间=2018-04-01, 当前数量=1}
{ISBN=9787121388361, 书名='PS之光：一看就懂的Photoshop攻略（全彩）', 作者='冯注龙', 分类='图形图像/多媒体', 价格=60.7, 出版社='电子工业出版社', 出版时间=2020-06-01, 当前数量=1}
{ISBN=9787115537973, 书名='数学之美 第三版', 作者='吴军', 分类='计算机理论、基础知识', 价格=54.4, 出版社='人民邮电出版社', 出版时间=2020-05-01, 当前数量=1}
{ISBN=9787302423287, 书名='机器学习', 作者='周志华', 分类='人工智能', 价格=64.8, 出版社='清华大学出版社', 出版时间=2016-01-01, 当前数量=1}
{ISBN=9787302255659, 书名='大话数据结构', 作者='程杰', 分类='编程语言与程序设计', 价格=47.2, 出版社='清华大学出版社', 出版时间=2011-06-01, 当前数量=1}
图书库同种图书加入：
书的种类数：10
书的总数量：13
{ISBN=9787115428028, 书名='Python编程 从入门到实践', 作者='埃里克·马瑟斯', 分类='编程语言与程序设计', 价格=61.4, 出版社='人民邮电出版社', 出版时间=2017-07-01, 当前数量=1}
{ISBN=9787111641247, 书名='深入理解Java虚拟机：JVM高级特性与最佳实践（第3版）', 作者='周志明', 分类='编程语言与程序设计', 价格=106.4, 出版社='机械工业出版社', 出版时间=2019-12-01, 当前数量=1}
{ISBN=9787115293800, 书名='算法(第4版)', 作者='Robert Sedgewick，Kevin Wayne', 分类='编程语言与程序设计', 价格=66.3, 出版社='人民邮电出版社', 出版时间=2012-10-01, 当前数量=2}
{ISBN=9787115525963, 书名='说服力 工作型PPT该这样做', 作者='秦阳', 分类='办公软件', 价格=66.3, 出版社='人民邮电出版社', 出版时间=2020-05-01, 当前数量=1}
{ISBN=9787115472588, 书名='鸟哥的Linux私房菜 基础学习篇 第四版', 作者='鸟哥', 分类='操作系统', 价格=93.0, 出版社='人民邮电出版社', 出版时间=2018-10-01, 当前数量=2}
{ISBN=9787569222258, 书名='零基础学Python（全彩版）', 作者='明日科技', 分类='编程语言与程序设计', 价格=67.0, 出版社='吉林大学出版社', 出版时间=2018-04-01, 当前数量=1}
{ISBN=9787121388361, 书名='PS之光：一看就懂的Photoshop攻略（全彩）', 作者='冯注龙', 分类='图形图像/多媒体', 价格=60.7, 出版社='电子工业出版社', 出版时间=2020-06-01, 当前数量=1}
{ISBN=9787115537973, 书名='数学之美 第三版', 作者='吴军', 分类='计算机理论、基础知识', 价格=54.4, 出版社='人民邮电出版社', 出版时间=2020-05-01, 当前数量=1}
{ISBN=9787302423287, 书名='机器学习', 作者='周志华', 分类='人工智能', 价格=64.8, 出版社='清华大学出版社', 出版时间=2016-01-01, 当前数量=1}
{ISBN=9787302255659, 书名='大话数据结构', 作者='程杰', 分类='编程语言与程序设计', 价格=47.2, 出版社='清华大学出版社', 出版时间=2011-06-01, 当前数量=2}
已找到该图书：
{ISBN=9787115472588, 书名='鸟哥的Linux私房菜 基础学习篇 第四版', 作者='鸟哥', 分类='操作系统', 价格=93.0, 出版社='人民邮电出版社', 出版时间=2018-10-01, 当前数量=2}

四、深入理解

二分搜索树的底层是一个链点，可以实现高效地插入，删除以及动态维护。
二分搜索树的结点是有序的，可以很快地求出最大，最小之类的关系值。
也正是因为二分搜索树的结点是有序的，在极端情况下，二分搜索树会褪化成一个链表

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-06-23 ，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树

数据结构

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

二叉树

数据结构

编程算法

登录后参与评论

0 条评论

热度

用一个图书库实例搞懂二分搜索树的底层原理

用一个图书库实例搞懂二分搜索树的底层原理

一、背景

二、概念

1、定义

2、动画示例

三、图书库实例

3.1、项目需求

3.2、代码结构

3.3、图书类

3.4、二分搜索树的底层实现

3.5、图书库的构建

四、深入理解

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

用一个图书库实例搞懂二分搜索树的底层原理

用一个图书库实例搞懂二分搜索树的底层原理

一、背景

二、概念

1、定义

2、 动画示例

三、图书库实例

3.1、项目需求

3.2、代码结构

3.3、图书类

3.4、二分搜索树的底层实现

3.5、图书库的构建

四、深入理解

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

2、动画示例