C++高級數(shù)據(jù)結(jié)構(gòu)之二叉查找樹

更新時(shí)間：2022年05月24日 09:50:04 作者：下一站不是永遠(yuǎn)

這篇文章主要介紹了C++高級數(shù)據(jù)結(jié)構(gòu)之二叉查找樹,文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下

前言：

文章目錄
基礎(chǔ)概念
基本實(shí)現(xiàn)
有序性相關(guān)的方法
與刪除相關(guān)的方法
性能分析
完整代碼和測試

高級數(shù)據(jù)結(jié)構(gòu)（Ⅳ）二叉查找樹

基礎(chǔ)概念

此數(shù)據(jù)結(jié)構(gòu)由結(jié)點(diǎn)組成，結(jié)點(diǎn)包含的鏈接可以為空（null）或者指向其他結(jié)點(diǎn)。在二叉樹中，每個(gè)結(jié)點(diǎn)只能有一個(gè)父結(jié)點(diǎn)（只有一個(gè)例外，也就是根結(jié)點(diǎn)，它沒有父結(jié)點(diǎn)），而且每個(gè)結(jié)點(diǎn)都只有左右兩個(gè)鏈接，分別指向自己的左子結(jié)點(diǎn)和右子結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)的兩個(gè)鏈接都指向了一棵獨(dú)立的子二叉樹或空鏈接。在二叉查找樹中，每個(gè)結(jié)點(diǎn)還包含了一個(gè)鍵和一個(gè)值，鍵之間也有順序之分以支持高校的查找。

定義：一棵二叉查找樹（BST）是一棵二叉樹，
其中每個(gè)結(jié)點(diǎn)都含有一個(gè)Comparable的鍵（以及相關(guān)聯(lián)的值）
且每個(gè)結(jié)點(diǎn)的鍵都大于其左子樹中的任意結(jié)點(diǎn)的鍵而小于右子樹的任意結(jié)點(diǎn)的鍵。

以int類型為鍵，string類型為值的二叉查找樹的API如下：

class BST<Key extends Comparable<Key>, Value>
-------------------------------------------------------------------------------------
Node root; 根結(jié)點(diǎn)
int size(Node x); 返回以結(jié)點(diǎn)x為根節(jié)點(diǎn)的子樹大小
Value get(Key key) 返回鍵key對應(yīng)的值
void put(Key key, Value val) 插入鍵值對{key : val}
Key min() 返回最小鍵
Key max() 返回最大鍵
Key floor(Key key) 向下取整（返回小于等于key的最大值）
Key ceiling(Key key) 向上取整（返回大于等于key的最小值）
Key select(int k) 返回排名為k的鍵
int rank(Key key) 返回鍵key的排名
Iterable<Key> keys(Key lo, Key hi) 返回查找（返回指定范圍內(nèi)的所有鍵值）
void deleteMin() 刪除最小鍵
void deleteMax() 刪除最大鍵
void delete (Key key) 刪除鍵key

基本實(shí)現(xiàn)

數(shù)據(jù)表示

我們嵌套定義一個(gè)私有類來表示二叉查找樹上的一個(gè)結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)都含有一個(gè)鍵、一個(gè)值、一條左鏈接、一條右鏈接和一個(gè)結(jié)點(diǎn)計(jì)數(shù)器。左鏈接指向一棵由小于該結(jié)點(diǎn)的所有鍵組成的二叉查找樹，右鏈接指向一棵由大于該結(jié)點(diǎn)的所有鍵組成的二叉查找樹。變量N給出了以該結(jié)點(diǎn)為根的子樹的結(jié)點(diǎn)總數(shù)。

實(shí)現(xiàn)：

class BST<Key extends Comparable<Key>, Value> {
private Node root; //二叉查找樹的根節(jié)點(diǎn)
private class Node{
private Key key; //鍵
private Value val; //值
private Node left, right; //指向子樹的鏈接
private int N; //以該結(jié)點(diǎn)為根的子樹中的結(jié)點(diǎn)總數(shù)
public Node(Key key, Value val, int N) {
this.key = key;
this.val = val;
this.N = N;
}
}
public int size() {
return size(root);
}
private int size(Node x) {
if (x == null) {
return 0;
} else {
return x.N;
}
}
}

