前言

??我們知道，「 順序表 」 可以 「 快速索引 」 資料，而 「 鏈表 」 則可以快速的進行資料的「 插入 和 洗掉 」，那么，有沒有一種資料結構，可以快速的實作 「 增 」「 刪 」「 改 」「 查 」 呢？
??本文，我們就來聊一下一種 「 樹形 」 的資料結構，它既有鏈表的快速插入與洗掉的特點，又有順序表快速查找的優勢，它就是：

「 二叉搜索樹 」

二叉樹的查找
二叉搜索樹的洗掉
二叉搜索樹的插入
點擊我跳轉末尾 獲取 粉絲專屬 《演算法和資料結構》原始碼，

一、二叉樹的概念

??在學習二叉搜索樹之前，我們首先需要了解下什么是二叉樹，

1、二叉樹的性質

??二叉樹是一種樹，它有如下幾個特征：
????1）每個結點最多 2 棵子樹，即每個結點的孩子結點個數為 0、1、2；
????2）這兩棵子樹是有順序的，分別叫：左子樹 和 右子樹；
????3）如果只有一棵子樹的情況，也需要區分順序，如圖所示：

?? b b b 為 a a a 的左子樹；

?? c c c 為 a a a 的右子樹；

2、特殊二叉樹

1）斜樹

??所有結點都只有左子樹的二叉樹被稱為左斜樹，

??所有結點都只有右子樹的二叉樹被稱為右斜樹，

??斜樹有點類似線性表，所以線性表可以理解為一種特殊形式的樹，

2）滿二叉樹

??對于一棵二叉樹，如果它的所有根結點和內部結點都存在左右子樹，且所有葉子結點都在同一層，這樣的樹就是滿二叉樹，

??滿二叉樹有如下幾個特點：
????1）葉子結點一定在最后一層；
????2）非葉子結點的度為 2；
????3）深度相同的二叉樹，滿二叉樹的結點個數最多，為 2 h ? 1 2^h-1 2h?1（其中 h h h 代表深度），

3）完全二叉樹

??對一棵具有 n n n 個結點的二叉樹按照層序進行編號，如果編號 i i i 的結點和同樣深度的滿二叉樹中的編號 i i i 的結點在二叉樹中位置完全相同，則被稱為 完全二叉樹，

??滿二叉樹一定是完全二叉樹，而完全二叉樹則不一定是滿二叉樹，
??完全二叉樹有如下幾個特點：
????1）葉子結點只能出現在最下面兩層，
????2）最下層的葉子結點一定是集中在左邊的連續位置；倒數第二層如果有葉子結點，一定集中在右邊的連續位置，
????3）如果某個結點度為 1，則只有左子樹，即 不存在只有右子樹 的情況，
????4）同樣結點數的二叉樹，完全二叉樹的深度最小，

??如下圖所示，就不是一棵完全二叉樹，因為 5 號結點沒有右子樹，但是 6 號結點是有左子樹的，不滿足上述第 2 點，

3、二叉樹的性質

??接下來我們來看下，二叉樹有哪些重要的性質，

1）性質1

??【性質1】二叉樹的第 i ( i ≥ 1 ) i (i \ge 1) i(i≥1) 層上至多有 2 i ? 1 2^{i-1} 2i?1 個結點，

??既然是至多，就只需要考慮滿二叉樹的情況，對于滿二叉樹而言，當前層的結點數是上一層的兩倍，第一層的結點數為 1，所以第 i i i 的結點數可以通過等比數列公式計算出來，為 2 i ? 1 2^{i-1} 2i?1，

2）性質2

??【性質2】深度為 h h h 的二叉樹至多有 2 h ? 1 2^{h}-1 2h?1 個結點，

??對于任意一個深度為 h h h 的二叉樹，滿二叉樹的結點數一定是最多的，所以我們可以拿滿二叉樹進行計算，它的每一層的結點數為 1 1 1、 2 2 2、 4 4 4、 8 8 8、…、 2 h ? 1 2^{h-1} 2h?1，
??利用等比數列求和公式，得到總的結點數為：
1 + 2 + 4 + . . . + 2 h ? 1 = 2 h ? 1 1 + 2 + 4 + ... + 2^{h-1} = 2^h - 1 1+2+4+...+2h?1=2h?1

