定義：
一棵二叉查找樹是一棵二叉樹，每個節(jié)點都含有一個Comparable的鍵（以及對應(yīng)的值）。
每個節(jié)點的鍵都大于左子樹中任意節(jié)點的鍵而小于右子樹中任意節(jié)點的鍵。

樹的術(shù)語：

NameFunction

路徑	順著連接點的邊從一個節(jié)點走向另一個節(jié)點，所經(jīng)過的節(jié)點的順序排列就稱為路徑。
根	樹頂端的節(jié)點就稱為根，一棵樹只有一個根，如果要把一個節(jié)點和邊的集合定義為樹，那么從根到其他任何一個節(jié)點都必須有一條路徑。
父節(jié)點	每個節(jié)點（除了根）都恰好有一條邊向上連接到另一個節(jié)點，上面的節(jié)點就稱為下面節(jié)點的“父節(jié)點”。
子節(jié)點	每個節(jié)點都可能有一條或多條邊向下連接其他節(jié)點，下面的這些節(jié)點就稱為它的“子節(jié)點”。
葉節(jié)點	沒有子節(jié)點的節(jié)點稱為“葉子節(jié)點”或簡稱“葉節(jié)點”。樹只能有一個根，但是可以有很多葉節(jié)點。
子樹	每個節(jié)點都可以作為子樹的根，它和它所有的子節(jié)點，子節(jié)點的子節(jié)點等都含在子樹中。
訪問	當(dāng)程序控制流程到達某個節(jié)點的時候，就稱為“訪問”這個節(jié)點，通常是為了在這個節(jié)點處執(zhí)行某種操作，例如查看節(jié)點某個數(shù)據(jù)字段的值或者顯示節(jié)點。
遍歷	遍歷樹意味著要遵循某種特定的順序訪問樹中的所有節(jié)點。
層	一個節(jié)點的層數(shù)是指從根開始到這個節(jié)點有多少“代”。
關(guān)鍵字	可以看到，對象中通常會有一個數(shù)據(jù)域被指定為關(guān)鍵字值。這個值通常用于查詢或者其他操作。
二叉樹	如果樹中的每個節(jié)點最多只能有兩個子節(jié)點，這樣的樹就稱為“二叉樹”。

性質(zhì)：

若它的左子樹不為空，則左子樹上的所有節(jié)點的值都小于它的根節(jié)點的值；

若它的右子樹不為空，則右子樹上所有節(jié)點的值都大于它的根節(jié)點的值；

其他的左右子樹也分別為二叉查找樹；

二叉查找樹是動態(tài)查找表，在查找的過程中可見添加和刪除相應(yīng)的元素，在這些操作中需要保持二叉查找樹的以上性質(zhì)。

根據(jù)其二叉樹的特性，節(jié)點類如下:

public class Node {public int index;//關(guān)鍵字段public String data;//值public Node leftNode;//左節(jié)點public Node rightNode;//右節(jié)點@Overridepublic boolean equals(Object obj) {return EqualsBuilder.reflectionEquals(this, obj);}@Overridepublic int hashCode() {return HashCodeBuilder.reflectionHashCode(this);} }

其中引用了commons-lang3包中的內(nèi)容，作為對象進行比較

查找某個節(jié)點，相當(dāng)于二分查找，如果小于當(dāng)前節(jié)點，則走左邊，如果大于當(dāng)前節(jié)點，則走右邊。當(dāng)最后葉子節(jié)點還沒有找到，則沒有找到

public Node findNode(int key){Node current = root;while(current.index != key){if(key < current.index){//左節(jié)點current = current.leftNode;}else{//右節(jié)點current = current.rightNode;}if(current == null){return null;}}return current; }

插入節(jié)點,按照插入的節(jié)點都不會出現(xiàn)重復(fù)關(guān)鍵字。每一次插入都將變?yōu)楦?jié)點的子節(jié)點，例如根節(jié)點關(guān)鍵字為1，接下來插入的節(jié)點則變?yōu)楦?jié)點的右子節(jié)點。

