最近在看演算法和資料結構方面的東西，提到：“唐納德-克努特在計算機程式設計藝術的第三卷排序和查詢中說道：儘管第一個二分查詢演算法於1946年出現，然而第一個完全正確的二分查詢演算法實現直到1962年才出現。”

1. 不重複的二叉查詢樹比較簡單，像下面就行：

上面這種是最基本的二叉搜尋樹，但是真正需要留意的是下面這幾種二叉搜尋樹的變種，所謂的“十個二分九個錯”。

2. 查詢第一個值等於給定值的元素；

3. 查詢最後一個值等於給定值的元素；

4. 查詢第一個大於等於給定值的元素；

5. 查詢最後一個小於等於給定值的元素；

需要的時候可以網上搜索一下具體答案，基礎還是最普通的二分搜尋，但對大於，小於和等於的處理有一些差異。

二叉搜尋樹需滿足以下四個條件：

若任意節點的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；若任意節點的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；任意節點的左、右子樹也分別為二叉查詢樹；沒有鍵值相等的節點。

　　二叉搜尋樹舉例：

　　

　　　　　　　　　　　　　　　　　　　　　　　　　圖一

　　接下來將基於圖一介紹二叉搜尋樹相關操作。

　　首先，應先有一個節點物件相關的類，命名為 Node。

　　

1 class Node { 2 int key; 3 int value; 4 Node leftChild; 5 Node rightChild; 6 7 public Node(int key, int value) { 8 this.key = key; 9 this.value = value;10 }11 12 public void displayNode() {13 14 }15 }

　　Node 類中包含 key 值，用於確定節點在樹中相應位置，value 值代表要儲存的內容，還含有指向左右孩子節點的兩個引用。

　　接下來看下搜尋樹相應的類：

　　

