java實現(xiàn) 二叉搜索樹功能
一、概念
二叉搜索樹也成二叉排序樹，它有這么一個特點，某個節(jié)點，若其有兩個子節(jié)點，則一定滿足，左子節(jié)點值一定小于該節(jié)點值，右子節(jié)點值一定大于該節(jié)點值，對于非基本類型的比較，可以實現(xiàn)Comparator接口，在本文中為了方便，采用了int類型數(shù)據(jù)進行操作。
要想實現(xiàn)一顆二叉樹，肯定得從它的增加說起，只有把樹構建出來了，才能使用其他操作。
二、二叉搜索樹構建
談起二叉樹的增加，肯定先得構建一個表示節(jié)點的類，該節(jié)點的類，有這么幾個屬性，節(jié)點的值，節(jié)點的父節(jié)點、左節(jié)點、右節(jié)點這四個屬性，代碼如下
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);
}
}
這里采用的是內(nèi)部類的寫法，構建完節(jié)點值后，再對整棵樹去構建，一棵樹，先得有根節(jié)點，再能延伸到余下子節(jié)點，那在這棵樹里，也有一些屬性，比如基本的根節(jié)點root,樹中元素大小size，這兩個屬性，如果采用了泛型，可能還得增加Comparator屬性，或提供其一個默認實現(xiàn)。具體代碼如下
public class SearchBinaryTree {
private Node root;
private int size;
public SearchBinaryTree() {
super();
}
}
三、增加
當要進行添加元素的時候，得考慮根節(jié)點的初始化，一般情況有兩種、當該類的構造函數(shù)一初始化就對根節(jié)點root進行初始化，第二種、在進行第一次添加元素的時候，對根節(jié)點進行添加。理論上兩個都可以行得通，但通常采用的是第二種懶加載形式。
在進行添加元素的時候，有這樣幾種情況需要考慮
一、添加時判斷root是否初始化，若沒初始化，則初始化，將該值賦給根節(jié)點，size加一。
二、因為二叉樹搜索樹滿足根節(jié)點值大于左節(jié)點，小于右節(jié)點，需要將插入的值，先同根節(jié)點比較，若大，則往右子樹中進行查找，若小，則往左子樹中進行查找。直到某個子節(jié)點。
這里的插入實現(xiàn)，可以采用兩種，一、遞歸、二、迭代(即通過while循環(huán)模式)。
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;
}
/**
* 獲取要插入的節(jié)點的父節(jié)點，該父節(jié)點滿足以下幾種狀態(tài)之一
* 1、父節(jié)點為子節(jié)點
* 2、插入節(jié)點值比父節(jié)點小，但父節(jié)點沒有左子節(jié)點
* 3、插入節(jié)點值比父節(jié)點大，但父節(jié)點沒有右子節(jié)點
* 4、插入節(jié)點值和父節(jié)點相等。
* 5、父節(jié)點為空
* 如果滿足以上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;
}
// 該節(jié)點是葉子節(jié)點，則返回
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;
}
}
使用遞歸，先找到遞歸的結束點，再去把整個問題化為子問題，在上述代碼里，邏輯大致是這樣的，先判斷根節(jié)點有沒有初始化，沒初始化則初始化，完成后返回，之后通過一個函數(shù)去獲取適配的節(jié)點。之后進行插入值。
3.2、迭代版本
public boolean put(int val){
return putVal(root,val);
}
private boolean putVal(Node node,int val){
if(node == null){// 初始化根節(jié)點
node = new Node(val);
root = node;
size++;
return true;
}
Node temp = node;
Node p;
int t;
/**
* 通過do while循環(huán)迭代獲取最佳節(jié)點，
*/
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;
}
原理其實和遞歸一樣，都是獲取最佳節(jié)點，在該節(jié)點上進行操作。
論起性能，肯定迭代版本最佳，所以一般情況下，都是選擇迭代版本進行操作數(shù)據(jù)。
四、刪除
可以說在二叉搜索樹的操作中，刪除是最復雜的，要考慮的情況也相對多，在常規(guī)思路中，刪除二叉搜索樹的某一個節(jié)點，肯定會想到以下四種情況,
1、要刪除的節(jié)點沒有左右子節(jié)點，如上圖的D、E、G節(jié)點
2、要刪除的節(jié)點只有左子節(jié)點，如B節(jié)點
3、要刪除的節(jié)點只有右子節(jié)點，如F節(jié)點
4、要刪除的節(jié)點既有左子節(jié)點，又有右子節(jié)點，如 A、C節(jié)點
對于前面三種情況，可以說是比較簡單，第四種復雜了。下面先來分析第一種
若是這種情況，比如 刪除D節(jié)點，則可以將B節(jié)點的左子節(jié)點設置為null，若刪除G節(jié)點，則可將F節(jié)點的右子節(jié)點設置為null。具體要設置哪一邊，看刪除的節(jié)點位于哪一邊。
第二種，刪除B節(jié)點，則只需將A節(jié)點的左節(jié)點設置成D節(jié)點，將D節(jié)點的父節(jié)點設置成A即可。具體設置哪一邊，也是看刪除的節(jié)點位于父節(jié)點的哪一邊。
第三種，同第二種。
第四種，也就是之前說的有點復雜，比如要刪除C節(jié)點，將F節(jié)點的父節(jié)點設置成A節(jié)點，F(xiàn)節(jié)點左節(jié)點設置成E節(jié)點，將A的右節(jié)點設置成F，E的父節(jié)點設置F節(jié)點(也就是將F節(jié)點替換C節(jié)點)，還有一種，直接將E節(jié)點替換C節(jié)點。那采用哪一種呢，如果刪除節(jié)點為根節(jié)點，又該怎么刪除？
對于第四種情況，可以這樣想，找到C或者A節(jié)點的后繼節(jié)點，刪除后繼節(jié)點，且將后繼節(jié)點的值設置為C或A節(jié)點的值。先來補充下后繼節(jié)點的概念。
一個節(jié)點在整棵樹中的后繼節(jié)點必滿足，大于該節(jié)點值得所有節(jié)點集合中值最小的那個節(jié)點，即為后繼節(jié)點，當然，也有可能不存在后繼節(jié)點。
但是對于第四種情況，后繼節(jié)點一定存在，且一定在其右子樹中，而且還滿足，只有一個子節(jié)點或者沒有子節(jié)點兩者情況之一。具體原因可以這樣想，因為后繼節(jié)點要比C節(jié)點大，又因為C節(jié)點左右子節(jié)一定存在，所以一定存在右子樹中的左子節(jié)點中。就比如C的后繼節(jié)點是F，A的后繼節(jié)點是E。
有了以上分析，那么實現(xiàn)也比較簡單了，代碼如下
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;
//以下所有父節(jié)點為空的情況，則表明刪除的節(jié)點是根節(jié)點
if(leftChild == null && rightChild == null){//沒有子節(jié)點
if(parent != null){
if(parent.leftChild == node){
parent.leftChild = null;
}else if(parent.rightChild == node){
parent.rightChild = null;
}
}else{//不存在父節(jié)點，則表明刪除節(jié)點為根節(jié)點
root = null;
}
node = null;
return true;
}else if(leftChild == null && rightChild != null){// 只有右節(jié)點
if(parent != null && parent.val > val){// 存在父節(jié)點，且node位置為父節(jié)點的左邊
parent.leftChild = rightChild;
}else if(parent != null && parent.val < val){// 存在父節(jié)點，且node位置為父節(jié)點的右邊
parent.rightChild = rightChild;
}else{
root = rightChild;
}
node = null;
return true;
}else if(leftChild != null && rightChild == null){// 只有左節(jié)點
if(parent != null && parent.val > val){// 存在父節(jié)點，且node位置為父節(jié)點的左邊
parent.leftChild = leftChild;
}else if(parent != null && parent.val < val){// 存在父節(jié)點，且node位置為父節(jié)點的右邊
parent.rightChild = leftChild;
}else{
root = leftChild;
}
return true;
}else if(leftChild != null && rightChild != null){// 兩個子節(jié)點都存在
Node successor = getSuccessor(node);// 這種情況，一定存在后繼節(jié)點
int temp = successor.val;
boolean delete = delete(temp);
if(delete){
node.val = temp;
}
successor = null;
return true;
}
return false;
}
/**
* 找到node節(jié)點的后繼節(jié)點
* 1、先判斷該節(jié)點有沒有右子樹，如果有，則從右節(jié)點的左子樹中尋找后繼節(jié)點，沒有則進行下一步
* 2、查找該節(jié)點的父節(jié)點，若該父節(jié)點的右節(jié)點等于該節(jié)點，則繼續(xù)尋找父節(jié)點，
* 直至父節(jié)點為Null或找到不等于該節(jié)點的右節(jié)點。
* 理由，后繼節(jié)點一定比該節(jié)點大，若存在右子樹，則后繼節(jié)點一定存在右子樹中，這是第一步的理由
* 若不存在右子樹，則也可能存在該節(jié)點的某個祖父節(jié)點(即該節(jié)點的父節(jié)點，或更上層父節(jié)點)的右子樹中，
* 對其迭代查找，若有，則返回該節(jié)點，沒有則返回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;
}
具體邏輯，看上面分析，這里不作文字敘述了，
除了這種實現(xiàn)，在算法導論書中，提供了另外一種實現(xiàn)。
public boolean remove(int val){
Node node = getNode(val);
if(node == null){
return false;
}
if(node.leftChild == null){// 1、左節(jié)點不存在，右節(jié)點可能存在，包含兩種情況 ，兩個節(jié)點都不存在和只存在右節(jié)點
transplant(node, node.rightChild);
}else if(node.rightChild == null){//2、左孩子存在，右節(jié)點不存在
transplant(node, node.leftChild);
}else{// 3、兩個節(jié)點都存在
Node successor = getSuccessor(node);// 得到node后繼節(jié)點
if(successor.parent != node){// 后繼節(jié)點存在node的右子樹中。
transplant(successor, successor.rightChild);// 用后繼節(jié)點的右子節(jié)點替換該后繼節(jié)點
successor.rightChild = node.rightChild;// 將node節(jié)點的右子樹賦給后繼節(jié)點的右節(jié)點，即類似后繼與node節(jié)點調(diào)換位置
successor.rightChild.parent = successor;// 接著上一步 給接過來的右節(jié)點的父引用復制
}
transplant(node, successor);
successor.leftChild = node.leftChild;
successor.leftChild.parent = successor;
}
return true;
}
/**
* 將child節(jié)點替換node節(jié)點
* @param root 根節(jié)點
* @param node 要刪除的節(jié)點
* @param child node節(jié)點的子節(jié)點
*/
private void transplant(Node node,Node child){
/**
* 1、先判斷 node是否存在父節(jié)點
* 1、不存在，則child替換為根節(jié)點
* 2、存在，則繼續(xù)下一步
* 2、判斷node節(jié)點是父節(jié)點的那個孩子(即判斷出 node是右節(jié)點還是左節(jié)點)，
* 得出結果后，將child節(jié)點替換node節(jié)點 ，即若node節(jié)點是左節(jié)點 則child替換后 也為左節(jié)點，否則為右節(jié)點
* 3、將node節(jié)點的父節(jié)點置為child節(jié)點的父節(jié)點
*/
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;
}
}
五、查找
查找也比較簡單，其實在增加的時候，已經(jīng)實現(xiàn)了。實際情況中，這部分可以抽出來單獨方法。代碼如下
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);// 位置在中間，則中序，若在前面，則為先序，否則為后續(xù)
print(root.rightChild);
}
}
總結
以上所述是小編給大家介紹的java實現(xiàn) 二叉搜索樹功能，希望對大家有所幫助，如果大家有任何疑問歡迎給我留言，小編會及時回復大家的！
相關文章
本文給大家總結了UML類圖中幾種比較常用的關系小總結，需要的朋友可以參考下2015-10-10
spring?retry實現(xiàn)方法請求重試的使用步驟
這篇文章主要介紹了spring?retry實現(xiàn)方法請求重試及使用步驟，本文分步驟通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-07-07
這篇文章主要介紹了Java通過反射,動態(tài)修改注解的某個屬性值操作，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-07-07
Elasticsearch是一個分布式的RESTful搜索和分析引擎,可讓您輕松地大規(guī)模存儲,搜索和分析,這篇文章主要給大家介紹了關于Elasticsearch(ES)多種查詢方式的相關資料,需要的朋友可以參考下2023-09-09
大家好，本篇文章主要講的是Java序列化和反序列化示例介紹，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽2022-01-01
這篇文章主要介紹了Java錯誤:進行語法分析時已到達文件結尾的解決方案,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
解決java.lang.Error: Unresolved compilation pro
這篇文章主要介紹了解決java.lang.Error: Unresolved compilation problems:問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-03-03
這篇文章主要給大家介紹了關于java類的定義與使用的相關資料,類的方法是用來定義類的行為,在方法中通過操作類的成員變量、編寫業(yè)務邏輯、返回 結果等實現(xiàn)類的業(yè)務行為,需要的朋友可以參考下2023-11-11
這篇文章主要介紹了使用Spring底層組件實現(xiàn)Aware接口,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-07-07
java使用JDBC動態(tài)創(chuàng)建數(shù)據(jù)表及SQL預處理的方法
這篇文章主要介紹了java使用JDBC動態(tài)創(chuàng)建數(shù)據(jù)表及SQL預處理的方法,涉及JDBC操作數(shù)據(jù)庫的連接、創(chuàng)建表、添加數(shù)據(jù)、查詢等相關實現(xiàn)技巧,需要的朋友可以參考下2017-08-08