一、樹 & 二叉樹
樹 是由節點和邊構成，儲存元素的集合。節點分根節點、父節點和子節點的概念。
二叉樹binary tree ，則加了“二叉”（binary），意思是在樹中作區分。每個節點至多有兩個子（child）,left child & right child。二叉樹在很多例子中使用，比如二叉樹表示算術表達式。
二、二叉搜索樹 BST 顧名思義，二叉樹上又加了個搜索的限制。其要求：每個節點比其左子樹元素大，比其右子樹元素小。
三、BST Java實現
直接上代碼，對應代碼分享在?Github?主頁
package org.algorithm.tree;
/** Copyright [2015] [Jeff Lee]** Licensed under the Apache License, Version 2.0 (the "License");* you may not use this file except in compliance with the License.* You may obtain a copy of the License at** http://www.apache.org/licenses/LICENSE-2.0** Unless required by applicable law or agreed to in writing, software* distributed under the License is distributed on an "AS IS" BASIS,* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.* See the License for the specific language governing permissions and* limitations under the License.*//*** 二叉搜索樹(BST)實現** Created by bysocket on 16/7/7.*/
public class BinarySearchTree {/*** 根節點*/public static TreeNode root;public BinarySearchTree() {this.root = null;}/*** 查找* 樹深(N) O(lgN)* 1. 從root節點開始* 2. 比當前節點值小,則找其左節點* 3. 比當前節點值大,則找其右節點* 4. 與當前節點值相等,查找到返回TRUE* 5. 查找完畢未找到,* @param key* @return*/public TreeNode search (int key) {TreeNode current = root;while (current != null&& key != current.value) {if (key < current.value )current = current.left;elsecurrent = current.right;}return current;}/*** 插入* 1. 從root節點開始* 2. 如果root為空,root為插入值* 循環:* 3. 如果當前節點值大于插入值,找左節點* 4. 如果當前節點值小于插入值,找右節點* @param key* @return*/public TreeNode insert (int key) {// 新增節點TreeNode newNode = new TreeNode(key);// 當前節點TreeNode current = root;// 上個節點TreeNode parent = null;// 如果根節點為空if (current == null) {root = newNode;return newNode;}while (true) {parent = current;if (key < current.value) {current = current.left;if (current == null) {parent.left = newNode;return newNode;}} else {current = current.right;if (current == null) {parent.right = newNode;return newNode;}}}}/*** 刪除節點* 1.找到刪除節點* 2.如果刪除節點左節點為空 , 右節點也為空;* 3.如果刪除節點只有一個子節點 右節點 或者 左節點* 4.如果刪除節點左右子節點都不為空* @param key* @return*/public TreeNode delete (int key) {TreeNode parent = root;TreeNode current = root;boolean isLeftChild = false;// 找到刪除節點 及 是否在左子樹while (current.value != key) {parent = current;if (current.value > key) {isLeftChild = true;current = current.left;} else {isLeftChild = false;current = current.right;}if (current == null) {return current;}}// 如果刪除節點左節點為空 , 右節點也為空if (current.left == null && current.right == null) {if (current == root) {root = null;}// 在左子樹if (isLeftChild == true) {parent.left = null;} else {parent.right = null;}}// 如果刪除節點只有一個子節點 右節點 或者 左節點else if (current.right == null) {if (current == root) {root = current.left;} else if (isLeftChild) {parent.left = current.left;} else {parent.right = current.left;}}else if (current.left == null) {if (current == root) {root = current.right;} else if (isLeftChild) {parent.left = current.right;} else {parent.right = current.right;}}// 如果刪除節點左右子節點都不為空else if (current.left != null && current.right != null) {// 找到刪除節點的后繼者TreeNode successor = getDeleteSuccessor(current);if (current == root) {root = successor;} else if (isLeftChild) {parent.left = successor;} else {parent.right = successor;}successor.left = current.left;}return current;}/*** 獲取刪除節點的后繼者* 刪除節點的后繼者是在其右節點樹種最小的節點* @param deleteNode* @return*/public TreeNode getDeleteSuccessor(TreeNode deleteNode) {// 后繼者TreeNode successor = null;TreeNode successorParent = null;TreeNode current = deleteNode.right;while (current != null) {successorParent = successor;successor = current;current = current.left;}// 檢查后繼者(不可能有左節點樹)是否有右節點樹// 如果它有右節點樹,則替換后繼者位置,加到后繼者父親節點的左節點.if (successor != deleteNode.right) {successorParent.left = successor.right;successor.right = deleteNode.right;}return successor;}public void toString(TreeNode root) {if (root != null) {toString(root.left);System.out.print("value = " + root.value + " -> ");toString(root.right);}}
}/*** 節點*/
class TreeNode {/*** 節點值*/int value;/*** 左節點*/TreeNode left;/*** 右節點*/TreeNode right;public TreeNode(int value) {this.value = value;left = null;right = null;}
}
1.?節點數據結構
代碼如下：
/*** 節點*/
class TreeNode {/*** 節點值*/int value;/*** 左節點*/TreeNode left;/*** 右節點*/TreeNode right;public TreeNode(int value) {this.value = value;left = null;right = null;}
}
?
2. 插入
/*** 插入* 1. 從root節點開始* 2. 如果root為空,root為插入值* 循環:* 3. 如果當前節點值大于插入值,找左節點* 4. 如果當前節點值小于插入值,找右節點* @param key* @return*/public TreeNode insert (int key) {// 新增節點TreeNode newNode = new TreeNode(key);// 當前節點TreeNode current = root;// 上個節點TreeNode parent = null;// 如果根節點為空if (current == null) {root = newNode;return newNode;}while (true) {parent = current;if (key < current.value) {current = current.left;if (current == null) {parent.left = newNode;return newNode;}} else {current = current.right;if (current == null) {parent.right = newNode;return newNode;}}}}
?
3.查找
其算法復雜度 :?O(lgN),樹深(N)。如圖查找邏輯：
/*** 查找* 樹深(N) O(lgN)* 1. 從root節點開始* 2. 比當前節點值小,則找其左節點* 3. 比當前節點值大,則找其右節點* 4. 與當前節點值相等,查找到返回TRUE* 5. 查找完畢未找到,* @param key* @return*/public TreeNode search (int key) {TreeNode current = root;while (current != null&& key != current.value) {if (key < current.value )current = current.left;elsecurrent = current.right;}return current;}
4. 刪除
結果為：
?
案例測試代碼如下，BinarySearchTreeTest.java
package org.algorithm.tree;
/** Copyright [2015] [Jeff Lee]** Licensed under the Apache License, Version 2.0 (the "License");* you may not use this file except in compliance with the License.* You may obtain a copy of the License at** http://www.apache.org/licenses/LICENSE-2.0** Unless required by applicable law or agreed to in writing, software* distributed under the License is distributed on an "AS IS" BASIS,* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.* See the License for the specific language governing permissions and* limitations under the License.*//*** 二叉搜索樹(BST)測試案例 {@link BinarySearchTree}** Created by bysocket on 16/7/10.*/
public class BinarySearchTreeTest {public static void main(String[] args) {BinarySearchTree b = new BinarySearchTree();b.insert(3);b.insert(8);b.insert(1);b.insert(4);b.insert(6);b.insert(2);b.insert(10);b.insert(9);b.insert(20);b.insert(25);// 打印二叉樹b.toString(b.root);System.out.println();// 是否存在節點值10TreeNode node01 = b.search(10);System.out.println("是否存在節點值為10 => " + node01.value);// 是否存在節點值11TreeNode node02 = b.search(11);System.out.println("是否存在節點值為11 => " + node02);// 刪除節點8TreeNode node03 = b.delete(8);System.out.println("刪除節點8 => " + node03.value);b.toString(b.root);}
}
運行結果如下：
value = 1 -> value = 2 -> value = 3 -> value = 4 -> value = 6 -> value = 8 -> value = 9 -> value = 10 -> value = 20 -> value = 25 ->
是否存在節點值為10 => 10
是否存在節點值為11 => null
刪除節點8 => 8
value = 1 -> value = 2 -> value = 3 -> value = 4 -> value = 6 -> value = 9 -> value = 10 -> value = 20 -> value = 25 ->
四、小結
與偶爾吃一碗“老壇酸菜牛肉面”一樣的味道，品味一個算法，比如BST，的時候，總是那種說不出的味道。
樹，二叉樹的概念
BST算法
相關代碼分享在?Github?主頁
轉載自 并發編程網 – ifeve.com本文鏈接地址: ? Java實現 二叉搜索樹算法（BST）
總結
以上是生活随笔 為你收集整理的Java实现 二叉搜索树算法（BST） 的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網站內容還不錯，歡迎將生活随笔 推薦給好友。
