當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

一文彻底掌握二叉查找树

發布時間：2025/3/16 编程问答 13 豆豆

生活随笔收集整理的這篇文章主要介紹了一文彻底掌握二叉查找树小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

在數據結構中，二叉查找樹無疑是極為重要的，但是初學者理解起來卻有些吃力，網上的文章講得也不太全面。本文希望結合多組動圖、圖片以及詳細的代碼實現，力爭讓大家完全掌握二叉查找樹（BST）的各種概念和操作。相信你看完肯定會有收獲。

先看一下本文的目錄吧！每個操作都配有動圖和詳細實現代碼（Java）

背景和必要性

背景

現代計算機和網絡使我們能夠接觸和訪問海量的信息，所以高效的檢索這些信息將是一個巨大的挑戰。這包括信息的存儲、處理和查找。這一問題促使我們去研究經典查找算法，即如何高效的存儲和查找數據？

目標

實現一個符號表，我們將信息（鍵-值）儲存在符號表里，根據相應的鍵去查找它所對應的值。你可以把它想象成一個字典，我們在字典中存儲了大量的詞語的釋義，我們應該能夠根據詞語（索引）去查找這個詞語對應的意思。

如下圖所示，就是一個很簡單的符號表，我們可以很輕松的通過鍵來查找值，但是，基于數組或者鏈表的這種數據結構并不高效，而且不能較好的維持一定的性質（比如我用數組存儲了很多數據，你讓我找到最大的那個，我該怎么辦呢？先在內部排序再輸出，但是，不高效！你是不是會想有沒有一種數據結構天然就滿足這種性質？）

總結一下，我們希望實現一個高效的符號表，它支持插入、查找、求最大鍵和最小鍵、求前驅節點（我們一會再說）和后驅節點等等，它的時間復雜度呢？我們盡量向O(logN)看齊。這就是我們今天的主角--二叉查找樹！

二叉樹知識回顧

二叉樹的定義

直接上幾組圖，你只需要記住每個節點至多有兩個子節點即可。

不平衡

平衡

不平衡

完全退化

這幾張圖幾乎代表了所有類型的二叉樹，你會發現，最后兩個其實就是鏈表，沒錯，二叉樹成功地退化成了鏈表，那性能上肯定會下降，但是關于這個問題如何避免卻不在本文的范圍內，這是下一期文章要解決的問題--[紅黑樹]。我們在這里只是熟悉一下二叉樹的定義就好了。

二叉樹的存儲方法

上一篇文章我們就已經介紹過，這里再重復一遍。二叉樹的存儲方法主要有兩種：鏈式存儲法和線性存儲法，它們分別對應著鏈表和數組。完全二叉樹最好用數組存放，因為數組下標和父子節點之間存在著完美的對應關系，而且也能夠盡最大可能的節省內存，如圖一所示。

我們把根節點儲存在下標為i=1的位置，那么左子節點儲存在2*i=2的位置，右子節點儲存在下標為2*i+1=2的位置。依此類推，完成樹的存儲。借助下標運算，我們可以很輕松的從父節點跳轉到左子節點和右子節點或者從任意一個子節點找到它的父節點。如果X的位置為i，則它的兩個子節點的下標分別為2i和2i+1,它的父節點的位置為i/2(這里結果向下取整)。

相比用數組存儲數據，鏈式存儲法則相應的更加靈活，我們使用自定義類型Node來表示每一個節點。

class?Node{int?data;Node?left,right; }

每個節點都是一個Node對象，它包含我們所需要存儲的數據，指向左子節點的引用，指向右子節點的引用，就像鏈表一樣將整個樹串起來。如果該節點沒有左子節點，則Node.left==null或者Node.right==null，如圖二所示。能理解就行，別在意它的美觀度了:)

二叉樹的遍歷

二叉樹的遍歷有三種方法：前序遍歷，中序遍歷和后序遍歷。在這里我只講和本文我們實現二叉查找樹相關的中序遍歷，如果你希望了解更多，請看上一篇文章吧，那里我給出了詳細的代碼和圖示。

所謂中序遍歷，就是指：對于樹中的任意節點來說，先打印它的左子樹，然后再打印它本身，最后打印它的右子樹。具體的代碼是用遞歸實現的，比較容易理解。

public?void?inOrder(Node?root){if(root==null)?return;inOrder(root.left);Systrm.out.println(root.data);inOrder(root.right); }

你可以結合下面這張圖理解一下