一棵二叉查找樹代表了一組鍵（及其相應(yīng)的值）的集合，而同一個(gè)集合可以用多棵不同的二叉查找樹表示。如果我們將一棵二叉查找樹的所有鍵投影到一條直線上，保證一個(gè)結(jié)點(diǎn)的左子樹中的鍵出現(xiàn)在它的左邊，右子樹中的鍵出現(xiàn)在它的右邊，那么我們一定可以得到一條有序的鍵列。

查找

一般來說，在符號表中查找一個(gè)鍵可能得到兩種結(jié)果。如果含有該鍵的結(jié)點(diǎn)存在于表中，我們的查找就命中了，然后返回相應(yīng)的值。否則查找未命中（并返回null）。根據(jù)數(shù)據(jù)表示的遞歸結(jié)構(gòu)我們馬上就能得到，在二叉查找樹中查找一個(gè)鍵的遞歸算法：如果樹是空的，則查找未命中；如果被查找的鍵和根結(jié)點(diǎn)的鍵相等，查找命中，否則我們就（遞歸地）在適當(dāng)?shù)淖訕渲欣^續(xù)查找。如果被查找的鍵較小就選擇左子樹，較大則選擇右子樹。

/*** 查找 ***/
public Value get(Key key) {
return get(root, key);
}
private Value get(Node x, Key key) {
//在以x為根節(jié)點(diǎn)的子樹中查找并返回key所對應(yīng)的值
//如果找不到則返回null
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
return get(x.left, key);
} else if (cmp > 0) {
return get(x.right, key);
} else {
return x.val;
}
}

插入

二叉查找樹插入的實(shí)現(xiàn)難度和查找差不多。如果樹是空的，就返回一個(gè)含有該鍵值對的新結(jié)點(diǎn)；如果被查找的鍵小于根結(jié)點(diǎn)的鍵，繼續(xù)在左子樹中搜索插入該鍵，否則在右子樹中插入該鍵。

/*** 插入 ***/
public void put(Key key, Value val) {
//查找key，找到則更新它的值，否則為它創(chuàng)建一個(gè)新的結(jié)點(diǎn)
root = put(root, key, val);
}
private Node put(Node x, Key key, Value val) {
//如果key存在于以x為根結(jié)點(diǎn)的子樹中則更新它的值；
//否則將以key和val為鍵值對的新結(jié)點(diǎn)插入到該子樹中
if (x == null) {
return new Node(key, val, 1);
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
x.left = put(x.left, key, val);
} else if (cmp > 0) {
x.right = put(x.right, key, val);
} else {
x.val = val;
}
x.N = size(x.left) + size(x.right) + 1;
return x;
}

有序性相關(guān)的方法

二叉查找樹得以廣泛應(yīng)用的一個(gè)重要原因就是它能夠保持鍵的有序性，因此它可以作為實(shí)現(xiàn)有序符號表API中的眾多方法的基礎(chǔ)。這使得符號表的用例不僅能夠通過鍵還能通過鍵的相對順序來訪問鍵值對。

最小鍵和最大鍵

如果根節(jié)點(diǎn)的左鏈接為空，那么一棵二叉查找樹中最小的鍵就是根結(jié)點(diǎn)；如果左鏈接非空，那么樹中的最小鍵就是左子樹中的最小鍵，顯示可以由遞歸操作實(shí)現(xiàn)。

找出最大鍵的方法也是類似的，只不過是變?yōu)椴檎矣易訕涠选?/p>

最小鍵

/*** 最小鍵 ***/
public Key min() {
if (root == null) {
return null;
}
return min(root).key;
}
private Node min(Node x) {
if (x.left == null) {
return x;
}
return min(x.left);
}

最大鍵

/*** 最大鍵 ***/
public Key max() {
if (root == null) {
return null;
}
return max(root).key;
}
private Node max(Node x) {
if (x.right == null) {
return x;
}
return max(x.right);
}

向上取整和向下取整

