部落客秋招提前批已拿百度、位元組跳動、拼多多、順豐等公司的offer，可加微信：pcwl_Java 一起交流秋招面試經驗，可獲得部落客的秋招履歷和複習筆記。
樹是一種非線性資料結構，這種資料結構要比線性資料結構複雜的多，是以分為三篇部落格進行講解：
第一篇：樹的基本概念及常用操作的Java實作（二叉樹為例）
第二篇：二叉查找樹
第三篇：紅黑樹
本文目錄
1、二叉查找樹的基本概念
2、二叉查找樹的查找操作
3、二叉查找樹的插入操作
4、二叉查找樹的删除操作 ---- 重要
4.1 待删除結點沒有子結點
4.2 待删除結點存在左子結點或右子結點時
4.3 待删除結點同時存在左右子結點時
4.4 三種情況代碼整合
5、支援重複資料的二叉查找樹
6、二叉查找樹的時間複雜度分析
7、二叉查找樹和散清單的對比
8、二叉查找樹的常用操作全代碼實作
推薦及參考：
第二篇：二叉查找樹BST
1、寫在前面：二叉查找樹最大的特點就是：支援動态資料集合的快速插入、删除和查找操作。
2、文末附：二叉查找樹的常用操作。
3、這裡需要進行說明下，前面講二叉查找樹的時候，我們預設都是樹中結點存儲的都是數字。很多時候，在實際的軟體開發中，我們在二叉查找樹中存儲的，是一個包含很多字段的對象。我們利用對象的某個字段作為鍵值(key)來建構二叉查找樹。我們把對象中的其他字段叫做衛星資料。
1、二叉查找樹的基本概念
二叉查找樹BST(Binary Sort Tree)：又稱為二叉排序樹/二叉搜尋樹。顧名思義，二叉查找樹是為了實作快速查找而生的。不過它不僅僅支援快速查找一個資料，還支援快速插入、删除一個資料。
具有以下性質的二叉樹稱為二叉查找樹：
1、若左子樹不為空，則左子樹上所有結點的值均小于它的根結點的值；
2、若右子樹不為空，則右子樹上所有的結點的值均大于或等于它的根結點的值；
3、左、右子樹也分别為二叉查找樹。
從上圖可以看出來，二叉查找樹中，左子樹都比父結點小，右子樹都比父結點大，遞歸定義。
是以，根據這個特點，二叉查找樹的中序周遊的結果肯定是有序的，上圖中中序周遊結果為：1、3、4、6、7、8、10、13、14。
2、二叉查找樹的查找操作
根據二叉查找樹的定義，我們可以将二叉查找樹的查找操作大概分為以下幾個步驟：
1、先比較它與根節點，相等就傳回；或者根節點為空，說明樹為空，也傳回；
2、如果它比根節點小，就從根節點的左子樹中進行遞歸查找；
3、如果它比根節點大，就從根節點的右子樹中進行遞歸查找。
【可以看出來，二叉查找樹的查找操作與二分查找十分相似】
public class BinarySearchTree {
private Node root; // 根節點
// 二叉查找樹的查找操作
public Node find(int data){
Node node = root;
while(node != null){
if(data < node.data) node = node.leftChild;
else if(data > node.data) node = node.rightChild;
else return node;
}
return null;
}
// Node内部類
public static class Node{
private int data;
private Node leftChild;
private Node rightChild;
public Node(int data){
this.data = data;
}
}
}
3、二叉查找樹的插入操作
二叉查找樹的插入操作有點類似于查找操作。先查找到合适的位置再插入，新插入的資料一般都在葉子結點上，是以我們隻需要從根結點開始，依次比較要插入的資料和結點的大小關系。
二叉查找樹的插入操作的關鍵幾個步驟如下：
1、如果要插入的資料比根結點的資料大，并且根結點的右子樹為空，就将新資料直接插入到右子結點的位置；如果不為空，就再遞歸周遊右子樹，查找插入位置；
2、同理，如果要插入的資料比根結點數值小，并且結點的左子樹為空，就将新資料插入到左子結點的位置；如果不為空，則周遊左子樹，查找插入位置。
// 二叉查找樹的插入操作
public void insert(int data){
if(root == null){
root = new Node(data);
}
Node node = root;
while(node != null){
if(data > node.data){
if(node.rightChild == null){
node.rightChild = new Node(data); // 右子結點為空，直接将新結點設定為目前結點的右子結點
}
node = node.rightChild; // 右子結點不為空，則繼續周遊目前結點的右子樹
}else{ // data < node.data
if(node.leftChild == null){
node.leftChild = new Node(data); // 左子結點為空，直接将新結點設定為目前結點的左子結點
}
node = node.leftChild; // 左子結點不為空，則繼續周遊目前結點的左子樹
}
}
}
4、二叉查找樹的删除操作
二叉查找樹的删除操作不是很好了解，該章節出自：https://blog.csdn.net/isea533/article/details/80345507
二叉查找樹的删除操作相對于它的查找和插入操作來說複雜的多。針對要删除的結點的子結點個數的不同，我們需要分成三種情況來處理：
1、要删除結點沒有左右子結點，可以直接删除；
2、存在左結點或者右結點中的一個，删除後需要對子結點移動；
3、同時存在左右子結點時，不能簡單地删除，但是可以通過和後繼結點交換後轉換為前兩種情況。
說明：實際上，還有一個特例，就是删除根節點，實作代碼中會展現。
下面就正式對删除操作的三種情況進行說明：
一棵查找二叉樹的初始狀态如下圖所示：
4.1 待删除結點沒有子結點
如圖中值為20的結點。這種情況是最簡單的，我們隻需要删除該結點和它父結點的關系即可。删除的時候需要判斷自己和父結點的關系是左側還是右側，代碼如下：
// 這裡忽略了父結點不存在的情況，三種情況整合時會處理這種情況
if(node.parent.left == node){
node.parent.left = null; // 如果父結點的左子結點是自己，就将其設定為null
}else{
node.parent.right = null; // 如果父結點的右子結點是自己，就将其設定為null
}
4.2 待删除結點存在左子結點或右子結點時
如圖中值為70的結點，删除它時，需要斷開兩個關系：70與它子結點的關系已經70與它父結點的關系，同時建立70子結點與70父結點之間的父子結點關系。
// 先找到要删除結點的子結點，不需要管他是左還是右
BSTNode<T> child = null; // 表示待删除結點的子結點
if(node.left != null){
child = node.left;
}else{
child = node.right;
}
// 這裡忽略了父結點不存在的情況，三種情況整合的時候，會處理
// 将代删除結點的父結點和待删除結點的子結點建立父子結點關系
if(node.parent.left == node){
// 如果待删除結點node是它父結點的左子結點，則将待删除結點node的子結點設定為node父結點的左子結點，即取代它的位置
node.parent.left = child;
}else{
// 如果待删除結點node是它父結點的右子結點，則将待删除結點node的子結點設定為node父結點的右子結點，即取代它的位置
node.parent.right = child;
}
child.parent = node.parent; // 建立node的子結點child中的父結點指針
4.3 待删除結點同時存在左右子結點時
如上圖中值為30的結點。如上圖中二叉查找樹中序周遊的結果，當我們要删除30結點時，整個中序周遊結果從32位都要往前移動一位。而32是30的後繼結點（即比30大的結點中最小的結點）。當某個結點存在右結點時，則它的後繼結點就是它右子樹中最小值，由于左側結點總比右側結點和父結點小，是以後繼結點一定不會是左子樹中的。從這一特點也能想到，待删除結點的後繼結點可能存在右結點或者沒有任何子結點。30的後繼結點還有一個特點就是，他比30的左子樹中的結點大，比30的右子樹中的結點都小，是以删除30的時候，可以之間将後繼結點32轉移到30結點上，然後再删除後繼結點32。又因為後繼結點最多隻有一個子結點（最多隻有一個比它大的右子結點），是以删除後繼結點的時候，就轉換成了3種情況的前兩種情況。
是以，當待删除結點同時存在左子結點和右子結點時，删除操作被分為了兩步：
1、将待删除結點的後繼節點“轉移”到待删除結點上；
2、删除待删除結點的後繼結點。【将删除指定結點轉化為了删除它的後繼結點】
// 擷取目前結點的後繼結點
Node<T> successor = successor(ndoe); // successor()函數的具體實作，後文中會給出
// 1、轉移值
node.data = successor.data
// 2、删除後繼結點successor
node = successor;
4.4 三種情況代碼整合 ---- 重要【這樣寫比較容易了解】
代碼說明：為了展現出其他二叉查找樹的操作，抽象出很多功能函數，互相配合調調用。後面會貼上二叉查找樹的所有常用操作的代碼。
public class BSTree<T extends Comparable<T>>{
BSTNode<T> root; // 根節點
/**
* 删除指定的data結點
*/
public void delete(T data){
// 先查找到要删除的結點
BSTNode<T> node = search(root, data);
// 如果存在就删除
if(node != null){
delete(node);
}
}
/**
* 删除指定的node
*/
public BSTNode<T> delete(BSTNode<T> node){
// 第3種情況，如果同時存在左右子結點
if(node.left != null && node.right != null){
// 擷取待删除結點的後繼結點
BSTNode<T> successor = successor(node);
// 轉移後繼節點值到目前待删除結點上
node.data = successor.data;
// 把要删除的目前結點設定為它的後繼結點
node = successor;
}
// 經過前面一步的處理，下面隻有兩種情況，即：待删除結點有一個子結點或者沒有子結點
// 不管有沒有子結點，都擷取子結點
BSTNode<T> child = null;
if(node.left != null){
child = node.left; // 待删除結點存在左子結點
}else{
child = node.right; // 待删除結點存在右子結點
}
// 如果child ！= null，就說明待删除結點存在一個子結點
if(child != null){
// 将待删除結點的子結點和待删除結點的父結點關聯上
child.parent = node.parent;
}
// 如果目前待删除結點沒有父結點，說明要删除的結點是根結點
if(node.parent == null){
// 将根節點的子節點設定為根節點，按照前面的邏輯下來，根節點隻有一個子結點或者沒有子結點
root = child;
}
// 如果待删除結點有父結點，并且待删除結點是它父結點的左結點時
else if(node == node.parent.left){
// 将父結點的左子結點設定為child
node.parent.left = child;
}
// 如果待删除結點有父結點，并且待删除結點是它父結點的右結點時
else{
// 将父結點的右子結點設定為child
node.parent.right = child;
}
// 傳回被删除的結點
return node;
}
/**
* 找到結點node的後繼節點。即：查找二叉樹中資料大于該結點的最小結點
*/
private BSTNode<T> successor(BSTNode<T> node) {
BSTNode<T> successor = null;
// 如果存在右子結點，則node的後繼結點為以其右子結點為根的右子樹中的最小結點
if(node.right != null){
while(node.right.left != null){
successor = node.right.left; // 最小結點肯定在右子樹中的左子結點中
}
}
// 如果node沒有右子結點，則node有以下兩種情況
BSTNode<T> nodeParent = node.parent;
// 1.node是“一個左子結點”，則node的後繼結點就為node的父結點
if(nodeParent != null && node == node.parent.left){
successor = node.parent;
}
// 2.node是“一個右子結點”，則查找node的“最低”父結點，并且該父結點要有左子結點，那麼這個“最低”的父結點就是node的後繼結點
// 2.1 如果nodeParent是nodeParent.parent的左子結點，則nodeParent.parent就是它的後繼節點
// 2.2如果nodeParent是nodeParent.parent的右子結點，則還需要往上面找，直到node作為它的左子結點時，此時的nodeParent.parent就是它的後繼節點
while(nodeParent != null && node == node.parent.right){
node = node.parent;
nodeParent = nodeParent.parent;
successor = nodeParent;
}
return successor;
}
/**
* 遞歸實作查找以node為根節點的二叉樹中值為data的結點
*/
private BSTNode<T> search(BSTNode<T> node, T data) {
if(node == null){
return node;
}
int cmp = data.compareTo(node.data);
if(cmp < 0) return search(node.left, data); // 在左子樹中找
else if(cmp > 0) return search(node.left, data); // 在右子樹中找
else return node;
}
/**
* BSTNode:結點内部類
*/
public class BSTNode<T extends Comparable<T>>{
T data; // 值
BSTNode<T> left; // 左子結點
BSTNode<T> right; // 右子結點
BSTNode<T> parent; // 父結點
public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right){
this.data= data;
this.parent = parent;
this.left = left;
this.right = right;
}
public T getData(){
return this.data;
}
@Override
public String toString(){
return "data:" + data;
}
}
}
5、支援重複資料的二叉查找樹
前面我們講的二叉查找樹的操作，針對的都是不存在鍵值相同的情況。如果存在存儲兩個對象的鍵值相同的情況，我們可以有兩種解決辦法：
方法1：通過連結清單和支援動态擴容的數組等資料結構實作二叉樹中的結點，把值相同的資料都存儲在同一個結點上；
方法2：每個結點仍然隻存儲一個資料。在查找插入位置的過程中，如果碰到一個結點的值與要插入資料的值相同，那麼就将這個要插入的資料放到這個結點的右子樹中，也就是說把這個新插入的資料當作大于這個結點的值來處理。
第1種方法比較容易了解，下面對第2種方法，進行下說明：
當我們查找資料的時候，遇到值相同的結點，我們并不停止查找操作，而是繼續在右子樹中查找，直到遇到葉子節點，才停止。這樣就可以把鍵值等于要查找值得所有結點都找出來了。
對于删除操作，我們也需要先查找到每個要删除得結點，然後再按照前面講得删除操作的方法，依次删除。
6、二叉查找樹的時間複雜度分析
此章節内容出自于：https://time.geekbang.org/column/article/68334
二叉查找樹的形态多種多樣。比如下圖中，對于同一組資料，我們構造了三種二叉查找樹。它們的查找、插入和删除操作的執行效率都不一樣的。圖中第一種二叉查找樹，根節點的左右子樹極不平衡，已經退化成了連結清單，是以查找的時間複雜度為O(n)。這是最糟糕的情況。
上面分析了最糟糕的情況，下面來分析下最理想的情況，即二叉查找樹是一棵滿二叉樹。
其實從前面的講解中，我們不難發現，不管操作是查找、插入還是删除，時間複雜度都跟樹的高度成正比，也就是O(height)。是以，求解二叉查找樹操作的時間複雜度就轉化為了如何求一棵包含n個結點的完全二叉樹的高度。
樹的高度就等于最大層數減1，為了友善計算，我們轉換為層來表示。從圖中可以看出，包含n個結點的完全二叉樹中，下面一層的結點個數是上面一層的2倍，即第k層包含的結點個數就是2^(k - 1)。不過對于完全二叉樹的最後一層的結點個數就沒有規律了，它包含的結點個數在1~2^(L - 1)個之間（假設最大層數為L）。如果我們把每一層的結點個數加起來就是總的結點個數n。那麼可以得出如下關系：
1 + 2 + 4 + 8 + ... + 2^(L-2) + 1 <= n <= 1 + 2 + 4 + 8 + ... + 2^(L-2) + 2^(L-1) // L-2：不包含最後一層
借助等比數列的求和公式，我們可以計算出L的範圍是[
,
]。完全二叉樹的層數小于等于
，也就是說，完全二叉樹的高度小于等于
。即理想狀态下的完全二叉樹的查找、插入和删除操作的時間複雜度都是O(logn)。
從上面的最壞和最好的二叉查找樹的時間複雜度分析來看，極度不平衡的二叉查找樹的查找性能肯定不能滿足我們的需求。我們需要建構出一種不管怎麼删除、插入和查找資料都能保持任意結點的左、右子樹比較平衡的二叉查找樹，這就是下一篇文章要講的一種特殊的二叉查找樹，即平衡二叉查找樹（紅黑樹）。平衡二叉查找樹的高度接近logn，是以它的查找、插入和删除操作的時間複雜度都比較穩定，是O(logn)。
7、二叉查找樹和散清單的對比
散清單的講解：https://blog.csdn.net/pcwl1206/article/details/83582986
在前面的散清單文章中講過，散清單的查找、插入和删除操作的時間複雜度都可以做到常量級的O(1)，非常的高效。那麼二叉查找樹在比較平衡的情況下，查找、插入和删除操作的時間複雜度才是O(logn)，相對散清單好像沒有什麼優勢，那麼我們為什麼還要用二叉查找樹呢？
主要原因有以下幾個方面：
1、散清單中的資料是無序存儲的，如果要輸出有序的資料，需要先進行排序。對于二叉查找樹來說，隻需要中序周遊，就可以在O(n)的時間複雜度内輸出所有的有序資料；
2、散清單擴容耗時很多，而且當遇到散列沖突的時候，性能不穩定。在工程中，我們常用的平衡二叉查找樹的性能非常穩定，時間複雜度穩定在O(logn)；
3、籠統的來說，盡管散清單的查找等操作的時間複雜度是常量級的，但是因為哈希沖突的存在，這個常量不一定比logn小，是以實際的查找速度可能不一定比O(logn)快。再加上哈希函數的耗時，也不一定比平衡二叉查找樹的效率高；
4、散清單的構造要比二叉查找樹要複雜的多，需要考慮的東西很多。比如散列函數的設計、沖突解決辦法、擴容、縮容等。平衡二叉查找樹隻需要考慮平衡性這一個問題，而且這個問題的解決方案比較成熟、固定。
5、散清單為了避免過多的散列沖突，散清單裝載因子不能太大，特别是基于開放尋址法解決散列沖突的散清單，不然會浪費一定的存儲空間。
綜合以上幾點：平衡二叉查找樹在某些方面還是由于散清單的，是以，這兩者之間并不存在沖突。我們在實際的開發中，需要結合實際的需求再來選擇使用哪一個。
8、二叉查找樹的常用操作全代碼實作
package com.zju.tree;
/**
* @author 作者 pcwl
* @date 建立時間：2018年11月17日 上午9:04:51
* @version 1.0
* @comment 二叉查找樹的操作
*/
public class BSTree<T extends Comparable<T>>{
BSTNode<T> root; // 根節點
public BSTree(){
root = null;
}
/**
* BSTNode:結點内部類
*/
public class BSTNode<T extends Comparable<T>>{
T data; // 值
BSTNode<T> left; // 左子結點
BSTNode<T> right; // 右子結點
BSTNode<T> parent; // 父結點
public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right){
this.data= data;
this.parent = parent;
this.left = left;
this.right = right;
}
public T getData(){
return this.data;
}
@Override
public String toString(){
return "data:" + data;
}
}
/**
* 前序周遊指定結點下的所有結點
*/
public void preOrder(BSTNode<T> node){
if(node != null){
System.out.println(root.data + " ");
preOrder(node.left);
preOrder(node.right);
}
}
/**
* 前序周遊二叉查找樹下的所有結點
*/
public void preOrder(){
preOrder(root);
}
/**
* 中序周遊指定結點下的所有結點
*/
public void inOrder(BSTNode<T> node){
if(node != null){
inOrder(node.left);
System.out.println(node.data + " ");
inOrder(node.right);
}
}
/**
* 中序周遊二叉查找樹下的所有結點
*/
public void inOrder(){
inOrder(root);
}
/**
* 後序周遊指定結點下的所有結點
*/
public void lastOrder(BSTNode<T> node){
if(node != null){
lastOrder(node.left);
lastOrder(node.right);
System.out.println(node.data + " ");
}
}
/**
* 後序周遊二叉查找樹下的所有結點
*/
public void lastOrder(){
lastOrder(root);
}
/**
* 遞歸實作查找以node為根節點的二叉樹中值為data的結點
*/
private BSTNode<T> search(BSTNode<T> node, T data) {
if(node == null){
return node;
}
int cmp = data.compareTo(node.data);
if(cmp < 0) return search(node.left, data); // 在左子樹中找
else if(cmp > 0) return search(node.left, data); // 在右子樹中找
else return node;
}
/**
* 遞歸實作查找根節點下值為data的結點
*/
public BSTNode<T> search(T data){
return search(root, data);
}
/**
* 删除指定的data結點
*/
public void delete(T data){
// 先查找到要删除的結點
BSTNode<T> node = search(root, data);
// 如果存在就删除
if(node != null){
delete(node);
}
}
/**
* 删除指定的node
*/
public BSTNode<T> delete(BSTNode<T> node){
// 第3種情況，如果同時存在左右子結點
if(node.left != null && node.right != null){
// 擷取待删除結點的後繼結點
BSTNode<T> successor = successor(node);
// 轉移後繼節點值到目前待删除結點上
node.data = successor.data;
// 把要删除的目前結點設定為它的後繼結點
node = successor;
}
// 經過前面一步的處理，下面隻有兩種情況，即：待删除結點有一個子結點或者沒有子結點
// 不管有沒有子結點，都擷取子結點
BSTNode<T> child = null;
if(node.left != null){
child = node.left; // 待删除結點存在左子結點
}else{
child = node.right; // 待删除結點存在右子結點
}
// 如果child ！= null，就說明待删除結點存在一個子結點
if(child != null){
// 将待删除結點的子結點和待删除結點的父結點關聯上
child.parent = node.parent;
}
// 如果目前待删除結點沒有父結點，說明要删除的結點是根結點
if(node.parent == null){
// 将根節點的子節點設定為根節點，按照前面的邏輯下來，根節點隻有一個子結點或者沒有子結點
root = child;
}
// 如果待删除結點有父結點，并且待删除結點是它父結點的左結點時
else if(node == node.parent.left){
// 将父結點的左子結點設定為child
node.parent.left = child;
}
// 如果待删除結點有父結點，并且待删除結點是它父結點的右結點時
else{
// 将父結點的右子結點設定為child
node.parent.right = child;
}
// 傳回被删除的結點
return node;
}
/**
* 查找以node為根節點下的最小結點
*/
public BSTNode<T> minNode(BSTNode<T> node){
if(node == null){
return null;
}
// 其實就是找ndoe下的最後一個左子結點
while(node.left != null){
node = node.left;
}
return node;
}
/**
* 查找整棵二叉查找樹下的最小結點
*/
public BSTNode<T> minNode(){
return minNode(root);
}
/**
* 查找以node為根節點下的最大結點
*/
public BSTNode<T> maxNode(BSTNode<T> node){
if(node == null){
return null;
}
// 其實就是找ndoe下的最後一個右子結點
while(node.right != null){
node = node.right;
}
return node;
}
/**
* 查找整棵二叉查找樹下的最大結點
*/
public BSTNode<T> maxNode(){
return maxNode(root);
}
/**
* 找到結點node的後繼節點。即：查找二叉樹中資料大于該結點的最小結點
*/
private BSTNode<T> successor(BSTNode<T> node) {
BSTNode<T> successor = null;
// 如果存在右子結點，則node的後繼結點為以其右子結點為根的右子樹中的最小結點
if(node.right != null){
while(node.right.left != null){
successor = node.right.left; // 最小結點肯定在右子樹中的左子結點中
}
}
// 如果node沒有右子結點，則node有以下兩種情況
BSTNode<T> nodeParent = node.parent;
// 1.node是“一個左子結點”，則node的後繼結點就為node的父結點
if(nodeParent != null && node == node.parent.left){
successor = node.parent;
}
// 2.node是“一個右子結點”，則查找node的“最低”父結點，并且該父結點要有左子結點，那麼這個“最低”的父結點就是node的後繼結點
// 2.1 如果nodeParent是nodeParent.parent的左子結點，則nodeParent.parent就是它的後繼節點
// 2.2如果nodeParent是nodeParent.parent的右子結點，則還需要往上面找，直到node作為它的左子結點時，此時的nodeParent.parent就是它的後繼節點
while(nodeParent != null && node == node.parent.right){
node = node.parent;
nodeParent = nodeParent.parent;
successor = nodeParent;
}
return successor;
}
/**
* 找到結點node的前驅節點。即：查找二叉樹中資料小于該結點的最小結點
*/
private BSTNode<T> predecessor(BSTNode<T> node) {
BSTNode<T> predecessor = null;
// 如果存在左子結點，則node的前驅結點為以其左子結點為根的左子樹中的最大結點
if(node.left != null){
while(node.left.right != null){
predecessor = node.left.right; // 最大結點肯定在左子樹中的右子結點中
}
}
// 如果node沒有左子結點，則node有以下兩種情況
BSTNode<T> nodeParent = node.parent;
// 1.node是“一個右子結點”，則node的前驅結點就為node的父結點
if(nodeParent != null && node == node.parent.left){
predecessor = node.parent;
}
// 2.node是“一個左子結點”，則查找node的“最低”父結點，并且該父結點要有右子結點，那麼這個“最低”的父結點就是node的前驅結點
// 2.1 如果nodeParent是nodeParent.parent的右子結點，則nodeParent.parent就是它的前驅節點
// 2.2如果nodeParent是nodeParent.parent的左子結點，則還需要往上面找，直到node作為它的右子結點時，此時的nodeParent.parent就是它的前驅節點
while(nodeParent != null && node == node.parent.left){
node = node.parent;
nodeParent = nodeParent.parent;
predecessor = nodeParent;
}
return predecessor;
}
/**
* 将結點插入到查找二叉樹中
*/
public void insert(BSTree<T> bst, BSTNode<T> node){
int cmp;
BSTNode<T> node1 = null;
BSTNode<T> root = bst.root;
// 先查找node的插入位置
while(root != null){
node1 = root;
cmp = node.data.compareTo(root.data);
if(cmp < 0){
root = root.left;
}else{
root = root.right;
}
}
node.parent = node1;
if(node1 == null){
bst.root = node;
}else{
cmp = node.data.compareTo(node1.data);
if(cmp < 0){
node1.left = node;
}else{
node1.right = node;
}
}
}
/**
* 銷毀二叉樹
*/
public void destroy(BSTNode<T> node){
if(node == null){
return ;
}
if(node.left != null){
destroy(node.left);
}
if(node.right != null){
destroy(node.right);
}
node = null;
}
/**
* 列印node作為根節點的二叉樹
* direction: 0:表示該結點是根結點
* -1:表示該結點是它父結點的左子結點
* 1:表示該結點是它父結點的右子結點
*/
public void print(BSTNode<T> node, T data, int direction){
if(node != null){
if(direction == 0){
System.out.printf("%2d is root\n", node.data);
}else{
System.out.printf("%2d is %2d's %6s child\n", node.data, data, direction == 1 ? "right" : "left");
}
print(node.left, node.data, -1);
print(node.right, node.data, 1);
}
}
/**
* 列印二叉樹
*/
public void print(){
if(root != null){
print(root, root.data, 0);
}
}
}
推薦及參考：
1、重溫資料結構：二叉排序樹的查找、插入、删除：https://blog.csdn.net/u011240877/article/details/53242179
2、《資料結構與算法之美》：https://time.geekbang.org/column/article/68334
3、二叉樹的删除操作詳解：https://blog.csdn.net/isea533/article/details/80345507【推薦閱讀】