3）性質3

??【性質3】對于任意一棵二叉樹 T T T，如果葉子結點數為 x 0 x_0 x0?，度為 2 的結點數為 x 2 x_2 x2?，則 x 0 = x 2 + 1 x_0 = x_2 + 1 x0?=x2?+1

??令 x 1 x_1 x1? 代表度 為 1 的結點數，總的結點數為 n n n，則有：
n = x 0 + x 1 + x 2 n = x_0 + x_1 + x_2 n=x0?+x1?+x2?
??任意一個結點到它孩子結點的連線我們稱為這棵樹的一條邊，對于任意一個非空樹而言，邊數等于結點數減一，令邊數為 e e e，則有：
e = n ? 1 e = n-1 e=n?1

??對于度為 1 的結點，可以提供 1 條邊，如圖中的黃色結點；對于度為 2 的結點，可以提供 2 條邊，如圖中的紅色結點，所以邊數又可以通過度為 1 和 2 的結點數計算得出： e = x 1 + 2 x 2 e = x_1 + 2 x_2 e=x1?+2x2???聯立上述三個等式，得到： e = n ? 1 = x 0 + x 1 + x 2 ? 1 = x 1 + 2 x 2 e = n-1 = x_0+x_1+x_2 - 1 = x_1 + 2 x_2 e=n?1=x0?+x1?+x2??1=x1?+2x2???化簡后，得證：
x 0 = x 2 + 1 x_0 = x_2 + 1 x0?=x2?+1

4）性質4

??【性質4】具有 n n n 個結點的完全二叉樹的深度為 ? l o g 2 n ? + 1 \lfloor log_2n \rfloor + 1 ?log2?n?+1，

??由【性質2】可得，深度為 h h h 的二叉樹至多有 2 h ? 1 2^{h}-1 2h?1 個結點，所以，假設一棵樹的深度為 h h h，它的結點數為 n n n，則必然滿足：
n ≤ 2 h ? 1 n \le 2^{h}-1 n≤2h?1??由于是完全二叉樹，它一定比深度為 h ? 1 h-1 h?1 的結點數要多，即：
2 h ? 1 ? 1 < n 2^{h-1}-1 \lt n 2h?1?1<n??將上述兩個不等式，稍加整理，得到：
2 h ? 1 ≤ n < 2 h 2^{h-1} \le n \lt 2^h 2h?1≤n<2h??然后，對不等式兩邊取以2為底的對數，得到： h ? 1 ≤ l o g 2 n < h h-1 \le log_2n \lt h h?1≤log2?n<h??這里，由于 h h h 一定是整數，所以有： h = ? l o g 2 n ? + 1 h = \lfloor log_2n \rfloor + 1 h=?log2?n?+1

二、二叉樹的存盤

1、順序表存盤

??二叉樹的順序存盤就是指利用陣列對二叉樹進行存盤，結點的存盤位置即陣列下標，能夠體現結點之間的邏輯關系，比如父結點和孩子結點之間的關系，左右兄弟結點之間的關系 等等，

1）完全二叉樹

??來看一棵完全二叉樹，我們對它進行如下存盤，

??編號代表了陣列下標的絕對位置，映射后如下：

??這里為了方便，我們把陣列下標為 0 的位置給留空了，這樣一來，當知道某個結點的下標 x x x，就可以知道它左右兒子的下標分別為 2 x 2x 2x 和 2 x + 1 2x+1 2x+1；反之，當知道某個結點的下標 x x x，也能知道它父結點的下標為 ? x 2 ? \lfloor \frac x 2 \rfloor ?2x??，

2）非完全二叉樹

??對于非完全二叉樹，只需要將對應不存在的結點設定為空即可，

??編號代表了陣列下標的絕對位置，映射后如下：

3）稀疏二叉樹

??對于較為稀疏的二叉樹，就會有如下情況出現，這時候如果用這種方式進行存盤，就比較浪費記憶體了，

??編號代表了陣列下標的絕對位置，映射后如下：

??于是，我們可以采取鏈表進行存盤，

2、鏈表存盤

??二叉樹每個結點至多有兩個孩子結點，所以對于每個結點，設定一個 資料域 和 兩個 指標域 即可，指標域 分別指向 左孩子結點 和 右孩子結點，