如果給定的鍵key小于二叉查找樹的根結(jié)點(diǎn)的鍵，那么小于等于key的最大鍵floor(key)一定在根結(jié)點(diǎn)的左子樹中；如果給定的鍵key大于二叉查找樹的根結(jié)點(diǎn)，那么只有當(dāng)根結(jié)點(diǎn)右子樹中存在小于等于key的結(jié)點(diǎn)時(shí)，小于等于key的最大鍵才會出現(xiàn)在右子樹中，否則根結(jié)點(diǎn)就是小于等于key的最大鍵。這段描述說明了floor()方法的遞歸實(shí)現(xiàn)，同時(shí)也遞推地證明了它能夠計(jì)算出預(yù)期的結(jié)果。將“左”變?yōu)?ldquo;右”（同時(shí)將小于變?yōu)榇笥冢┚湍軌虻玫絚eiling()的算法。

向下取整

/*** 向下取整 ***/
public Key floor(Key key) {
Node x = floor(root, key);
if (x == null) {
return null;
}
return x.key;
}
private Node floor(Node x, Key key) {
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp == 0) {
return x;
}
if (cmp < 0) {
return floor(x.left, key);
}
Node t = floor(x.right, key);
if (t != null) {
return t;
} else {
return x;
}
}

向上取整

/**** 向上取整 **/
public Key ceiling(Key key) {
Node x = ceiling(root, key);
if (x == null) {
return null;
}
return x.key;
}
private Node ceiling(Node x, Key key) {
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp == 0) {
return x;
}
if (cmp > 0) {
return ceiling(x.right, key);
}
Node t = ceiling(x.left, key);
if (t != null) {
return t;
} else {
return x;
}
}

選擇操作

/*** 選擇操作(返回排名為k的鍵) ***/
public Key select(int k) {
if (root == null) {
return null;
}
return select(root, k).key;
}
private Node select(Node x, int k) {
//返回排名為k結(jié)點(diǎn)
if (x == null) {
return null;
}
//注：書中此處為int t = size(x.left);
//個(gè)人覺得此處應(yīng)該加上當(dāng)前結(jié)點(diǎn),即+1（若有建議歡迎指正）
int t = size(x.left) + 1;
if (t > k) {
return select(x.left, k);
} else if (t < k) {
return select(x.right, k - t - 1);
} else {
return x;
}
}

二叉查找樹的選擇操作和基于切分的數(shù)組選擇操作類似。我們在二叉查找樹中的每個(gè)結(jié)點(diǎn)中維護(hù)的子樹結(jié)點(diǎn)計(jì)數(shù)器變量??N??就是用來支持此操作的。

排名

/*** 返回給定鍵key的排名 ***/
public int rank(Key key) {
if (root == null) {
return 0;
}
return rank(root, key);
}
private int rank(Node x, Key key) {
//返回以x為根結(jié)點(diǎn)的子樹中小于x.key的鍵的數(shù)量
if (x == null) {
return 0;
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
return rank(x.left, key);
} else if (cmp > 0) {
return 1 + size(x.left) + rank(x.right, key);
} else {
//若返回給定鍵的排名，我認(rèn)為這里要+1，不然可以在上面調(diào)用后的return語句后+1
//書中此處為return size(x.left)（若有建議歡迎指正）;
return size(x.left) + 1;
}
}

rank()方法是select()方法的逆方法，它會返回給定鍵的排名。它的實(shí)現(xiàn)和select()類似：如果給定的鍵和根結(jié)點(diǎn)的鍵相等，我們返回左子樹中的結(jié)點(diǎn)總數(shù)t；如果給定的鍵小于根結(jié)點(diǎn)，我們會返回該鍵在左子樹中的排名（遞歸計(jì)算）；如果給定的鍵大于根結(jié)點(diǎn)，我們會返回t+1（根結(jié)點(diǎn)）加上它在右子樹中的排名（遞歸計(jì)算）。

范圍查找

/*** 范圍查找（返回給定范圍內(nèi)的所有鍵值） ***/
public Iterable<Key> keys() {
return keys(min(), max());
}

public Iterable<Key> keys(Key lo, Key hi) {
Queue<Key> queue = new LinkedList<Key>();
keys(root, queue, lo, hi);
return queue;
}
private void keys(Node x, Queue<Key> queue, Key lo, Key hi) {
if (x == null) {
return;
}
int cmplo = lo.compareTo(x.key);
int cmphi = hi.compareTo(x.key);
if (cmplo < 0) {
keys(x.left, queue, lo, hi);
}
if (cmplo <= 0 && cmphi >= 0) {
queue.offer(x.key);
}
if (cmphi > 0) {
keys(x.right, queue, lo, hi);
}
}