1 class Tree { 2 Node root;//儲存樹的根 3 4 public Node find(int key) {//查詢指定節點 5 6 } 7 8 public void insert(int key, int value) {//插入節點 9 10 }11 12 public boolean delete(int key) {//刪除指定節點13 14 }15 16 private Node getDirectPostNode(Node delNode) {//得到待刪除節點的直接後繼節點17 18 }19 20 public void preOrder(Node rootNode) {//先序遍歷樹21 22 }23 24 public void inOrder(Node rootNode) {//中序遍歷樹25 26 }27 28 public void postOrder(Node rootNode) {//後序遍歷樹29 30 }31 }

　　　類中表示樹的框架，包含查詢、插入、遍歷、刪除相應方法，其中刪除節點操作最為複雜，接下來一一介紹。

　　一、查詢某個節點

　　　　由於二叉搜尋樹定義上的特殊性，只需根據輸入的 key 值從根開始進行比較，若小於根的 key 值，則與根的左子樹比較，大於根的key值與根的右子樹比較，以此類推，找到則返回相應節點，否則返回 null。

1 public Node find(int key) { 2 Node currentNode = root; 3 while (currentNode != null && currentNode.key != key) { 4 if (key < currentNode.key) { 5 currentNode = currentNode.leftChild; 6 } else { 7 currentNode = currentNode.rightChild; 8 } 9 }10 return currentNode;11 }

　　　二、插入節點

　　　　與查詢操作相似，由於二叉搜尋樹的特殊性，待插入的節點也需要從根節點開始進行比較，小於根節點則與根節點左子樹比較，反之則與右子樹比較，直到左子樹為空或右子樹為空，則插入到相應為空的位置，在比較的過程中要注意儲存父節點的資訊 及 待插入的位置是父節點的左子樹還是右子樹，才能插入到正確的位置。

1 public void insert(int key, int value) { 2 if (root == null) { 3 root = new Node(key, value); 4 return; 5 } 6 Node currentNode = root; 7 Node parentNode = root; 8 boolean isLeftChild = true; 9 while (currentNode != null) {10 parentNode = currentNode;11 if (key < currentNode.key) {12 currentNode = currentNode.leftChild;13 isLeftChild = true;14 } else {15 currentNode = currentNode.rightChild;16 isLeftChild = false;17 }18 }19 Node newNode = new Node(key, value);20 if (isLeftChild) {21 parentNode.leftChild = newNode;22 } else {23 parentNode.rightChild = newNode;24 }25 }

　　　　三、遍歷二叉搜尋樹

　　　　遍歷操作與遍歷普通二叉樹操作完全相同，不贅述。

1 public void preOrder(Node rootNode) { 2 if (rootNode != null) { 3 System.out.println(rootNode.key + " " + rootNode.value); 4 preOrder(rootNode.leftChild); 5 preOrder(rootNode.rightChild); 6 } 7 } 8 9 public void inOrder(Node rootNode) {10 if (rootNode != null) {11 inOrder(rootNode.leftChild);12 System.out.println(rootNode.key + " " + rootNode.value);13 inOrder(rootNode.rightChild);14 }15 }16 17 public void postOrder(Node rootNode) {18 if (rootNode != null) {19 postOrder(rootNode.leftChild);20 postOrder(rootNode.rightChild);21 System.out.println(rootNode.key + " " + rootNode.value);22 }23 }　　public boolean delete(int key) { Node currentNode = root;//用來儲存待刪除節點 Node parentNode = root;//用來儲存待刪除節點的父親節點 boolean isLeftChild = true;//用來確定待刪除節點是父親節點的左孩子還是右孩子 while (currentNode != null && currentNode.key != key) { parentNode = currentNode; if (key < currentNode.key) { currentNode = currentNode.leftChild; isLeftChild = true; } else { currentNode = currentNode.rightChild; isLeftChild = false; } } if (currentNode == null) { return false; } if (currentNode.leftChild == null && currentNode.rightChild == null) {//要刪除的節點為葉子節點 if (currentNode == root) root = null; else if (isLeftChild) parentNode.leftChild = null; else parentNode.rightChild = null; } ...... }

　　

　　　　由以上分析可得程式碼如下（接上述 delete 方法省略號後）：

1 else if (currentNode.rightChild == null) {//要刪除的節點只有左孩子 2 if (currentNode == root) 3 root = currentNode.leftChild; 4 else if (isLeftChild) 5 parentNode.leftChild = currentNode.leftChild; 6 else 7 parentNode.rightChild = currentNode.leftChild; 8 } else if (currentNode.leftChild == null) {//要刪除的節點只有右孩子 9 if (currentNode == root)10 root = currentNode.rightChild;11 else if (isLeftChild)12 parentNode.leftChild = currentNode.rightChild;13 else14 parentNode.rightChild = currentNode.rightChild;15 } ......

　　　　例如刪除圖一中 key 值為 10 的節點，這時就需要用 key 值為 10 的節點的中序後繼節點（節點 11）來代替 key 值為 10 的節點，並刪除 key 值為 10 的節點的中序後繼節點，由中序遍歷相關規則可知， key 值為 10 的節點的直接中序後繼節點一定是其右子樹中 key 值最小的節點，所以此中序後繼節點一定不含子節點或者只含有一個右孩子，刪除此中序後繼節點就屬於上述 1,2 所述情況。圖一中 key 值為 10 的節點的直接中序後繼節點 為 11，節點 11 含有一個右孩子 12。

1 private Node getDirectPostNode(Node delNode) {//方法作用為得到待刪除節點的直接後繼節點 2 3 Node parentNode = delNode;//用來儲存待刪除節點的直接後繼節點的父親節點 4 Node direcrPostNode = delNode;//用來儲存待刪除節點的直接後繼節點 5 Node currentNode = delNode.rightChild; 6 while (currentNode != null) { 7 parentNode = direcrPostNode; 8 direcrPostNode = currentNode; 9 currentNode = currentNode.leftChild;10 }11 if (direcrPostNode != delNode.rightChild) {//從樹中刪除此直接後繼節點12 parentNode.leftChild = direcrPostNode.rightChild;13 direcrPostNode.rightChild = null;14 }15 return direcrPostNode;//返回此直接後繼節點16 17 }

　　　　b、將此後繼節點的 key、value 值賦給待刪除節點的 key，value值。(接情況二中省略號程式碼之後)

1 else { //要刪除的節點既有左孩子又有右孩子2 3 //思路：用待刪除節點右子樹中的key值最小節點的值來替代要刪除的節點的值,然後刪除右子樹中key值最小的節點4 //右子樹key最小的節點一定不含左子樹,所以刪除這個key最小的節點一定是屬於葉子節點或者只有右子樹的節點5 Node directPostNode = getDirectPostNode(currentNode);6 currentNode.key = directPostNode.key;7 currentNode.value = directPostNode.value;8 9 }

　　最後給出完整程式碼及簡單測試程式碼及測試結果：

　　

1 class Node { 2 int key; 3 int value; 4 Node leftChild; 5 Node rightChild; 6 7 public Node(int key, int value) { 8 this.key = key; 9 this.value = value; 10 } 11 12 public void displayNode() { 13 14 } 15 } 16 17 class Tree { 18 Node root; 19 20 public Node find(int key) { 21 Node currentNode = root; 22 while (currentNode != null && currentNode.key != key) { 23 if (key < currentNode.key) { 24 currentNode = currentNode.leftChild; 25 } else { 26 currentNode = currentNode.rightChild; 27 } 28 } 29 return currentNode; 30 } 31 32 public void insert(int key, int value) { 33 if (root == null) { 34 root = new Node(key, value); 35 return; 36 } 37 Node currentNode = root; 38 Node parentNode = root; 39 boolean isLeftChild = true; 40 while (currentNode != null) { 41 parentNode = currentNode; 42 if (key < currentNode.key) { 43 currentNode = currentNode.leftChild; 44 isLeftChild = true; 45 } else { 46 currentNode = currentNode.rightChild; 47 isLeftChild = false; 48 } 49 } 50 Node newNode = new Node(key, value); 51 if (isLeftChild) { 52 parentNode.leftChild = newNode; 53 } else { 54 parentNode.rightChild = newNode; 55 } 56 } 57 58 public boolean delete(int key) { 59 Node currentNode = root; 60 Node parentNode = root; 61 boolean isLeftChild = true; 62 while (currentNode != null && currentNode.key != key) { 63 parentNode = currentNode; 64 if (key < currentNode.key) { 65 currentNode = currentNode.leftChild; 66 isLeftChild = true; 67 } else { 68 currentNode = currentNode.rightChild; 69 isLeftChild = false; 70 } 71 } 72 if (currentNode == null) { 73 return false; 74 } 75 if (currentNode.leftChild == null && currentNode.rightChild == null) { 76 //要刪除的節點為葉子節點 77 if (currentNode == root) 78 root = null; 79 else if (isLeftChild) 80 parentNode.leftChild = null; 81 else 82 parentNode.rightChild = null; 83 } else if (currentNode.rightChild == null) {//要刪除的節點只有左孩子 84 if (currentNode == root) 85 root = currentNode.leftChild; 86 else if (isLeftChild) 87 parentNode.leftChild = currentNode.leftChild; 88 else 89 parentNode.rightChild = currentNode.leftChild; 90 } else if (currentNode.leftChild == null) {//要刪除的節點只有右孩子 91 if (currentNode == root) 92 root = currentNode.rightChild; 93 else if (isLeftChild) 94 parentNode.leftChild = currentNode.rightChild; 95 else 96 parentNode.rightChild = currentNode.rightChild; 97 } else { //要刪除的節點既有左孩子又有右孩子 98 //思路：用待刪除節點右子樹中的key值最小節點的值來替代要刪除的節點的值,然後刪除右子樹中key值最小的節點 99 //右子樹key最小的節點一定不含左子樹,所以刪除這個key最小的節點一定是屬於葉子節點或者只有右子樹的節點100 Node directPostNode = getDirectPostNode(currentNode);101 currentNode.key = directPostNode.key;102 currentNode.value = directPostNode.value;103 }104 return true;105 }106 107 private Node getDirectPostNode(Node delNode) {//方法作用為得到待刪除節點的直接後繼節點108 109 Node parentNode = delNode;//用來儲存待刪除節點的直接後繼節點的父親節點110 Node direcrPostNode = delNode;//用來儲存待刪除節點的直接後繼節點111 Node currentNode = delNode.rightChild;112 while (currentNode != null) {113 parentNode = direcrPostNode;114 direcrPostNode = currentNode;115 currentNode = currentNode.leftChild;116 }117 if (direcrPostNode != delNode.rightChild) {//從樹中刪除此直接後繼節點118 parentNode.leftChild = direcrPostNode.rightChild;119 direcrPostNode.rightChild = null;120 }121 return direcrPostNode;//返回此直接後繼節點122 123 }124 125 public void preOrder(Node rootNode) {126 if (rootNode != null) {127 System.out.println(rootNode.key + " " + rootNode.value);128 preOrder(rootNode.leftChild);129 preOrder(rootNode.rightChild);130 }131 }132 133 public void inOrder(Node rootNode) {134 if (rootNode != null) {135 inOrder(rootNode.leftChild);136 System.out.println("key: " + rootNode.key + " " + "value: " + rootNode.value);137 inOrder(rootNode.rightChild);138 }139 }140 141 public void postOrder(Node rootNode) {142 if (rootNode != null) {143 postOrder(rootNode.leftChild);144 postOrder(rootNode.rightChild);145 System.out.println(rootNode.key + " " + rootNode.value);146 }147 }　　　　 　　private void destroy(Node tree) { 　　 if (tree==null) 　　 return ; 　　 if (tree.left != null) 　　 destroy(tree.leftChild); 　　 if (tree.right != null) 　　 destroy(tree.rightChild); 　　 tree=null; 　　 }　　　　　　　　public void destory() {　　　　　　destory(root);　　　　}148 } 149 public class BinarySearchTreeApp { 150　　 public static void main(String[] args) {151　　　　　　 Tree tree = new Tree(); 152　　　　 tree.insert(6, 6);//插入操作,構造圖一所示的二叉樹 153　　　　 tree.insert(3, 3); 154 　　　　tree.insert(14, 14); 155　　　　 tree.insert(16, 16); 156　　　　 tree.insert(10, 10); 157　　　　 tree.insert(9, 9); 158 　　　　tree.insert(13, 13); 159　　　　 tree.insert(11, 11); 160 　　　　tree.insert(12, 12); 161 162　　 System.out.println("刪除前遍歷結果"); 163 　　　　tree.inOrder(tree.root);//中序遍歷操作 164 165　　 System.out.println("刪除節點10之後遍歷結果"); 166 　　　　tree.delete(10);//刪除操作 167 　　　　tree.inOrder(tree.root); 168 　　　　} 169 }

　　　　測試結果：

　　　　

二叉搜尋樹

我們可以用二叉搜尋樹中的插入操作構建一棵二叉搜尋樹

插入操作：

1. 從root節點開始

2. 如果root為空,root為插入值

迴圈:

3. 如果當前節點值大於插入值,找左節點

4. 如果當前節點值小於插入值,找右節點

二叉搜尋樹的虛擬碼：

Java實現：

public class BSTree {

Node<Integer> root = new Node<Integer>();

public BSTree(){

this.root = null;

}

//插入

public Node<Integer> insert (int key) {

Node<Integer> newNode = new Node<>(key);

Node<Integer> current = root;

Node<Integer> parent = null;

if (current == null) {

root = newNode;

return newNode;

}

while (true) {

parent = current;

if (key < current.data) {

current = current.left;

if (current == null) {

parent.left = newNode;

return newNode;

}

} else {

current = current.right;

if (current == null) {

parent.right = newNode;

return newNode;

}

}

}

}

//前序遍歷

public void PreOrder(Node node) {

if (node != null) {

System.out.print(node.data + " ");

PreOrder(node.left);

PreOrder(node.right);

}

}

}

測試類：

public class BSTreeTest {

public static void main(String[] args) {

BSTree tree =new BSTree();

tree.insert(30);

tree.insert(15);

tree.insert(41);

tree.insert(35);

tree.insert(50);

tree.PreOrder(tree.root);

}

}

IT技術人員面對面試、跳槽、升職等問題，如何快速成長，獲得大廠入門資格和升職加薪的籌碼？與大廠技術大牛面對面交流，解答你的疑惑。《從職場小白到技術總監成長之路：我的職場焦慮與救贖》活動連結http://mk1.top/2i2qad3