二元查找樹可以遞歸地定義如下，二叉查找樹或是空二叉樹，或是滿足下列性質的二元樹:
（1）若它的左子樹不為空，則其左子樹上任意結點的關鍵字的值都小於根結點關鍵字的值。
（2）若它的右子樹不為空，則其右子樹上任意結點的關鍵字的值都大於根節點關鍵字的值。
（3）它的左、右子樹本身又是一個二元查找樹。
從效能上來說如果二元尋找樹的所有非葉子結點的左右子樹的結點數目都保持差不多（平衡），那麼二元尋找樹的搜尋效能逼近二分查找；但它比連續記憶體空間的二分查找的優點是，改變二元查找樹結構（插入與刪除結點）不需要移動大段的記憶體數據，甚至通常是常數開銷。二元查找樹可以表示按順序序列排列的資料集合，因此二元查找樹也被稱為二元排序樹，並且同一個資料集合可以表示為不同的二元查找樹。二元查找樹的結點的資料結構定義為:
struct celltype{
records data;
celltype * lchild, * rchild;
}
typedef celltype * BST;在Java中，節點的資料結構定義如下:
package wx.algorithm.search.bst;
/**
* Created by apple on 16/7/29.
*/
/**
* @function 二叉搜索树中的节点
*/
public class Node {
//存放节点数据
int data;
//指向左子节点
Node left;
//指向右子节点
Node right;
/**
* @function 默认构造函数
* @param data 节点数据
*/
public Node(int data) {
this.data = data;
left = null;
right = null;
}
}查找
而二叉查找樹的查找過程為從根結點開始，如果查詢的關鍵字與結點的關鍵字相等，那麼就命中；否則，如果查詢關鍵字比結點關鍵字小，就進入左兒子；如果比結點關鍵字大，就進入右兒子；如果左兒子或右兒子的指針為空，則報告找不到相應的關鍵字。
BST Search(keytype k, BST F){
//在F所指的二叉查找树中查找关键字为k的记录。若成功，则返回响应结点的指针，否则返回空
if(F == NULL) //查找失败
return NULL;
else if(k == F -> data.key){ //查找成功
return F;
}
else if (k < F -> data.key){ //查找左子树
return Search(k,F -> lchild);
}
else if (k > F -> data.key){ //查找右子树
return Search(k,F -> rchild);
}
}插入
把一個新的記錄R插入到二元尋找樹，應該保證在插入之後不破壞二元尋找樹的結構性質。因此，為了執行插入操作首先應該查找R所在的位置。查找時，仍然採用上述的遞歸演算法。若查找失敗，則把包含R的結點插在具有空子樹位置，若查找成功，則不執行插入，操作結束。
void Insert(records R, BST &F){
//在F所指的二叉查找树中插入一个新纪录R
if(F == NULL){
F = new celltype;
F -> data = R;
F -> lchild = NULL;
F -> rchild = NULL;
}
else if (R.key < F -> data.key){
Insert(R,F -> lchild);
}else if(R.key > F -> data.key){
Insert(R,F -> rchild);
}
//如果 R.key == F -> data.key 则返回
}刪除
刪除葉節點
刪除只有一個子節點的內部節點
刪除有兩個子節點的內部節點
如果我們進行簡單的替換，那麼可能碰到如下情況:
#因此我們要在子樹中選擇一個合適的替換節點，替換節點一般來說會是右子樹中的最小的節點:
Java 實作
BinarySearchTree的Java版本程式碼參考BinarySearchTree:
package wx.algorithm.search.bst;
/**
* Created by apple on 16/7/29.
*/
/**
* @function 二叉搜索树的示范代码
*/
public class BinarySearchTree {
//指向二叉搜索树的根节点
private Node root;
//默认构造函数
public BinarySearchTree() {
this.root = null;
}
/**
* @param id 待查找的值
* @return
* @function 默认搜索函数
*/
public boolean find(int id) {
//从根节点开始查询
Node current = root;
//当节点不为空
while (current != null) {
//是否已经查询到
if (current.data == id) {
return true;
} else if (current.data > id) {
//查询左子树
current = current.left;
} else {
//查询右子树
current = current.right;
}
}
return false;
}
/**
* @param id
* @function 插入某个节点
*/
public void insert(int id) {
//创建一个新的节点
Node newNode = new Node(id);
//判断根节点是否为空
if (root == null) {
root = newNode;
return;
}
//设置current指针指向当前根节点
Node current = root;
//设置父节点为空
Node parent = null;
//遍历直到找到第一个插入点
while (true) {
//先将父节点设置为当前节点
parent = current;
//如果小于当前节点的值
if (id < current.data) {
//移向左节点
current = current.left;
//如果当前节点不为空,则继续向下一层搜索
if (current == null) {
parent.left = newNode;
return;
}
} else {
//否则移向右节点
current = current.right;
//如果当前节点不为空,则继续向下一层搜索
if (current == null) {
parent.right = newNode;
return;
}
}
}
}
/**
* @param id
* @return
* @function 删除树中的某个元素
*/
public boolean delete(int id) {
Node parent = root;
Node current = root;
//记录被找到的节点是父节点的左子节点还是右子节点
boolean isLeftChild = false;
//循环直到找到目标节点的位置,否则报错
while (current.data != id) {
parent = current;
if (current.data > id) {
isLeftChild = true;
current = current.left;
} else {
isLeftChild = false;
current = current.right;
}
if (current == null) {
return false;
}
}
//如果待删除的节点没有任何子节点
//直接将该节点的原本指向该节点的指针设置为null
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) {
//寻找右子树中的最小值
Node successor = getSuccessor(current);
if (current == root) {
root = successor;
} else if (isLeftChild) {
parent.left = successor;
} else {
parent.right = successor;
}
successor.left = current.left;
}
return true;
}
/**
* @param deleleNode
* @return
* @function 在树种查找最合适的节点
*/
private Node getSuccessor(Node deleleNode) {
Node successsor = null;
Node successsorParent = null;
Node current = deleleNode.right;
while (current != null) {
successsorParent = successsor;
successsor = current;
current = current.left;
}
if (successsor != deleleNode.right) {
successsorParent.left = successsor.right;
successsor.right = deleleNode.right;
}
return successsor;
}
/**
* @function 以中根顺序遍历树
*/
public void display() {
display(root);
}
private void display(Node node) {
//判断当前节点是否为空
if (node != null) {
//首先展示左子树
display(node.left);
//然后展示当前根节点的值
System.out.print(" " + node.data);
//最后展示右子树的值
display(node.right);
}
}
}測試函數:
package wx.algorithm.search.bst;
import org.junit.Before;
import org.junit.Test;
/**
* Created by apple on 16/7/30.
*/
public class BinarySearchTreeTest {
BinarySearchTree binarySearchTree;
@Before
public void setUp() {
binarySearchTree = new BinarySearchTree();
binarySearchTree.insert(3);
binarySearchTree.insert(8);
binarySearchTree.insert(1);
binarySearchTree.insert(4);
binarySearchTree.insert(6);
binarySearchTree.insert(2);
binarySearchTree.insert(10);
binarySearchTree.insert(9);
binarySearchTree.insert(20);
binarySearchTree.insert(25);
binarySearchTree.insert(15);
binarySearchTree.insert(16);
System.out.println("原始的树 : ");
binarySearchTree.display();
System.out.println("");
}
@Test
public void testFind() {
System.out.println("判断4是否存在树中 : " + binarySearchTree.find(4));
}
@Test
public void testInsert() {
}
@Test
public void testDelete() {
System.out.println("删除值为2的节点 : " + binarySearchTree.delete(2));
binarySearchTree.display();
System.out.println("\n 删除有一个子节点值为4的节点 : " + binarySearchTree.delete(4));
binarySearchTree.display();
System.out.println("\n 删除有两个子节点的值为10的节点 : " + binarySearchTree.delete(10));
binarySearchTree.display();
}
}以上是Java實作二元搜尋樹演算法的程式碼詳解（圖）的詳細內容。更多資訊請關注PHP中文網其他相關文章！
JWT能否實現動態權限變更？與Session機制有何區別？Apr 19, 2025 pm 06:12 PM關於JWT和Session的困惑與解答許多初學者在學習JWT和Session時，常常會對其本質和適用場景感到困惑。本文將圍繞J...
Windows Server 2019防火牆如何正確配置才能支持WebSocket通信？Apr 19, 2025 pm 06:09 PMWindowsServer2019防火牆與WebSocket通信問題詳解在使用SpringBoot開發的Jar程序部署於WindowsServer2019...
Java單線程下的指令重排序會影響System.out.println的輸出順序嗎？Apr 19, 2025 pm 06:00 PMJava單線程下的指令重排序與輸出順序在Java編程中，指令重排序是一個常見的優化技術，用於提高程序的執行效�...
IntelliJ IDEA是如何通過JavaAgent技術識別Spring Boot項目的端口號的？Apr 19, 2025 pm 05:57 PMIntelliJIDEA如何識別SpringBoot項目的端口號？在使用IntelliJIDEAUltimate版本時，啟動Spring...
如何通過 OAuth2.0 的 scope 機制精細控制 access_token 的接口訪問權限？Apr 19, 2025 pm 05:54 PM通過OAuth2.0的access_token如何精細控制接口訪問權限？在現代應用開發中，OAuth2.0...
RuoYi框架如何實現Bean依賴注入而無需顯式編寫DataSource實現類？Apr 19, 2025 pm 05:51 PM深入剖析RuoYi框架的Bean依賴注入機制：無需顯式實現類RuoYi框架是一個流行的Java前後端分離框架，其簡潔的代碼...
熱AI工具
Undresser.AI Undress
人工智慧驅動的應用程序，用於創建逼真的裸體照片
AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。
Undress AI Tool
免費脫衣圖片
Clothoff.io
AI脫衣器
AI Hentai Generator
免費產生 AI 無盡。
熱門文章
熱工具
MantisBT
Mantis是一個易於部署的基於Web的缺陷追蹤工具，用於幫助產品缺陷追蹤。它需要PHP、MySQL和一個Web伺服器。請查看我們的演示和託管服務。
PhpStorm Mac 版本
最新（2018.2.1 ）專業的PHP整合開發工具
Dreamweaver CS6
視覺化網頁開發工具
SecLists
SecLists是最終安全測試人員的伙伴。它是一個包含各種類型清單的集合，這些清單在安全評估過程中經常使用，而且都在一個地方。 SecLists透過方便地提供安全測試人員可能需要的所有列表，幫助提高安全測試的效率和生產力。清單類型包括使用者名稱、密碼、URL、模糊測試有效載荷、敏感資料模式、Web shell等等。測試人員只需將此儲存庫拉到新的測試機上，他就可以存取所需的每種類型的清單。
SublimeText3漢化版
中文版，非常好用