要實(shí)現(xiàn)能夠返回給定范圍鍵的keys()方法，我們首先需要一個(gè)遍歷二叉查找樹的基本方法，為中序遍歷。要說明這個(gè)方法，我們先看看如何能夠?qū)⒍娌檎覙渲械乃墟I按照順序打印出來。要做到這一點(diǎn)，我們應(yīng)該先打印出根結(jié)點(diǎn)的左子樹中的所有鍵（根據(jù)二叉查找樹的定義它們應(yīng)該都小于根結(jié)點(diǎn)的鍵），然后打印出根結(jié)點(diǎn)的鍵，最后打印出根結(jié)點(diǎn)的右子樹中的所有鍵（根據(jù)二叉查找樹的定義它們應(yīng)該都大于根結(jié)點(diǎn)的鍵）。

與刪除相關(guān)的方法

刪除最小鍵

二叉查找樹中最難實(shí)現(xiàn)的方法就是delete()方法，即從符號表中刪除一個(gè)鍵值對。在此之前，我們先考慮deleteMin()方法（刪除最小鍵所對應(yīng)的鍵值對）。對于deleteMin()，我們要不斷深入根節(jié)點(diǎn)的左子樹直至遇見一個(gè)空鏈接，然后將指向該結(jié)點(diǎn)的右子樹（只需要在遞歸調(diào)用中返回它的右鏈接即可）。此時(shí)它會被垃圾收集器清理掉。我們給出的標(biāo)準(zhǔn)遞歸代碼在刪除結(jié)點(diǎn)后會正確地設(shè)置它的父結(jié)點(diǎn)的鏈接并更新它到根結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)的計(jì)數(shù)器的值。

/*** 刪除最小鍵 ***/
public void deleteMin() {
if (root == null) {
return;
}
deleteMin(root);
}
private Node deleteMin(Node x) {
if (x.left == null) {
return x.right;
}
x.left = deleteMin(x.left);
x.N = size(x.left) + size(x.right) + 1;
return x;
}

刪除最大鍵

deletemax()方法的實(shí)現(xiàn)和deletemin()完全類似，相應(yīng)地，只需刪除右子樹最右端結(jié)點(diǎn)，然后返回其最右端結(jié)點(diǎn)的左子樹即可。

/*** 刪除最大鍵 ***/
public void deleteMax() {
if (root == null) {
return;
}
deleteMax(root);
}
private Node deleteMax(Node x) {
if (x.right == null) {
return x.left;
}
x.right = deleteMax(x.right);
x.N = size(x.left) + size(x.right) + 1;
return x;
}

刪除操作

將指向即將被刪除的結(jié)點(diǎn)的鏈接保存為t;
將x指向它的后繼結(jié)點(diǎn)min(t.right);
將x的右鏈接（原本指向一棵所有結(jié)點(diǎn)都大于x.key的二叉查找樹）指向deleteMin(t.right)，也就是在刪除后所有結(jié)點(diǎn)仍然都大于x.key的子二叉查找樹；
將x的左鏈接（本為空）設(shè)為t.left（其下所有的鍵都小于被刪除的結(jié)點(diǎn)和它的后繼結(jié)點(diǎn)）。

實(shí)現(xiàn)：

/*** 刪除操作 ***/
public void delete (Key key) {
root = delete(root, key);
}

private Node delete(Node x, Key key) {
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
x.left = delete(x.left, key);
} else if(cmp > 0) {
x.right = delete(x.right, key);
} else {
if (x.right == null) {
return x.left;
}
if (x.left == null) {
return x.right;
}
Node t = x;
x = min(t.right);
x.right = deleteMin(t.right);
x.left = t.left;
}
x.N = size(x.left) + size(x.right) + 1;
return x;
}

性能分析

我見過二叉查找樹，但它的實(shí)現(xiàn)沒有使用遞歸。這兩種方式各有哪些優(yōu)缺點(diǎn)？
答：一般來說，遞歸的實(shí)現(xiàn)更容易驗(yàn)證其正確性，而非遞歸的實(shí)現(xiàn)效率更高。

完整代碼和測試

完整代碼

