目錄
- 一、背景
- 二、概念
- 三、圖書庫實例
- 3.1、項目需求
- 3.2、代碼結構
- 3.3、圖書類
- 3.4、二分搜索樹的底層實現
- 3.5、圖書庫的構建
- 四、深入理解
一、背景
二叉樹是一種常用的數據結構，更是實現眾多算法的一把利器。本文將通過建立一個圖書庫的實例對二叉樹中的常用類型：二分搜索樹（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}
四、深入理解
- 二分搜索樹的底層是一個鏈點，可以實現高效地插入，刪除以及動態維護。
- 二分搜索樹的結點是有序的，可以很快地求出最大，最小之類的關係值。
- 也正是因為二分搜索樹的結點是有序的，在極端情況下，二分搜索樹會褪化成一個鏈表
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※為什麼 USB CONNECTOR 是電子產業重要的元件?
※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!
※台北網頁設計公司全省服務真心推薦
※想知道最厲害的網頁設計公司"嚨底家"!
※新北清潔公司,居家、辦公、裝潢細清專業服務
※推薦評價好的iphone維修中心