以上，我們回顧了二叉樹的基本知識，請確保你已經完全掌握。接下來我們將介紹今天的主角二叉查找樹(Binary Search Tree),它是一種符號表，成功地將鏈表插入的靈活性和有序數組查找的高效性結合起來。聽起來是不是很完美？

二叉查找樹

一起來看一下它的定義吧，其實只是在二叉樹的定義上做了一個小小的限制：

一棵二叉查找樹是一棵二叉樹，其中每個節點的鍵都大于它的左子樹上的任意節點的鍵，并且小于右子樹上任意節點的鍵。

只要按照這個規則，我們構造出來的樹就是二叉查找樹。現在，請仔細看一下上文所有帶數字的樹，它們都是二叉查找樹。你可能會發現如果我們對二叉查找樹進行中序遍歷的話，得到的序列是有序的，這是二叉查找樹天生的靈活性。具體也可以看一下下面這幅圖：

準備完熱身運動，接下來我們就正式進入二叉查找樹的講解:)。

數據表示
查找數據
插入數據
查找最大值與最小值
查找前驅節點和后繼節點
查找向下取整和向上取整
刪除操作

數據表示

完全等同于二叉樹的鏈式存儲法，我們定義一個節點類Node來表示二叉查找樹上的一個節點，每個節點含有一個鍵，一個值，一個左鏈接，一個有鏈接。其中鍵和值是為了儲存和查找，一般來說，給定鍵，我們能夠快速的找到它所對應的值。