typedef struct TreeNode {
    DataType data;
    struct TreeNode *left;   // (1)
    struct TreeNode *right;  // (2)
}TreeNode;

• ( 1 ) (1) (1) left指向左孩子結點；
• ( 2 ) (2) (2) right指向右孩子結點；
  

三、二叉樹的遍歷

??二叉樹的遍歷是指從根結點出發，按照某種次序依次訪問二叉樹中的所有結點，使得每個結點訪問一次且僅被訪問一次，
??對于線性表的遍歷，要么從頭到尾，要么從尾到頭，遍歷方式較為單純，但是樹不一樣，它的每個結點都有可能有兩個孩子結點，所以遍歷的順序面臨著不同的選擇，
??二叉樹的常用遍歷方法有以下四種：前序遍歷、中序遍歷、后序遍歷、層序遍歷，
??我們用 void visit(TreeNode *root)這個函式代表訪問某個結點，這里為了簡化問題，訪問結點的程序就是列印對應資料域的程序，如下代碼所示：

void visit(TreeNode *root) {
    printf("%c", root->data);
}

1、 前序遍歷

1）演算法描述

??【前序遍歷】如果二叉樹為空，則直接回傳，否則，先訪問根結點，再遞回前序遍歷左子樹，再遞回前序遍歷右子樹，

??前序遍歷的結果如下： a b d g h c e f i abdghcefi abdghcefi，

2）原始碼詳解

void preorder(TreeNode *root) {
    if(root == NULL) {
        return ;            // (1)
    }
    visit(root);            // (2)
    preorder(root->left);   // (3)
    preorder(root->right);  // (4)
}

• ( 1 ) (1) (1) 待訪問結點為空時，直接回傳；
• ( 2 ) (2) (2) 先訪問當前樹的根；
• ( 3 ) (3) (3) 再前序遍歷左子樹；
• ( 4 ) (4) (4) 最后前序遍歷右子樹；

2、 中序遍歷

1）演算法描述

??【中序遍歷】如果二叉樹為空，則直接回傳，否則，先遞回中序遍歷左子樹，再訪問根結點，再遞回中序遍歷右子樹，

??中序遍歷的結果如下： g d h b a e c i f gdhbaecif gdhbaecif，

2）原始碼詳解

void inorder(TreeNode *root) {
    if(root == NULL) {
        return ;            // (1)
    }
    inorder(root->left);    // (2)
    visit(root);            // (3)
    inorder(root->right);   // (4)
}

• ( 1 ) (1) (1) 待訪問結點為空時，直接回傳；
• ( 2 ) (2) (2) 先中序遍歷左子樹；
• ( 3 ) (3) (3) 再訪問當前樹的根；
• ( 4 ) (4) (4) 最后中序遍歷右子樹；

3、 后序遍歷

1）演算法描述

??【后序遍歷】如果二叉樹為空，則直接回傳，否則，先遞回后遍歷左子樹，再遞回后序遍歷右子樹，再訪問根結點，

??后序遍歷的結果如下： g h d b e i f c a ghdbeifca ghdbeifca，

2）原始碼詳解

void postorder(TreeNode *root) {
    if(root == NULL) {
        return ;            // (1)
    }
    postorder(root->left);  // (2)
    postorder(root->right); // (3)
    visit(root);            // (4)
}

• ( 1 ) (1) (1) 待訪問結點為空時，直接回傳；
• ( 2 ) (2) (2) 先后序遍歷左子樹；
• ( 3 ) (3) (3) 再后序遍歷右子樹；
• ( 4 ) (4) (4) 再訪問當前樹的根；

四、二叉搜索樹的概念

1、定義

??二叉搜索樹，又稱為二叉排序樹，二叉查找樹，它滿足如下四點性質：
????1）空樹是二叉搜索樹；
????2）若它的左子樹不為空，則左子樹上所有結點的值均小于它根結點的值；
????3）若它的右子樹不為空，則右子樹上所有結點的值均大于它根結點的值；
????4）它的左右子樹均為二叉搜索樹；

??如圖所示，對于任何一棵子樹而言，它的根結點的值一定大于左子樹所有結點的值，且一定小于右子樹所有結點的值，

2、用途

