一、概念
二叉搜索樹也成二叉排序樹，它有這麼一個特點，某個節點，若其有兩個子節點，則一定滿足，左子節點值一定小於該節點值，右子節點值一定大於該節點值，對於非基本類型的比較，可以實現Comparator接口，在本文中為了方便，採用了int類型數據進行操作。
要想實現一顆二叉樹，肯定得從它的增加說起，只有把樹構建出來了，才能使用其他操作。
二、二叉搜索樹構建
談起二叉樹的增加，肯定先得構建一個表示節點的類，該節點的類，有這麼幾個屬性，節點的值，節點的父節點、左節點、右節點這四個屬性，代碼如下
static class Node{ Node parent; Node leftChild; Node rightChild; int val; public Node(Node parent, Node leftChild, Node rightChild,int val) { super(); this.parent = parent; this.leftChild = leftChild; this.rightChild = rightChild; this.val = val; } public Node(int val){ this(null,null,null,val); } public Node(Node node,int val){ this(node,null,null,val); } }這裡採用的是內部類的寫法，構建完節點值後，再對整棵樹去構建，一棵樹，先得有根節點，再能延伸到餘下子節點，那在這棵樹里，也有一些屬性，比如基本的根節點root,樹中元素大小size，這兩個屬性，如果採用了泛型，可能還得增加Comparator屬性，或提供其一個默認實現。具體代碼如下
public class SearchBinaryTree { private Node root; private int size; public SearchBinaryTree() { super(); }}三、增加
當要進行添加元素的時候，得考慮根節點的初始化，一般情況有兩種、當該類的構造函數一初始化就對根節點root進行初始化，第二種、在進行第一次添加元素的時候，對根節點進行添加。理論上兩個都可以行得通，但通常採用的是第二種懶加載形式。
在進行添加元素的時候，有這樣幾種情況需要考慮
一、添加時判斷root是否初始化，若沒初始化，則初始化，將該值賦給根節點，size加一。
二、因為二叉樹搜索樹滿足根節點值大於左節點，小於右節點，需要將插入的值，先同根節點比較，若大，則往右子樹中進行查找，若小，則往左子樹中進行查找。直到某個子節點。
這裡的插入實現，可以採用兩種，一、遞歸、二、迭代(即通過while循環模式)。
3.1、遞歸版本插入
public boolean add(int val){ if(root == null){ root = new Node(val); size++; return true; } Node node = getAdapterNode(root, val); Node newNode = new Node(val); if(node.val > val){ node.leftChild = newNode; newNode.parent = node; }else if(node.val < val){ node.rightChild = newNode; newNode.parent = node; }else{ // 暫不做處理} size++;19 return true; } /** * 獲取要插入的節點的父節點，該父節點滿足以下幾種狀態之一* 1、父節點為子節點* 2、插入節點值比父節點小，但父節點沒有左子節點* 3、插入節點值比父節點大，但父節點沒有右子節點* 4、插入節點值和父節點相等。 * 5、父節點為空* 如果滿足以上5種情況之一，則遞歸停止。 * @param node * @param val * @return */ private Node getAdapterNode(Node node,int val){ if(node == null){ return node; } // 往左子樹中插入，但沒左子樹，則返回if(node.val > val && node.leftChild == null){ return node; } // 往右子樹中插入，但沒右子樹，也返回if(node.val < val && node.rightChild == null){ return node; } // 該節點是葉子節點，則返回if(node.leftChild == null && node.rightChild == null){ return node; } if(node.val > val && node.leftChild != null){ return getAdaptarNode(node.leftChild, val); }else if(node.val < val && node.rightChild != null){ return getAdaptarNode(node.rightChild, val); }else{ return node; } }使用遞歸，先找到遞歸的結束點，再去把整個問題化為子問題，在上述代碼裡，邏輯大致是這樣的，先判斷根節點有沒有初始化，沒初始化則初始化，完成後返回，之後通過一個函數去獲取適配的節點。之後進行插入值。
3.2、迭代版本
public boolean put(int val){ return putVal(root,val); } private boolean putVal(Node node,int val){ if(node == null){// 初始化根節點node = new Node(val); root = node; size++; return true; } Node temp = node; Node p; int t; /** * 通過do while循環迭代獲取最佳節點， */ do{ p = temp; t = temp.val-val; if(t > 0){ temp = temp.leftChild; }else if(t < 0){ temp = temp.rightChild; }else{ temp.val = val; return false; } }while(temp != null); Node newNode = new Node(p, val); if(t > 0){ p.leftChild = newNode; }else if(t < 0){ p.rightChild = newNode; } size++; return true; }原理其實和遞歸一樣，都是獲取最佳節點，在該節點上進行操作。
論起性能，肯定迭代版本最佳，所以一般情況下，都是選擇迭代版本進行操作數據。
四、刪除
可以說在二叉搜索樹的操作中，刪除是最複雜的，要考慮的情況也相對多，在常規思路中，刪除二叉搜索樹的某一個節點，肯定會想到以下四種情況,
1、要刪除的節點沒有左右子節點，如上圖的D、E、G節點
2、要刪除的節點只有左子節點，如B節點
3、要刪除的節點只有右子節點，如F節點
4、要刪除的節點既有左子節點，又有右子節點，如A、C節點
對於前面三種情況，可以說是比較簡單，第四種複雜了。下面先來分析第一種
若是這種情況，比如刪除D節點，則可以將B節點的左子節點設置為null，若刪除G節點，則可將F節點的右子節點設置為null。具體要設置哪一邊，看刪除的節點位於哪一邊。
第二種，刪除B節點，則只需將A節點的左節點設置成D節點，將D節點的父節點設置成A即可。具體設置哪一邊，也是看刪除的節點位於父節點的哪一邊。
第三種，同第二種。
第四種，也就是之前說的有點複雜，比如要刪除C節點，將F節點的父節點設置成A節點，F節點左節點設置成E節點，將A的右節點設置成F，E的父節點設置F節點(也就是將F節點替換C節點)，還有一種，直接將E節點替換C節點。那採用哪一種呢，如果刪除節點為根節點，又該怎麼刪除？
對於第四種情況，可以這樣想，找到C或者A節點的後繼節點，刪除後繼節點，且將後繼節點的值設置為C或A節點的值。先來補充下後繼節點的概念。
一個節點在整棵樹中的後繼節點必滿足，大於該節點值得所有節點集合中值最小的那個節點，即為後繼節點，當然，也有可能不存在後繼節點。
但是對於第四種情況，後繼節點一定存在，且一定在其右子樹中，而且還滿足，只有一個子節點或者沒有子節點兩者情況之一。具體原因可以這樣想，因為後繼節點要比C節點大，又因為C節點左右子節一定存在，所以一定存在右子樹中的左子節點中。就比如C的後繼節點是F，A的後繼節點是E。
有了以上分析，那麼實現也比較簡單了，代碼如下
public boolean delete(int val){ Node node = getNode(val); if(node == null){ return false; } Node parent = node.parent; Node leftChild = node.leftChild; Node rightChild = node.rightChild; //以下所有父節點為空的情況，則表明刪除的節點是根節點if(leftChild == null && rightChild == null){//沒有子節點if(parent != null){ if(parent.leftChild == node){ parent.leftChild = null; }else if(parent.rightChild == node){ parent.rightChild = null; } }else{//不存在父節點，則表明刪除節點為根節點root = null; } node = null; return true; }else if(leftChild == null && rightChild != null){// 只有右節點if(parent != null && parent.val > val){// 存在父節點，且node位置為父節點的左邊parent.leftChild = rightChild; }else if(parent != null && parent.val < val){// 存在父節點，且node位置為父節點的右邊parent.rightChild = rightChild; }else{ root = rightChild; } node = null; return true; }else if(leftChild != null && rightChild == null){// 只有左節點if(parent != null && parent.val > val){// 存在父節點，且node位置為父節點的左邊parent.leftChild = leftChild; }else if(parent != null && parent.val < val){// 存在父節點，且node位置為父節點的右邊parent.rightChild = leftChild; }else{ root = leftChild; } return true; }else if(leftChild != null && rightChild != null){// 兩個子節點都存在Node successor = getSuccessor(node);// 這種情況，一定存在後繼節點int temp = successor.val; boolean delete = delete(temp); if(delete){ node.val = temp; } successor = null; return true; } return false; } /** * 找到node節點的後繼節點* 1、先判斷該節點有沒有右子樹，如果有，則從右節點的左子樹中尋找後繼節點，沒有則進行下一步* 2、查找該節點的父節點，若該父節點的右節點等於該節點，則繼續尋找父節點， * 直至父節點為Null或找到不等於該節點的右節點。 * 理由，後繼節點一定比該節點大，若存在右子樹，則後繼節點一定存在右子樹中，這是第一步的理由* 若不存在右子樹，則也可能存在該節點的某個祖父節點(即該節點的父節點，或更上層父節點)的右子樹中， * 對其迭代查找，若有，則返回該節點，沒有則返回null * @param node * @return */ private Node getSuccessor(Node node){ if(node.rightChild != null){ Node rightChild = node.rightChild; while(rightChild.leftChild != null){ rightChild = rightChild.leftChild; } return rightChild; } Node parent = node.parent; while(parent != null && (node == parent.rightChild)){ node = parent; parent = parent.parent; } return parent; }具體邏輯，看上面分析，這裡不作文字敘述了，
除了這種實現，在算法導論書中，提供了另外一種實現。
public boolean remove(int val){ Node node = getNode(val); if(node == null){ return false; } if(node.leftChild == null){// 1、左節點不存在，右節點可能存在，包含兩種情況，兩個節點都不存在和只存在右節點transplant(node, node.rightChild); }else if(node.rightChild == null){//2、左孩子存在，右節點不存在transplant(node, node.leftChild); }else{// 3、兩個節點都存在Node successor = getSuccessor(node);// 得到node後繼節點if(successor.parent != node){// 後繼節點存在node的右子樹中。 transplant(successor, successor.rightChild);// 用後繼節點的右子節點替換該後繼節點successor.rightChild = node.rightChild;// 將node節點的右子樹賦給後繼節點的右節點，即類似後繼與node節點調換位置successor.rightChild.parent = successor;// 接著上一步給接過來的右節點的父引用複制} transplant(node, successor); successor.leftChild = node.leftChild; successor.leftChild.parent = successor; } return true; } /** * 將child節點替換node節點* @param root 根節點* @param node 要刪除的節點* @param child node節點的子節點*/ private void transplant(Node node,Node child){ /** * 1、先判斷node是否存在父節點* 1、不存在，則child替換為根節點* 2、存在，則繼續下一步* 2、判斷node節點是父節點的那個孩子(即判斷出node是右節點還是左節點)， * 得出結果後，將child節點替換node節點，即若node節點是左節點則child替換後也為左節點，否則為右節點* 3、將node節點的父節點置為child節點的父節點*/ if(node.parent == null){ this.root = child; }else if(node.parent.leftChild == node){ node.parent.leftChild = child; }else if(node.parent.rightChild == node){ node.parent.rightChild = child; } if(child != null){ child.parent = node.parent; } }五、查找
查找也比較簡單，其實在增加的時候，已經實現了。實際情況中，這部分可以抽出來單獨方法。代碼如下
public Node getNode(int val){ Node temp = root; int t; do{ t = temp.val-val; if(t > 0){ temp = temp.leftChild; }else if(t < 0){ temp = temp.rightChild; }else{ return temp; } }while(temp != null); return null; }六、二叉搜索樹遍歷
在了解二叉搜索樹的性質後，很清楚的知道，它的中序遍歷是從小到大依次排列的，這裡提供中序遍歷代碼
public void print(){ print(root); } private void print(Node root){ if(root != null){ print(root.leftChild); System.out.println(root.val);// 位置在中間，則中序，若在前面，則為先序，否則為後續print(root.rightChild); } }總結
以上所述是小編給大家介紹的java實現二叉搜索樹功能，希望對大家有所幫助，如果大家有任何疑問歡迎給我留言，小編會及時回復大家的！