OK，看我們題目就可知道啦，今天要分享學習的一種數據結構就是二叉搜索樹。

內容題目也說了三個大概的，分別是尋找、插入、刪除。

講這個之前呢，那么就先講講這個二叉搜索樹是何方神圣呢？

二叉搜索樹：

又稱二叉排序樹，它或者是一顆空樹，或者是具有以下性質的二叉樹：

若它的左子樹不為空，則左子樹上的所有節點的值都小于根節點的值。

若它的右子樹不為空，則右子樹上的所有節點的值都大于根節點的值。

它的左右子樹也分別為二叉搜索樹

示例如下：

OK，講完了這個概念，那么接下來這個操作內容吧。

首先創建這個節點先

public class SearchTree {class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val){this.val=val;}}public TreeNode root=null;
}

以及把這個節點初始一個變量root，置為null。

接下來，就寫這個簡單的方法——查找

查找

public TreeNode search(int key){TreeNode cur=root;while(cur!=null){if(cur.val<key){cur = cur.right;}else if(cur.val>key){cur=cur.left;}else{return cur;}}return null;}

思路：

讓一個cur的節點幫我去走，因為root的左邊比root小，右邊比root大，所以當cur.val小于key時，說明key大往右走，否則往左走，都不是，即找到了，就可以返回當前節點的值了。

插入

先上代碼

public void insert(int val){TreeNode node=new TreeNode(val);if(root==null){root=node;return;}TreeNode cur=root;TreeNode parent=null;while(cur!=null){if(cur.val>val){parent=cur;cur=cur.left;}else if(cur.val<val){parent=cur;cur=cur.right;}else{return;}}if(parent.val>val){parent.left=node;}else{parent.right=node;}}

思路：

先定義好一個Node節點，保存要插入的信息，然后再定義一個parent節點來保存上一個節點的信息，為什么呢？

因為這個總體思路就是要插入的節點的值比這個當前root節點的值進行比大小，大于root就往右走，小于往左走。

接著，再定義一個cur的節點，讓它去走，當cur往左還是往右走時，parent都要走到當前cur的位置

當然，插入一個已有的值，可以選擇return了，

當while循環走完，意味著走到了對的位置了

舉個例子

插入一個2，那么這個cur就得往左走，走到1位置才是正確的，

然后parent也是到了cur的位置。

然后，當前的parent的值和當前val的值相比，大于就插入右邊，小于就插入左邊，

顯然這個例子中，2插入1的右邊。

最后一個內容。

刪除

這里的刪除有些麻煩，要分三種情況

第一種情況

刪除的節點左邊為空

舉個例子

這個當左邊為空時，也有三種狀況。

第一種：當root為刪除的節點時，讓root=cur.right

第二種：當cur為根節點的左邊時，圖中為3，既讓root=cur.right

第三種：當cur為根節點的右邊時，圖中為7，既讓root=cur.right

而根據這里我們也可以寫出第一部分的代碼了

public void remove(int key){TreeNode parent=null;TreeNode cur=root;while(cur!=null){if(cur.val<key){parent=cur;cur=cur.right;}else if(cur.val>key){parent=cur;cur=cur.left;}else{removeNode(parent,cur);}}}private void removeNode(TreeNode parent,TreeNode cur){if(cur.left==null){if(cur==root){root=cur.right;}else if(cur==parent.left){parent.left=cur.right;}else {parent.right=cur.right;}
}

代碼解釋：同樣的，我們刪掉節點之前，也先需要找到這個節點，刪除節點的事讓removeNode來做。

剛剛說明的root=cur.right中的root，當然是讓一個parent來記錄下來（即cur前面節點的信息）

第二種情況

即刪除的節點右邊為空

舉個例子

同樣的，這里也有三種情況

第一種：當刪除的節點為根節點，所以root=cur.left

第二種：當刪除的節點為root的左邊，圖中為3，所以root=cur.left

第三種：當刪除的節點為root的右邊，圖中為7，所以root=cur.left

所以到這里也可以寫一些代碼了

 private void removeNode(TreeNode parent,TreeNode cur){if(cur.left==null){if(cur==root){root=cur.right;}else if(cur==parent.left){parent.left=cur.right;}else {parent.right=cur.right;}}else if(cur.right==null){if(cur==root){root=cur.left;}else if(cur==parent.left){parent.left=cur.left;}else{parent.right=cur.left;}

這個代碼，跟第一種情況是類似的。

第三種情況

即刪除的節點左右都不為空

目錄

二叉搜索樹：

查找

插入

刪除

第一種情況

第二種情況

第三種情況

完！

---

舉個例子

當我們要刪除的節點為cur時，即圖中的60，我們采用的方法是替換法，

即其一的辦法是，在cur的右邊找到其最小值替換掉cur，即圖中的65替換掉60。

同理也可以找到cur的左邊的最大值替換掉cur，

這樣做是因為可以保持整棵樹為一個二叉搜索樹

具體這樣子做（以在cur的右子樹找最小值為例）

定義兩個節點，一個是target，一個是targetParent。

其中，target=cur.right

targetParent=cur

讓這個target去找到其最小值，找到了，再去賦值然后更新要修改的節點

修改完成后，再像其第一種情況中的當targetParent的左邊為空時，讓這個targetParent的左邊指向

target的右邊，相當于指向一個空指針，使其不再引用這個65的節點，達到刪除效果

上代碼

             TreeNode target=cur.right;TreeNode targetParent=cur;while(target !=null){targetParent=target;target =target.left;}cur.val=target.val;if(target ==targetParent.left){targetParent.left=target .right;}else{targetParent.right=target .right;}}

完！