??從二叉搜索樹的定義可知，它的前提是二叉樹，并且采用了遞回的方式進行定義，它的結點間滿足一個偏序關系，左子樹根結點的值一定比父結點小，右子樹根結點的值一定比父結點大，
??正如它的名字所說，構造這樣一棵樹的目的是為了提高搜索的速度，如果對二叉搜索樹進行中序遍歷，我們可以發現，得到的序列是一個遞增序列，

3、資料結構

??我們用孩子表示法來定義一棵二叉搜索樹的結點，如下：

struct TreeNode {
    int val;                 // (1)
    struct TreeNode *left;   // (2)
    struct TreeNode *right;  // (3)
};

• ( 1 ) (1) (1) 二叉搜索樹結點的值，注意，這里的型別其實可以是任意型別，只要這種型別支持 關系運算子 的比較即可，本文為了把問題簡單話，一律采用整數進行講解，
• ( 2 ) (2) (2) 二叉搜索樹結點的左兒子結點的指標，沒有左兒子結點時，值為NULL；
• ( 3 ) (3) (3) 二叉搜索樹結點的右兒子結點的指標，沒有右兒子結點時，置為NULL；

4、結點創建

??結點創建就是給結點分配一塊記憶體，并且填充它的資料域和指標域，然后回傳這個結點，C語言實作如下：

 struct TreeNode* createNode(int val) { 
     struct TreeNode* node = (struct TreeNode*) malloc( sizeof(struct TreeNode) );
     node->val = val;
     node->left = NULL;
     node->right = NULL;
     return node;
 }

五、二叉搜索樹的操作

1、查找

??二叉搜索樹的查找指的是：在樹上查找某個數是否存在，存在回傳true，不存在回傳false，

1）演算法原理

??對于要查找的數val，從根結點出發，總共四種情況依次判斷：
????1）若為空樹，直接回傳false；
????2）val的值 等于 樹根結點的值，則直接回傳true；
????3）val的值 小于 樹根結點的值，說明val對應的結點不在根結點，也不在右子樹上，則遞回回傳左子樹的 查找 結果；
????4）val的值 大于 樹根結點的值，說明val對應的結點不在根結點，也不在左子樹上，則遞回回傳右子樹的 查找 結果；

2）動圖演示

??如圖所示，代表的是從一個二叉搜索樹中查找一個值為 3 的結點，一開始， 3 比根結點 5 小，于是遞回訪問左子樹；還是比子樹的根結點 4 小，于是繼續遞回訪問左子樹；這時候比根結點 2 大，于是遞回訪問右子樹，正好找到值為 3 的結點，回溯結束查找，

3）原始碼詳解

bool BSTFind(struct TreeNode* root, int val) {    // (1) 
    if(root == NULL) {
        return false;                             // (2) 
    }
    if(root->val == val) {
        return true;                              // (3) 
    } 
    if(val < root->val) {
        return BSTFind(root->left, val);          // (4)
    }else {
        return BSTFind(root->right, val);         // (5)
    }
}

• ( 1 ) (1) (1) BSTFind這個函式用于查找以now為根結點的樹中是否存在值為val這個結點；
• ( 2 ) (2) (2) 空樹是不可能存在值為val的結點的，直接回傳false；
• ( 3 ) (3) (3) 一旦發現有值為val的結點，直接回傳true；
• ( 4 ) (4) (4) val的值 小于 樹根結點的值，說明val對應的結點不在根結點，也不在右子樹上，則遞回回傳左子樹的 查找 結果；
• ( 5 ) (5) (5) val的值 大于 樹根結點的值，說明val對應的結點不在根結點，也不在左子樹上，則遞回回傳右子樹的 查找 結果；

2、插入

??二叉搜索樹的插入指的是：將給定的值生成結點后，插入到樹上的某個位置，并且保持這棵樹還是二叉搜索樹，

1）演算法原理

??對于要插入的數val，從根結點出發，總共四種情況依次判斷：
????1）若為空樹，則創建一個值為val的結點并且回傳；
????2）val的值 等于 樹根結點的值，無須執行插入，直接回傳根結點；
????3）val的值 小于 樹根結點的值，那么插入位置一定在 左子樹，遞回執行插入左子樹的程序，并且回傳插入結果作為新的左子樹；
????4）val的值 大于 樹根結點的值，那么插入位置一定在 右子樹，遞回執行插入右子樹的程序，并且回傳插入結果作為新的右子樹；