private?class?Node{private?int?key;//鍵private?String?value;//值，我這里把數據設為String，為了和key區分開private?Node?left,right;//指向子樹的鏈接public?Node(int?key,String?value);//Java中的構造函數 }

查找數據

查找操作接受一個鍵值（key），返回該鍵值對應的值（value），如果找不到就返回 null。大致思路是：如果樹是空的，則查找未命中，返回null；如果被查找的鍵和根節點的鍵相等，查找命中，返回根節點對應的值；如果被查找的鍵較小，則在左子樹中繼續查找；如果被查找的鍵較大，則在右子樹中繼續查找。我們用遞歸來實現這個操作，具體的代碼如下：

public?String?find(int?key){return?find(root,key); } private?String?find(Node?x,int?key){//在以x為根結點的子樹中查找并返回鍵key所對應的值//如果找不到，就返回nullif(x==null)?return?null;if(key<x.key)?return?find(x.left,key);else?if(key>x.left)?return?find(x.right,key);else?return?x.value; } //?注意這里用了兩個方法，一個私有一個公開，私有的用來遞歸，公開的對外開放

遞歸代碼的實現是很簡潔的，比較容易理解，我們來看一下動圖：

比如我們想查找32,首先，32小于41，所以對41的左子樹進行查找，32大于20，再對20的右子樹進行查找，緊接著對29的右子樹查找，正好命中32,如果查找不到的話就返回null。

插入數據

我們首先判斷根節點是不是空節點，如果是空節點，就直接創建一個新的Node對象作為根節點即可；如果根節點非空，就通過while循環以及p.key和key的大小比較不斷向下尋找。循環結束時肯定會找到一個空位置，這時我們就創建一個新的Node對象并把它接在這里。當然還有一種情況，如果p.key==key,就更新這個鍵鍵對應的值，結束。

來一起看下面這個例子，向樹中插入31，可以結合著實現方法一（非遞歸）理解一下：

實現方法一（非遞歸實現）：

public?void?insert(int?key,String?value)?{//如果根節點為空節點if?(root?==?null)?{root?=?new?Node(key,value);return;}//根節點不是空節點Node?p?=?root;while?(p?!=?null)?{if?(key?>?p.key)?{?//向右走if?(p.right?==?null)?{p.right?=?new?Node(key,value);return;}p?=?p.right;}?else?if?{?//?key?<?p.key,向左走if?(p.left?==?null)?{p.left?=?new?Node(key,value);return;}p?=?p.left;}else?p.value=value;//如果原來樹中就含有value鍵，則更新它的值}}

實現方法二（遞歸實現）：

public?void?insert(int?key,String?value){root=insert(root,key,value); } private?Node?insert(Node?x,int?key,String?value){//如果key存在于以x為根節點的子樹中則更新它的值；//如果不在就創建新節點插入到合適的位置；if(x==null)?return?new?Node(key,value);if(key<x.key)?x.left=insert(x.left,key,value);else?if(key>x.key)?x.right=insert(x.right,key,value);else?x.value=value;return?x; }

這個遞歸的代碼盡管很簡潔，但卻不是那么容易理解。我先說一下寫遞歸算法需要注意的問題:

1.一個問題的解可以分解為幾個子問題的解何為子問題
這個問題與分解之后的子問題，除了數據規模不同，求解思路完全一樣
3.存在遞歸終止條件

PS:關鍵在于寫出遞推公式，找到終止條件

在這里，遞推公式就是根據條件判斷。然后將根節點對應的樹轉化為規模小一點的左子樹或右子樹，終止條件就是遇到空鏈接

如果實在繞腦子，你只需要理解第一種非遞歸的方法就行了:)。

查找最大值和最小值

這個操作應該是最簡單的了。根據二叉查找樹的定義，最小值就是最左邊的元素，直接從根節點一直向左查找即可。它也有兩種實現方式，具體的代碼如下：

實現一（遞歸實現）

public?int?min(){return?min(root).key; } private?Node?min(Node?x){//?返回以x為根節點的樹的最小節點if(x.left==null)?return?x;return?min(x.left); }

實現二（非遞歸實現）

public?int?min()if(root==null)?return?-1;?//表示不存在最小值Node?x=root;//沿著左子樹一直深入搜索下去，直到遇到左子樹為空的節點，此時當前節?點為最小值while(x.left?!=null)x?=?x.leftreturn?x.key; }

以下是動圖演示:

查找最大元素的道理類似，只需把left換成right即可，在這里就不再多說了，就當給你留的一個作業了:)。

查找前驅節點和后繼節點

前驅節點指的是小于該鍵的最大鍵，后繼節點指的是大于該鍵的最小鍵。你可以結合中序遍歷理解，通過中序遍歷，在得到的序列中位于該點左側的就是前驅節點，右側的就是后驅節點。

舉個例子,如圖所示：

我們首先介紹一下前驅節點的性質：

1.若一個節點有左子樹，那么該節點的前驅節點是其左子樹中最大的節點（也就是左子樹中最右邊的那個節點），示例如下：

2.若一個節點沒有左子樹，那么判斷該節點和其父節點的關系

2.1 若該節點是其父節點的右子節點，那么該節點的前驅節點即為其父節點。示例如下：

2.2 若該節點是其父節點的左子節點，那么需要沿著其父親節點一直向樹的頂端尋找，直到找到一個節點P，P節點是其父節點Q的右子節點，那么Q就是該節點的后繼節點，示例如下：

以上就是尋找的思路，不過實際上我們還有一步操作，就是找到這個給定的節點，在這個過程中，我們同時記錄最近的一個向右走的節點first_parent。具體的代碼如下（已測試）：

????public?int?get_prenode(int?key){if?(root==null)return?-1;//-1表示找不到給定的節點if?(root.key==key)return?-1;Node?p?=?root;Node?pp?=?null;Node??first_parent=null;while?(p?!=?null)?{if?(key>p.key)?{pp?=?p;first_parent=p;p?=?p.right;}?else?if?(key<p.key)?{pp?=?p;?p?=?p.left;}?else?{break;}}if(p==null)?return?-1;else?if(p.left!=null)?return?max(p.left).key;//對應了第1種情況，如果左子樹不為空，則前驅一定是左子樹的最大值，即小于p的最大值（左子樹的值都小于p節點）//以下是左子樹為空的情況2.1else?if(pp.right==p)?return?pp.key;//以下是左子樹為空的情況2.2else?if(pp.left==p)?return?first_parent.key;return?-1;}

向上取整和向下取整

向上取整是指大于等于該鍵的最小鍵，向下取整是指小于等于該鍵的最小值。

向下取整與前驅后繼節點的區別在于查找前驅后繼節點對應的參數是樹中的某一個節點鍵，而向下取整則允許接受任意的鍵作為參數，另一方面，向下取整可以包含等于自己的鍵，是小于等于

關于向上取整與向下取整這兩個操作，我只在算法(第四版)上面見到過，在其他的相關文章中沒有遇到，不過我感覺咱們可以體會一下它的思想，畢竟我感覺這個操作也蠻重要的。

我們拿上圖中查找19前驅節點為例說明一下流程：首先，在以41為根節點的樹中查詢，由于19<41,在41的左子樹查詢，即在以20為根節點的樹中查詢。接著因為19<20,繼續向左，在以11為根結點的樹中查詢。集中注意力，因為19>11,所以11有可能是19的前驅節點，但是前提是11的右子樹中沒有比19小的元素。也就是說我們應該先在11的右子樹中尋找，然后判斷尋找的情況（命中或未命中），如果命中，那就自動返回結果了，如果沒有命中，則說明11就是19的前驅節點!，這其中查找的過程是一個遞歸的過程！希望你仔細體會:)

我只能說到這里了，不好理解:(。具體實現如下：

public?int?floor(int?key){Node?x=floor(root,key);if(x==null)?return?-1;//未查找到return?x.key; } private?Node?floor(Node?x,int?key){if(x==null)?return?null;//表示在以x為根節點的樹中沒有查找到if(key=x.key)?return?x;//命中，且恰好在根節點xif(key<x.key)?return?floor(x.left,key);//在x的左子樹中查詢，根節點有x變為x的子節點，數據規模減小//往下走說明key>x.key,這個時候要去x的右子樹去尋找Node t=floor(x.right,key);//在右子樹中尋找if(t!=null)?return?t;//在右子樹中找到了else?return?x;//在右子樹中沒有找到，那就說明x節點就是要求的前驅節點 }

向上取整的代碼類似，我這里就不詳細說了，你可以自己實現一下。

刪除操作

二叉樹的刪除操作就相對比較復雜了。希望你打起十二分的精神！刪除一個結點只會對一顆二叉查找樹的局部產生一定的影響，所以，我們的任務就是恢復刪除這個結點所帶來的影響。

刪除操作也有遞歸算法，不過我很迷，而且我見很多地方也不是用遞歸實現的，所以這里就不再介紹了，感興趣的話可以看一下算法（第四版），上面有詳細的介紹。好了，不啰嗦了，咱們繼續~

針對待刪除結點的子節點個數的不同，我們將它分為三種情況加以處理。

1.如果要刪除的節點沒有子節點，此時的操作時十分容易的，我們只需要將父節點中指向該節點的鏈接設置為null就可以了。請看下圖,我們的任務是刪除結點27,找到這個節點后直接抹去就 OK 了。

2.如果要刪除的節點只有一個子節點(只有左子節點或只有右子節點)，這種情況也不復雜。我們只需要更新父節點中的指向待刪除結點的鏈接即可，讓它指向待刪除結點的子節點即可。請看下圖，我們的目標是刪除節點50:

3.如果要刪除的節點有兩個子節點，這時就變得復雜了。你聽我仔細描述一下這個過程：我們需要找到這個節點的右子樹上的最小結點【記為H】（因為它沒有左子節點），把【H】替換到我們計劃刪除的節點上；然后，再刪除這個最小的節點【H】（因為它沒有左子節點，所以可以轉化成之前的兩種情況之一），而且，你會發現，二叉查找樹的性質被完美的保留了下來，驚不驚喜！

接下來請看下面這三個例子，它們分別能夠轉化為情況一和情況二：

第一幅圖，想要刪除節點20,它的右子樹的最小節點【H】沒有子節點

第二幅圖，想要刪除節點20,它的右子樹的最小節點【H】存在右節點

注意：【H】不可能有左節點，因為它是最小的

圖一

圖二

具體的代碼如下:

????public?void?delete(int?key){//如果找到鍵為key的結點，就將它刪除，找不到不做處理Node?p=root;//p指向需要刪除的結點，這里初始化為根節點Node?pp=null;//pp記錄的是p的父節點//通過while循環查找Key結點while(p!=null&&p.key!=Key){pp=p;if(Key>p.Key)?p=p.right;else?p=p.left;}if(p==null)?return;//沒有找到//情況一：要刪除的結點有兩個子結點if(p.left!=null&&p.right!=null){//查找右子樹的最小結點Node minP=p.right;//minP是右子樹的最小結點Node minPP=p;//minPP表示minP的父結點while(minP.left!=null){minPP=minP;minP=minP.left;}p.Key=minP.Key;p.val=minP.val;//替換p（將被刪除的結點）的鍵和值//轉化，以下問題只需要將minP刪除即可//因為minP作為右子樹最小的結點，肯定沒有左子結點，可以轉化為情況二處理p=minP;//使p指向右子樹的最小結點pp=minPP;//使被刪除結點的父結點指向右子樹最小結點的父結點}//情況二：待刪除結點是葉子結點（即沒有子結點）或者僅有一個子結點Node child;//p的子結點if(p.left!=null)?child=p.left;else?if(p.right!=null)?child=p.right;else?child=null;//執行刪除操作if(pp==null)?root=child;//刪除的是根結點else?if(pp.left==p)?pp.left=child;else?pp.right=child;}

可以再根據下面這幅圖理解一下:)