本篇內(nèi)容介紹了“二叉查找樹的概念和實(shí)現(xiàn)方法”的有關(guān)知識，在實(shí)際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！
讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長期合作伙伴，公司提供的服務(wù)項(xiàng)目有：主機(jī)域名、網(wǎng)絡(luò)空間、營銷軟件、網(wǎng)站建設(shè)、金水網(wǎng)站維護(hù)、網(wǎng)站推廣。
二叉查找樹是將一組無序的數(shù)據(jù)構(gòu)建成一顆有序數(shù)據(jù)的樹，其設(shè)計(jì)思想與二分法類似。很好的提高了海量數(shù)據(jù)查找效率，使得由從頭遍歷到尾的方式轉(zhuǎn)為二分查找的方式，時(shí)間復(fù)雜度從O(n)降低為O(log(n))。
結(jié)點(diǎn)：樹上的每個元素。
根結(jié)點(diǎn)：沒有父結(jié)點(diǎn)的結(jié)點(diǎn)。
父結(jié)點(diǎn)：結(jié)點(diǎn)的上一級結(jié)點(diǎn)。
子結(jié)點(diǎn)：結(jié)點(diǎn)的下一級結(jié)點(diǎn)。
葉子結(jié)點(diǎn)：沒有子結(jié)點(diǎn)的結(jié)點(diǎn)。
兄弟結(jié)點(diǎn)：擁有同一父結(jié)點(diǎn)的相鄰結(jié)點(diǎn)。
結(jié)點(diǎn)的度：一個結(jié)點(diǎn)中擁有子結(jié)點(diǎn)的個數(shù)。
樹的度：樹上最大結(jié)點(diǎn)的度。
結(jié)點(diǎn)的層次：以根結(jié)點(diǎn)為1，每深入一個子結(jié)點(diǎn)層次加1。
樹的高度：樹中最大的結(jié)點(diǎn)的層次。
左子樹所有的結(jié)點(diǎn)值均小于，等于根結(jié)點(diǎn)值或?yàn)榭铡?/p>
左子樹所有的結(jié)點(diǎn)值均大于，等于根結(jié)點(diǎn)值或?yàn)榭铡?/p>
左、右子樹也分別為二叉排序樹。
沒有鍵值相等的結(jié)點(diǎn)。
構(gòu)建二叉查找樹，主要把握幾條原則，小于當(dāng)前結(jié)點(diǎn)的在左邊，大于的在右邊，相等的不予處理。但是情況下結(jié)合實(shí)際業(yè)務(wù)需求，也可在相等時(shí)放在左結(jié)點(diǎn)或右結(jié)點(diǎn)，但是必須統(tǒng)一規(guī)則，不能左右都存在相等的。 創(chuàng)建結(jié)點(diǎn)對象：
重慶分公司
重慶分公司
package com.ytao.bst;
/**
* Created by YANGTAO on 2019/11/3 0003.
*/
public class Node {
private Integer value;
private Node leftChildren;
private Node rightChildren;
public Integer getValue() {
return value;
}
public void setValue(Integer value) {
this.value = value;
}
public Node getLeftChildren() {
return leftChildren;
}
public void setLeftChildren(Node leftChildren) {
this.leftChildren = leftChildren;
}
public Node getRightChildren() {
return rightChildren;
}
public void setRightChildren(Node rightChildren) {
this.rightChildren = rightChildren;
}
public Node(Integer value) {
this.value = value;
}
}創(chuàng)建樹的實(shí)現(xiàn)：
package com.ytao.bst;
/**
* Created by YANGTAO on 2019/11/3 0003.
*/
public class BuildBST {
private Node rootNode = null;
public Node build(int[] vals){
// 遍歷所有數(shù)據(jù)，每次都需從根結(jié)點(diǎn)開始尋找左或右子節(jié)點(diǎn)為空的位置添加
for (int val : vals) {
this.assemble(rootNode, val);
}
return rootNode;
}
private void assemble(Node node, int val){
// 創(chuàng)建根結(jié)點(diǎn)
if (node == null){
rootNode = new Node(val);
}else{
// 根據(jù)左小右大特性判斷
if (val < node.getValue()){
Node leftNode = node.getLeftChildren();
// 如果左子結(jié)點(diǎn)為空，就添加為當(dāng)前結(jié)點(diǎn)的左結(jié)點(diǎn)，否則繼續(xù)遞歸下去
if (leftNode == null){
node.setLeftChildren(new Node(val));
}else{
this.assemble(node.getLeftChildren(), val);
}
}else{
Node rightNode = node.getRightChildren();
// 如果右子結(jié)點(diǎn)為空，就添加為當(dāng)前結(jié)點(diǎn)的右結(jié)點(diǎn)，否則繼續(xù)遞歸下去
if (rightNode == null){
node.setRightChildren(new Node(val));
}else{
this.assemble(rightNode, val);
}
}
}
}
}使用[7,5,9,2,11,6]測試是否滿足我們創(chuàng)建樹的要求：
public static void main(String[] args) {
int[] vals = {7,5,9,2,11,6};
Node node = new BuildBST().build(vals);
System.out.println(new Gson().toJson(node));
}測試結(jié)果滿足我們要求
{
"value": 7,
"leftChildren": {
"value": 5,
"leftChildren": {
"value": 2
},
"rightChildren": {
"value": 6
}
},
"rightChildren": {
"value": 9,
"rightChildren": {
"value": 11
}
}
}假設(shè)從一百萬個數(shù)字中獲取值為88的數(shù)據(jù)，如果我們使用遍歷的方式，最糟的情況就是排在第一百萬個位置的時(shí)候，需要我們遍歷一百萬次才能獲取到數(shù)據(jù)，這就是我們最不想遇到的情況。這時(shí)將一百萬個數(shù)據(jù)構(gòu)建成二叉查找樹，我們就可通過樹快速找到我們想要的數(shù)據(jù)。 由于設(shè)定一百萬個數(shù)據(jù)比較多，這里我們舉例當(dāng)前擁有數(shù)據(jù)[7,5,9,2,11,6],我們要找出其中的6。 使用循環(huán)遍歷所有數(shù)據(jù)的方法，我們需要6次遍歷 7->5->9->2->11->6。 使用二叉查找樹查找時(shí)，首先構(gòu)建好的二叉查找樹的結(jié)構(gòu)如圖：
從根結(jié)點(diǎn)開始查找；
獲取根結(jié)點(diǎn)7，不等于6，且6<7，所以繼續(xù)找左子結(jié)點(diǎn)；
獲取到結(jié)點(diǎn)5，不等于6，且6>5，所以繼續(xù)找右子節(jié)點(diǎn)；
最終獲取到結(jié)點(diǎn)6，滿足我們需要的條件。所遍歷的數(shù)據(jù)為 7->5->6。 代碼實(shí)現(xiàn)查找：
package com.ytao.bst;
/**
* Created by YANGTAO on 2019/11/3 0003.
*/
public class SearchBST {
public Node search(Node node, int val){
// 如果結(jié)點(diǎn)為空，說明是沒有了符合的結(jié)點(diǎn)
if (node == null)
return null;
int nodeVal = node.getValue();
// 如果結(jié)點(diǎn)上的鍵值相等，就是我們需要找的結(jié)點(diǎn)
if (val == nodeVal){
return node;
}else if (val < nodeVal){ // 如果小于結(jié)點(diǎn)的值，那么一定在結(jié)點(diǎn)的左子樹中
return this.search(node.getLeftChildren(), val);
}else{
return this.search(node.getRightChildren(), val);
}
}
}二叉查找樹的插入規(guī)則，必須是要插入后的結(jié)點(diǎn)是作為葉子結(jié)點(diǎn)?，F(xiàn)在向上面的樹中插入10，根據(jù)上面所分析到的規(guī)則，為確保二叉查找樹的完整性，最終的插入流程為7->9->11->10：
代碼實(shí)現(xiàn)：
package com.ytao.bst;
/**
* Created by YANGTAO on 2019/11/3 0003.
*/
public class InsertBST {
public void inesrt(Node node, int newVal){
// 當(dāng)結(jié)點(diǎn)為空是，說明是作為根結(jié)點(diǎn)
if (node == null){
node = new Node(newVal);
}
int nodeVal = node.getValue();
// 如果小于結(jié)點(diǎn)的值，插入到左子樹中，大于就插入右子樹中
if (newVal < nodeVal){
Node leftNode = node.getLeftChildren();
// 為空時(shí)，說明為葉子結(jié)點(diǎn)，可插入
if (leftNode == null){
node.setLeftChildren(new Node(newVal));
}else {
this.inesrt(leftNode, newVal);
}
}else if (newVal > nodeVal){
Node rightNode = node.getRightChildren();
if (rightNode == null){
node.setRightChildren(new Node(newVal));
}else {
this.inesrt(rightNode, newVal);
}
}else {
// todo 相等時(shí)，可根據(jù)具體業(yè)務(wù)處理，放棄，或在左右樹中選擇一個
}
}
}刪除結(jié)點(diǎn)分為多種情況，其中主要分析的：
刪除葉子結(jié)點(diǎn)，將所要刪除的葉子結(jié)點(diǎn)直接刪除便可，比如刪除結(jié)點(diǎn)6。
被刪除結(jié)點(diǎn)，如果只有一個子結(jié)點(diǎn)，那么被刪除結(jié)點(diǎn)刪除后，該結(jié)點(diǎn)的子結(jié)點(diǎn)補(bǔ)上其位置，比如刪除結(jié)點(diǎn)9。
為了更加清楚表達(dá)刪除存在左右結(jié)點(diǎn)的結(jié)點(diǎn)，先向樹中多添加3個結(jié)點(diǎn)8，10，15。然后刪除結(jié)點(diǎn)9。 這里的解決方法就是，刪除9后，可以用前驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn)補(bǔ)上。前驅(qū)結(jié)點(diǎn)為左子樹中最大的結(jié)點(diǎn)，后繼結(jié)點(diǎn)為右子樹中最小的結(jié)點(diǎn)。 現(xiàn)在以后繼結(jié)點(diǎn)補(bǔ)上的方案為：
后繼結(jié)點(diǎn)補(bǔ)上刪除后的結(jié)點(diǎn)：
完成刪除，后繼結(jié)點(diǎn)補(bǔ)充上后：
代碼實(shí)現(xiàn)：
package com.ytao.bst;
/**
* Created by YANGTAO on 2019/11/3 0003.
*/
public class DeleteBST {
public Node delete(Node node, int delVal) {
// 為空時(shí)，代表葉子結(jié)點(diǎn)
if (node == null){
return node;
}
int nodeVal = node.getValue();
Node leftNode = node.getLeftChildren();
Node rightNode = node.getRightChildren();
// 刪除的結(jié)點(diǎn)，與遍歷到的當(dāng)前結(jié)點(diǎn)做比較，小于，大于或等于
if (delVal < nodeVal){
Node tempLeftNode = delete(leftNode, delVal);
node.setLeftChildren(tempLeftNode);
} else if(delVal > nodeVal){
Node tempRightNode = delete(rightNode, delVal);
node.setRightChildren(tempRightNode);
} else {
// 刪除的結(jié)點(diǎn)與當(dāng)前遍歷到的結(jié)點(diǎn)相等時(shí)
// 并且左結(jié)點(diǎn)為空時(shí)，返回右結(jié)點(diǎn)去補(bǔ)上刪除的位置，反則返回左結(jié)點(diǎn)補(bǔ)上
// 說明刪除結(jié)點(diǎn)為單子結(jié)點(diǎn)的情況
if (leftNode == null){
return rightNode;
} else if (rightNode == null){
return leftNode;
}
// 通過查詢最小右結(jié)點(diǎn)，獲取后繼結(jié)點(diǎn)
Node minNode = minNode(rightNode);
int minNodeValue = minNode.getValue();
node.setValue(minNodeValue);
// 刪除后繼結(jié)點(diǎn)
Node tempRightNode = delete(rightNode, minNodeValue);
node.setRightChildren(tempRightNode);
}
return node;
}
private Node minNode(Node node) {
// 一直尋找最小值，知道左子節(jié)點(diǎn)為空為止
Node leftNode = node.getLeftChildren();
if (leftNode != null)
return minNode(leftNode);
return node;
}
}至此上面三中情況都予滿足。
上面對二叉查找樹的操作都已介紹，但是正真使用中，是要結(jié)合實(shí)際業(yè)務(wù)進(jìn)行相關(guān)調(diào)整來滿足自己的需求，不然，一切的優(yōu)化手段都是假把式。二叉查找樹雖然好用，但是它也是有一定要求，在數(shù)據(jù)量不大的情況下，使用遍歷的方式，更加符合我們的要求，所以它使用場景一般是在海量數(shù)據(jù)的查詢，用來提查詢效率。
“二叉查找樹的概念和實(shí)現(xiàn)方法”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！