2）動圖演示

??如圖所示，代表的是將一個值為 3 的結點插入到一個二叉搜索樹中，一開始， 3 比根結點 5 小，于是遞回插入左子樹；還是比子樹的根結點 4 小，于是繼續遞回插入左子樹；這時候比根結點 2 大，于是遞回插入右子樹，右子樹為空，則直接生成一個值為 3 的結點，回溯結束插入，

3）原始碼詳解

struct TreeNode* BSTInsert(struct TreeNode* root, int val){ // (1)
    if(root == NULL) {                              
        return createNode(val);                             // (2)
    }
    if(val == root->val) {
        return root;                                        // (3)
    }
    if(val < root->val) {                                   // (4)
        root->left = BSTInsert(root->left, val);  
    }else {                                                 // (5)
        root->right = BSTInsert(root->right, val);          
    }
    return root;
}

• ( 1 ) (1) (1) BSTInsert函式用于將值為val的結點插入到以root為根結點的子樹中；
• ( 2 ) (2) (2) 如果是空樹，則創建一個值為val的結點并且回傳；
• ( 3 ) (3) (3) val的值 等于 樹根結點的值，無須執行插入，直接回傳根結點；
• ( 4 ) (4) (4) val的值 小于 樹根結點的值，那么插入位置一定在 左子樹，遞回執行插入左子樹的程序，并且回傳插入結果作為新的左子樹；
• ( 5 ) (5) (5) val的值 大于 樹根結點的值，那么插入位置一定在 右子樹，遞回執行插入右子樹的程序，并且回傳插入結果作為新的右子樹；

3、洗掉

??二叉搜索樹的洗掉指的是：在樹上洗掉給定值的結點，

1）演算法原理

??洗掉值為val的結點的程序，從根結點出發，總共四種情況依次判斷：
????1）空樹，不存在結點直接回傳空樹；
????2）val的值 小于 樹根結點的值，則需要洗掉的結點一定不在右子樹上，遞回呼叫洗掉左子樹的對應結點；
????3）val的值 大于 樹根結點的值，則需要洗掉的結點一定不在左子樹上，遞回呼叫洗掉右子樹的對應結點；
????4）val的值 等于 樹根結點的值，相當于是要洗掉根結點，這時候又要分三種情況：
??????4.1）當前樹只有左子樹，則直接將左子樹回傳，并且釋放當前樹根結點的空間；
??????4.2）當前樹只有右子樹，則直接將右子樹回傳，并且釋放當前樹根結點的空間；
??????4.3）當左右子樹都存在時，需要在右子樹上找到一個值最小的結點，替換新的樹根，而其它結點組成的樹作為它的子樹，并且在子樹中刪掉這個最小的結點，而這一步洗掉的程序正是繼續遞回呼叫結點洗掉的程序；

2）動圖演示

??如圖所示，下圖展示的是，從這棵樹洗掉根結點 5 的程序，首先，由于它有左右兒子結點，所以這個程序，根結點并不是真正的洗掉，而是從右子樹中找到最小的結點 6，替換根結點，并且從根結點為 7 的子樹中洗掉 6 的程序，由于 6 沒有子結點所以這個程序就直接結束了，

3）原始碼詳解

3.1）介面簡介
??在介紹二叉搜索樹的結點洗掉演算法前，我們首先需要知道以下四個介面：

int BSTFindMin(struct TreeNode* root);                       // (2)
struct TreeNode* BSTDelete(struct TreeNode* root, int val);  // (3)
struct TreeNode* Delete(struct TreeNode* root);              // (4)

• ( 1 ) (1) (1) BSTFindMin：查找root為根的樹中，值最小的那個結點的值，根據二叉搜索樹的性質，如果左子樹存在，則必然存在更小的值，遞回搜索左子樹；如果左子樹不存在，則根結點的值必然最小，直接回傳，具體實作見下文；
• ( 2 ) (2) (2) BSTDelete：在root為根的樹中，洗掉值為val的結點，是我們需要實作的洗掉介面，具體實作見下文；
• ( 3 ) (3) (3) Delete：在root為根的樹中，將根結點洗掉，并且使得剩下的樹還是二叉搜索樹，具體實作見下文；