class BST<Key extends Comparable<Key>, Value> {
private Node root; //二叉查找樹的根節(jié)點(diǎn)
private class Node{
private Key key; //鍵
private Value val; //值
private Node left, right; //指向子樹的鏈接
private int N; //以該結(jié)點(diǎn)為根的子樹中的結(jié)點(diǎn)總數(shù)

public Node(Key key, Value val, int N) {
this.key = key;
this.val = val;
this.N = N;
}
}

public int size() {
return size(root);
}

private int size(Node x) {
if (x == null) {
return 0;
} else {
return x.N;
}
}

/*** 查找 ***/
public Value get(Key key) {
return get(root, key);
}

private Value get(Node x, Key key) {
//在以x為根節(jié)點(diǎn)的子樹中查找并返回key所對應(yīng)的值
//如果找不到則返回null
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
return get(x.left, key);
} else if (cmp > 0) {
return get(x.right, key);
} else {
return x.val;
}
}

/*** 插入 ***/
public void put(Key key, Value val) {
//查找key，找到則更新它的值，否則為它創(chuàng)建一個(gè)新的結(jié)點(diǎn)
root = put(root, key, val);
}

private Node put(Node x, Key key, Value val) {
//如果key存在于以x為根結(jié)點(diǎn)的子樹中則更新它的值；
//否則將以key和val為鍵值對的新結(jié)點(diǎn)插入到該子樹中
if (x == null) {
return new Node(key, val, 1);
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
x.left = put(x.left, key, val);
} else if (cmp > 0) {
x.right = put(x.right, key, val);
} else {
x.val = val;
}
x.N = size(x.left) + size(x.right) + 1;
return x;
}

/*** 最小鍵 ***/
public Key min() {
if (root == null) {
return null;
}
return min(root).key;
}

private Node min(Node x) {
if (x.left == null) {
return x;
}
return min(x.left);
}

/*** 最大鍵 ***/
public Key max() {
if (root == null) {
return null;
}
return max(root).key;
}

private Node max(Node x) {
if (x.right == null) {
return x;
}
return max(x.right);
}

/*** 向下取整 ***/
public Key floor(Key key) {
Node x = floor(root, key);
if (x == null) {
return null;
}
return x.key;
}

private Node floor(Node x, Key key) {
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp == 0) {
return x;
}
if (cmp < 0) {
return floor(x.left, key);
}
Node t = floor(x.right, key);
if (t != null) {
return t;
} else {
return x;
}
}

/**** 向上取整 **/
public Key ceiling(Key key) {
Node x = ceiling(root, key);
if (x == null) {
return null;
}
return x.key;
}
private Node ceiling(Node x, Key key) {
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp == 0) {
return x;
}
if (cmp > 0) {
return ceiling(x.right, key);
}
Node t = ceiling(x.left, key);
if (t != null) {
return t;
} else {
return x;
}
}
/*** 選擇操作(返回排名為k的鍵) ***/
public Key select(int k) {
if (root == null) {
return null;
}
return select(root, k).key;
}
private Node select(Node x, int k) {
//返回排名為k結(jié)點(diǎn)
if (x == null) {
return null;
}
int t = size(x.left) + 1;
if (t > k) {
return select(x.left, k);
} else if (t < k) {
return select(x.right, k - t - 1);
} else {
return x;
}
}
/*** 返回給定鍵key的排名 ***/
public int rank(Key key) {
if (root == null) {
return 0;
}
return rank(root, key);
}

private int rank(Node x, Key key) {
//返回以x為根結(jié)點(diǎn)的子樹中小于x.key的鍵的數(shù)量
if (x == null) {
return 0;
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
return rank(x.left, key);
} else if (cmp > 0) {
return 1 + size(x.left) + rank(x.right, key);
} else {
return size(x.left) + 1;
}
}

/*** 范圍查找（返回給定范圍內(nèi)的所有鍵值） ***/
public Iterable<Key> keys() {
return keys(min(), max());
}

public Iterable<Key> keys(Key lo, Key hi) {
Queue<Key> queue = new LinkedList<Key>();
keys(root, queue, lo, hi);
return queue;
}

