目錄
- 一、背景
- 二、概念
- 三、圖書庫實例
- 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維修中心
電動車廠特斯拉遇到了新對手，但這並不是寶馬也不是通用汽車，而是來自澳洲大學的一群學生。這些學生研發 eVe 電動車，單次充電後以每小時 100 公里的時速行駛了 500 公里，這也打破了塵封已久的電動車續航世界紀錄。此前，這項記錄為單次充電後，以 72 公里每小時速度跑滿 500 公里。 一直以來，續航能力是電動車推廣普及的最大難題，而 eVe 打破記錄外也表明，電動車可以在合理高速下行駛數百公里。eVe 由澳洲新南威爾士大學 Sunswift 團隊學生研發，到如今已是第五代版本。Sunswift 團隊早前曾以打造太陽能汽車名聲大噪，其推出的 IVy 太陽能動力車在 2011 年跑出了時速達 88 公里/小時，創造了該領域車輛的最快時速記錄。 eVe 電動車配有傳統電池，可以採用使用常規充電樁進行電力補充，其也可以通過覆蓋車身的太陽能電池板充電，車身重量為 317公斤（700磅），使用重量 59 公斤的松下電池，用常規家用插座可在 8 小時內充滿電，若接入工業用電插口，可在 5 小時內充滿。Sunswift 團隊表示，如果 eVe 停在太陽下 8 個小時，搭載的 800 瓦太陽能電池組可以提供 2 小時行駛里程，且太陽能面板還可在車輛行駛過程中收集能量。 Sunswift 團隊負責人Hayden Smith 表示，eVe 證明太陽能電動車是傳統石化燃料汽車可行性替代方案。該團隊希望以此激勵商業公司進入這一技術領域，並促使 eVe 成為澳洲首個合法上路的太陽能電動車。 （圖片來源：）