3.2）查找最小結點

int BSTFindMin(struct TreeNode* root) {
    if(root->left)
        return BSTFindMin(root->left);  // (1)
    return root->val;                   // (2)
}

• ( 1 ) (1) (1) 如果左子樹存在，則遞回呼叫左子樹的查找最小結點介面；
• ( 2 ) (2) (2) 如果左子樹不存在，則當前根結點的值一定是最小的，直接回傳介面；

3.3）洗掉給定結點

struct TreeNode* BSTDelete(struct TreeNode* root, int val){
    if(NULL == root) {
        return NULL;                                  // (1)
    }
    if(val == root->val) {
        return Delete(root);                          // (2)
    }
    else if(val < root->val) {
        root->left = BSTDelete(root->left, val);      // (3)
    }else if(val > root->val) {
        root->right = BSTDelete(root->right, val);    // (4)
    }
    return root;                                      // (5)
}

• ( 1 ) (1) (1) 如果為空樹，則直接回傳空結點；
• ( 2 ) (2) (2) 如果需要洗掉的結點，是這棵樹的根結點，則直接呼叫介面Delete，下文會介紹它的實作；
• ( 3 ) (3) (3) 如果需要洗掉的結點的值 小于 樹根結點的值，則需要洗掉的結點必定在左子樹上，遞回呼叫左子樹的洗掉，并且將回傳值作為新的左子樹的根結點；
• ( 4 ) (4) (4) 如果需要洗掉的結點的值 大于 樹根結點的值，則需要洗掉的結點必定在右子樹上，遞回呼叫右子樹的洗掉，并且將回傳值作為新的右子樹的根結點；
• ( 5 ) (5) (5) 最后，回傳當前樹的根結點；

3.4）洗掉給定二叉搜索樹的根結點，并且回傳新的樹根

struct TreeNode* Delete(struct TreeNode* root) {
    struct TreeNode *delNode, *retNode;
    if(root->left == NULL) {          // (1)
        delNode = root, retNode = root->right, free(delNode);
    }else if(root->right == NULL) {   // (2)
        delNode = root, retNode = root->left, free(delNode);
    }else {                           // (3)
        retNode = (struct TreeNode*) malloc (sizeof(struct TreeNode));
        retNode->val = BSTFindMin(root->right);
        retNode->right = BSTDelete(root->right, retNode->val);
        retNode->left = root->left;
    }
    return retNode;
}

• ( 1 ) (1) (1) 如果左子樹為空，則用右子樹做為新的樹根；
• ( 2 ) (2) (2) 如果右子樹為空，則用左子樹作為新的樹根；
• ( 3 ) (3) (3) 否則，當左右子樹都為非空時，利用BSTFindMin，從右子樹上找出最小的結點，作為新的根，并且在右子樹中洗掉對應的結點，洗掉程序就是遞回呼叫BSTDelete的程序；

4、構造

??二叉搜索樹的構造就是：給定一個陣列序列，構造出一個棵二叉搜索樹，

1）演算法原理

??原理比較簡單，一開始是一棵空樹，然后遍歷陣列，對每個元素生成一個結點，不斷執行插入操作，并且回傳新的樹根，就完成了構造的程序，

2）原始碼詳解

struct TreeNode* BSTConstruct(int *vals, int valSize) {
    int i;
    struct TreeNode* root = NULL;         // (1)
    for(i = 0; i < valSize; ++i) {
        root = BSTInsert(root, vals[i]);  // (2)
    }
    return root;
}

• ( 1 ) (1) (1) 初始化空樹；
• ( 2 ) (2) (2) 根據陣列給定順序執行插入樹的操作；

??插入程序需要明確一點，就是如果給定的陣列是嚴格遞增，或者嚴格遞減，就會導致每次插入都要遍歷樹的所有結點，這樣就使得整個插入程序的時間復雜度變成了 O ( n 2 ) O(n^2) O(n2)，改善的方法有幾種：
??方法1：隨機將陣列打亂順序，再執行插入；
??方法2：每次插入后，變換成平衡樹，對于平衡樹相關內容，下篇文章會詳細講解；

六、二叉搜索樹的遍歷

1、先序遍歷