private void keys(Node x, Queue<Key> queue, Key lo, Key hi) {
if (x == null) {
return;
}
int cmplo = lo.compareTo(x.key);
int cmphi = hi.compareTo(x.key);
if (cmplo < 0) {
keys(x.left, queue, lo, hi);
}
if (cmplo <= 0 && cmphi >= 0) {
queue.offer(x.key);
}
if (cmphi > 0) {
keys(x.right, queue, lo, hi);
}
}

/*** 刪除最小鍵 ***/
public void deleteMin() {
if (root == null) {
return;
}
deleteMin(root);
}

private Node deleteMin(Node x) {
if (x.left == null) {
return x.right;
}
x.left = deleteMin(x.left);
x.N = size(x.left) + size(x.right) + 1;
return x;
}
/*** 刪除最大鍵 ***/
public void deleteMax() {
if (root == null) {
return;
}
deleteMax(root);
}
private Node deleteMax(Node x) {
if (x.right == null) {
return x.left;
}
x.right = deleteMax(x.right);
x.N = size(x.left) + size(x.right) + 1;
return x;
}

/*** 刪除操作 ***/
public void delete (Key key) {
root = delete(root, key);
}

private Node delete(Node x, Key key) {
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
x.left = delete(x.left, key);
} else if(cmp > 0) {
x.right = delete(x.right, key);
} else {
if (x.right == null) {
return x.left;
}
if (x.left == null) {
return x.right;
}
Node t = x;
x = min(t.right);
x.right = deleteMin(t.right);
x.left = t.left;
}
x.N = size(x.left) + size(x.right) + 1;
return x;
}
}

測試

int[] keys = {6, 5, 1, 3, 2, 4, 9, 7, 8, 10};
String[] values = {"F", "E", "A", "C", "B", "D", "I", "G", "H", "J"};

public class BSTTest {
public static void main(String[] args) {
int[] keys = {6, 5, 1, 3, 2, 4, 9, 7, 8, 10};
String[] values = {"F", "E", "A", "C", "B", "D", "I", "G", "H", "J"};

BST<Integer, String> bst = new BST<Integer, String>();
//構(gòu)建樹
for (int i = 0; i < keys.length; i++) {
bst.put(keys[i], values[i]);
}

System.out.println("創(chuàng)建樹的鍵為：");
LinkedList<Integer> queue = (LinkedList<Integer>) bst.keys();
while (!queue.isEmpty()) {
System.out.print(queue.poll() + " ");
}

System.out.println("\n創(chuàng)建樹的大小為：" + bst.size());
System.out.println("鍵3所對應(yīng)的值為：" + bst.get(3));
System.out.println("最小鍵為：" + bst.min());
System.out.println("最大鍵為: " + bst.max());
System.out.println("小于等于11的最大鍵是：" + bst.floor(11));
System.out.println("大于等于0的最小鍵是: " + bst.ceiling(0));
System.out.println("排名為5的鍵是：" + bst.select(5));
System.out.println("鍵7的排名是：" + bst.rank(7));

System.out.println("\n鍵值在3-8之間的鍵有：");
LinkedList<Integer> queue1 = (LinkedList<Integer>) bst.keys(3, 8);
while (!queue1.isEmpty()) {
System.out.print(queue1.poll() + " ");
}
System.out.println("\n刪除最小鍵和最大鍵后的鍵值為：");
bst.deleteMin();
bst.deleteMax();
LinkedList<Integer> queue2 = (LinkedList<Integer>) bst.keys();
while (!queue2.isEmpty()) {
System.out.print(queue2.poll() + " ");
}
System.out.println("\n刪除鍵4后的鍵值為： ");
bst.delete(4);
LinkedList<Integer> queue3 = (LinkedList<Integer>) bst.keys();
while (!queue3.isEmpty()) {
System.out.print(queue3.poll() + " ");
}
}
}

創(chuàng)建樹的鍵為：
1 2 3 4 5 6 7 8 9 10
創(chuàng)建樹的大小為：10
鍵3所對應(yīng)的值為：C
最小鍵為：1
最大鍵為: 10
小于等于11的最大鍵是：10
大于等于0的最小鍵是: 1
排名為5的鍵是：5
鍵7的排名是：7
鍵值在3-8之間的鍵有：
3 4 5 6 7 8
刪除最小鍵和最大鍵后的鍵值為：
2 3 4 5 6 7 8 9
刪除鍵4后的鍵值為：
2 3 5 6 7 8 9
Process finished with exit code 0