public void insertNode(int key,String value){Node node = new Node();node.index = key;node.data = value;if(root == null){root = node;return;}//找到插入節(jié)點的位置Node parent = root;Node current = root;while(true){parent = current;if(key == current.index){return;}if(key < current.index){//左節(jié)點current = current.leftNode;if(current == null){//當(dāng)前節(jié)點已經(jīng)是葉子結(jié)點了parent.leftNode = node; return;}}else{current = current.rightNode;if(current == null){parent.rightNode = node;return;}}} }

遍歷節(jié)點，中序遍歷.

調(diào)用自身來遍歷節(jié)點的左子樹

訪問這個節(jié)點

掉用自身來遍歷節(jié)點的右子樹

public void inOrder(Node localRoot) {if (localRoot != null) {inOrder(localRoot.leftNode);System.out.println("索引：" + localRoot.index + ",值：" + localRoot.data);inOrder(localRoot.rightNode);} }

刪除節(jié)點，分三種情況：

刪除節(jié)點沒有子節(jié)點，那么將父節(jié)點的左節(jié)點或者是右節(jié)點設(shè)置為空

刪除節(jié)點只有一個子節(jié)點，刪除該節(jié)點后，該節(jié)點的子節(jié)點變?yōu)楦腹?jié)點的子節(jié)點，如果刪除節(jié)點時父節(jié)點的左節(jié)點，那么父節(jié)點的左節(jié)點指向該節(jié)點的子節(jié)點，反之則右節(jié)點指向刪除節(jié)點的子節(jié)點。

刪除節(jié)點有兩個字節(jié)點，刪除了該節(jié)點后，則需要選擇一個后繼節(jié)點，并且還不破壞該二叉樹的特性(左節(jié)點要小于右節(jié)點)，一般是從刪除節(jié)點的右節(jié)點中找到一個后繼節(jié)點，而這個節(jié)點是右子樹的最小值。

public boolean delete(int key) {Node current = root;Node parent = root;boolean isLeftChild = true;//找到被刪除的節(jié)點，并標(biāo)識該節(jié)點是否為左節(jié)點while (current.index != key) {parent = current;if (key < current.index) {isLeftChild = true;current = current.leftNode;} else {isLeftChild = false;current = current.rightNode;}if (current == null) {return false;}}//第一種情況，刪除節(jié)點為子節(jié)點if (current.leftNode == null && current.rightNode == null) {if (current == root) {root = null;} else {if (isLeftChild) {parent.leftNode = null;} else {parent.rightNode = null;}}} else if ((current.leftNode != null && current.rightNode == null) || (current.leftNode == null && current.rightNode != null)) {//第二中情況，刪除節(jié)點只包含一個子節(jié)點，則將子節(jié)點移動動當(dāng)前節(jié)點中if (current.rightNode == null) {//刪除的節(jié)點的左節(jié)點有值，右節(jié)點為空if (root == current) {root = current.leftNode;} else {if (isLeftChild) {parent.leftNode = current.leftNode;} else {parent.rightNode = current.leftNode;}}} else {//刪除的節(jié)點的右節(jié)點有值，左節(jié)點為空if (root == current) {root = current.rightNode;} else {if (isLeftChild) {parent.leftNode = current.rightNode;} else {parent.rightNode = current.rightNode;}}}} else if (current.leftNode != null && current.rightNode != null) {//第三種情況，刪除節(jié)點中有左右兩個節(jié)點//找到后繼節(jié)點Node processer = processer(current);if (current == root) {//刪除是根節(jié)點，則root = processer;} else {if (isLeftChild) {parent.leftNode = processer;} else {parent.rightNode = processer;}}//選中的節(jié)點的左節(jié)點與刪除節(jié)點的左節(jié)點相連processer.leftNode = current.leftNode;}return true;}//找到后繼節(jié)點private Node processer(Node delNode) {Node parent = delNode;Node success = delNode;Node current = delNode.rightNode;while (current != null) {// 后繼節(jié)點父節(jié)點首先保存后繼節(jié)點的狀態(tài)parent = current;success = current;// 后繼節(jié)點 不斷的向左更新current = current.leftNode;}// 假如我們找到的后繼節(jié)點不直接是 要刪除節(jié)點的右節(jié)點 而是在其右節(jié)點那條子樹上面最小的一個節(jié)點if (success != delNode.rightNode) {//后繼節(jié)點的父節(jié)點斷開其與后繼節(jié)點左邊的引用，重新連接上后繼節(jié)點的右子節(jié)點（因為后繼節(jié)點是沒有左子節(jié)點的，鎖以要保存之前樹的狀態(tài)，還要把后繼節(jié)點的右子節(jié)點處理一下，不管 其存在不存在）parent.leftNode = success.rightNode;// 這時候后繼節(jié)點的右邊已經(jīng)空了 上一條語句已經(jīng)將其給了自己父節(jié)點的左子節(jié)點 然后讓后繼節(jié)點的右邊 連接要刪除節(jié)點的右子樹success.rightNode = delNode.rightNode;}return success;}

轉(zhuǎn)載于:https://www.cnblogs.com/skyice/p/10618303.html

總結(jié)

以上是生活随笔為你收集整理的二叉查找树 Java实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。