??給定一個某個二叉搜索樹的先序遍歷序列，構造出一棵二叉搜索樹，方法如下：
??1）首先，考慮先序遍歷的特點：先訪問根結點，再依次訪問左右子樹；所以，第一個結點一定是根結點；
??2）然后，陣列往后遍歷的程序中，遇到的所有小于當前根結點的結點，都必然是左子樹上的結點，后面的結點必然是右子樹的（當然，如果檢測到后面的結點有比這個根結點小的，則這個序列無法構造出一棵二叉搜索樹）；
??3）遍歷找到左右子樹的分界點后，就可以進行左右子樹遞回計算了，注意遞回時回傳構造完的子樹的根結點，

2、中序遍歷

??二叉搜索樹的中序遍歷是最常用的，一棵二叉搜索樹的中序遍歷是一個遞增序列，
??遞增序列是存在單調性的，所以可以利用這個特性，在有效的時間內找出這棵樹的第 k k k 大結點，

3、后序遍歷

??給定一個整數陣列，判斷該陣列是不是某二叉搜索樹的后序遍歷結果，方法如下：
??1）從后序遍歷的定義出發，先左子樹，再右子樹，最后根結點，所以，這個序列的最后一個元素，一定是根結點，且所有小于它的元素作為左子樹，所有大于它的元素作為右子樹，
??2）如果能夠分成這樣兩部分，則遞回計算左右子樹；
??3）否則，在出現第一個大于 最后一個元素的情況下，又出現小于 最后一個元素的情況，則表示這是一種非法情況，直接回傳false，

七、二叉搜索樹的總結

??縱觀二叉搜索樹的查找、插入 和 洗掉，完全取決于二叉搜索樹的形狀，如果是完全二叉樹或者接近完全二叉樹，則這三個程序都是 O ( l o g 2 n ) O(log_2n) O(log2?n) 的，如果是斜樹，則三個程序近似操作線性表，為 O ( n ) O(n) O(n)，

??有關 🌳 二叉搜索樹 🌳 的的內容到這里就完全結束了，如果還有什么疑問，可以添加作者微信咨詢，
??有關🌳《畫解資料結構》🌳 的原始碼均開源，鏈接如下：《畫解資料結構》

??相信看我文章的大多數都是「 大學生 」，能上大學的都是「 精英 」，那么我們自然要「 精益求精 」，如果你還是「 大一 」，那么太好了，你擁有大把時間，當然你可以選擇「 刷劇 」，然而，「 學好演算法 」，三年后的你自然「 不能同日而語 」，
??那么這里，我整理了「 幾十個基礎演算法 」 的分類，點擊開啟：

??為了讓這件事情變得有趣，以及「 照顧初學者 」，目前題目只開放最簡單的演算法 「 列舉系列 」 （包括：線性列舉、雙指標、前綴和、二分列舉、三分列舉），當有 一半成員刷完 「 列舉系列 」 的所有題以后，會開放下個章節，等這套題全部刷完，你還在群里，那么你就會成為「 夜深人靜寫演算法 」專家團 的一員，
??不要小看這個專家團，三年之后，你將會是別人 望塵莫及 的存在，如果要加入，可以聯系我，考慮到大家都是學生， 沒有「 主要經濟來源 」，在你成為神的路上，「 不會索取任何 」，

🔥讓天下沒有難學的演算法🔥
C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
入門級C語言真題匯總 🧡《C語言入門100例》🧡
幾張動圖學會一種資料結構 🌳《畫解資料結構》🌳
組團學習，抱團生長 🌌《演算法入門指引》🌌
競賽選手金典圖文教程 💜《夜深人靜寫演算法》💜 ??這篇文章的主要目的是講解二叉搜索樹的一些基礎概念，以及和二叉搜索樹相關的一些經典演算法，但是實際學習程序還是需要看個人的毅力和堅持，下圖代表的是 LeetCode 經典的二叉搜索樹的題集，其中樹是很重要的一個章節，涉及了諸多演算法，希望可以供讀者參考和學習，

粉絲專屬福利

語言入門：《光天化日學C語言》(示例代碼)
語言訓練：《C語言入門100例》試用版
資料結構：《畫解資料結構》原始碼
演算法入門：《演算法入門》指引
演算法進階：《夜深人靜寫演算法》演算法模板

??