二叉搜索樹需滿足以下四個(gè)條件：

1. 若任意節(jié)點(diǎn)的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
2. 若任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
3. 任意節(jié)點(diǎn)的左、右子樹也分別為二叉查找樹；
4. 沒有鍵值相等的節(jié)點(diǎn)。

二叉搜索樹舉例：

圖一

接下來將基于圖一介紹二叉搜索樹相關(guān)操作。

首先，應(yīng)先有一個(gè)節(jié)點(diǎn)對(duì)象相關(guān)的類，命名為Node。

1classNode{2intkey;3intvalue;4NodeleftChild;5NoderightChild;67publicNode(intkey,intvalue){8this.key=key;9this.value=value;10}1112publicvoiddisplayNode(){1314}15}

Node類中包含key值，用于確定節(jié)點(diǎn)在樹中相應(yīng)位置，value值代表要存儲(chǔ)的內(nèi)容，還含有指向左右孩子節(jié)點(diǎn)的兩個(gè)引用。

接下來看下搜索樹相應(yīng)的類：

1classTree{2Noderoot;//保存樹的根34publicNodefind(intkey){//查找指定節(jié)點(diǎn)56}78publicvoidinsert(intkey,intvalue){//插入節(jié)點(diǎn)910}1112publicbooleandelete(intkey){//刪除指定節(jié)點(diǎn)1314}1516privateNodegetDirectPostNode(NodedelNode){//得到待刪除節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)1718}1920publicvoidpreOrder(NoderootNode){//先序遍歷樹2122}2324publicvoidinOrder(NoderootNode){//中序遍歷樹2526}2728publicvoidpostOrder(NoderootNode){//后序遍歷樹2930}31}

類中表示樹的框架，包含查找、插入、遍歷、刪除相應(yīng)方法，其中刪除節(jié)點(diǎn)操作最為復(fù)雜，接下來一一介紹。

一、查找某個(gè)節(jié)點(diǎn)

由于二叉搜索樹定義上的特殊性，只需根據(jù)輸入的key值從根開始進(jìn)行比較，若小于根的key值，則與根的左子樹比較，大于根的key值與根的右子樹比較，以此類推，找到則返回相應(yīng)節(jié)點(diǎn)，否則返回null。

1publicNodefind(intkey){2NodecurrentNode=root;3while(currentNode!=null&&currentNode.key!=key){4if(key<currentNode.key){5currentNode=currentNode.leftChild;6}else{7currentNode=currentNode.rightChild;8}9}10returncurrentNode;11}

二、插入節(jié)點(diǎn)

與查找操作相似，由于二叉搜索樹的特殊性，待插入的節(jié)點(diǎn)也需要從根節(jié)點(diǎn)開始進(jìn)行比較，小于根節(jié)點(diǎn)則與根節(jié)點(diǎn)左子樹比較，反之則與右子樹比較，直到左子樹為空或右子樹為空，則插入到相應(yīng)為空的位置，在比較的過程中要注意保存父節(jié)點(diǎn)的信息及待插入的位置是父節(jié)點(diǎn)的左子樹還是右子樹，才能插入到正確的位置。

1publicvoidinsert(intkey,intvalue){2if(root==null){3root=newNode(key,value);4return;5}6NodecurrentNode=root;7NodeparentNode=root;8booleanisLeftChild=true;9while(currentNode!=null){10parentNode=currentNode;11if(key<currentNode.key){12currentNode=currentNode.leftChild;13isLeftChild=true;14}else{15currentNode=currentNode.rightChild;16isLeftChild=false;17}18}19NodenewNode=newNode(key,value);20if(isLeftChild){21parentNode.leftChild=newNode;22}else{23parentNode.rightChild=newNode;24}25}

三、遍歷二叉搜索樹

遍歷操作與遍歷普通二叉樹操作完全相同，不贅述。

1publicvoidpreOrder(NoderootNode){2if(rootNode!=null){3System.out.println(rootNode.key+""+rootNode.value);4preOrder(rootNode.leftChild);5preOrder(rootNode.rightChild);6}7}89publicvoidinOrder(NoderootNode){10if(rootNode!=null){11inOrder(rootNode.leftChild);12System.out.println(rootNode.key+""+rootNode.value);13inOrder(rootNode.rightChild);14}15}1617publicvoidpostOrder(NoderootNode){18if(rootNode!=null){19postOrder(rootNode.leftChild);20postOrder(rootNode.rightChild);21System.out.println(rootNode.key+""+rootNode.value);22}23}

四、刪除指定節(jié)點(diǎn)。

在二叉搜索樹中刪除節(jié)點(diǎn)操作較復(fù)雜，可分為以下三種情況。

1、待刪除的節(jié)點(diǎn)為葉子節(jié)點(diǎn)，可直接刪除。

publicbooleandelete(intkey){NodecurrentNode=root;//用來保存待刪除節(jié)點(diǎn)NodeparentNode=root;//用來保存待刪除節(jié)點(diǎn)的父親節(jié)點(diǎn)booleanisLeftChild=true;//用來確定待刪除節(jié)點(diǎn)是父親節(jié)點(diǎn)的左孩子還是右孩子while(currentNode!=null&&currentNode.key!=key){parentNode=currentNode;if(key<currentNode.key){currentNode=currentNode.leftChild;isLeftChild=true;}else{currentNode=currentNode.rightChild;isLeftChild=false;}}if(currentNode==null){returnfalse;}if(currentNode.leftChild==null&&currentNode.rightChild==null){//要?jiǎng)h除的節(jié)點(diǎn)為葉子節(jié)點(diǎn)if(currentNode==root)root=null;elseif(isLeftChild)parentNode.leftChild=null;elseparentNode.rightChild=null;}......}

2、待刪除節(jié)點(diǎn)只有一個(gè)孩子節(jié)點(diǎn)

例如刪除圖一中的key值為11的節(jié)點(diǎn)，只需將key值為13的節(jié)點(diǎn)的左孩子指向key值為12的節(jié)點(diǎn)即可達(dá)到刪除key值為11的節(jié)點(diǎn)的目的。

由以上分析可得代碼如下（接上述delete方法省略號(hào)后）：

1elseif(currentNode.rightChild==null){//要?jiǎng)h除的節(jié)點(diǎn)只有左孩子2if(currentNode==root)3root=currentNode.leftChild;4elseif(isLeftChild)5parentNode.leftChild=currentNode.leftChild;6else7parentNode.rightChild=currentNode.leftChild;8}elseif(currentNode.leftChild==null){//要?jiǎng)h除的節(jié)點(diǎn)只有右孩子9if(currentNode==root)10root=currentNode.rightChild;11elseif(isLeftChild)12parentNode.leftChild=currentNode.rightChild;13else14parentNode.rightChild=currentNode.rightChild;15}......

3、待刪除節(jié)點(diǎn)既有左孩子，又有右孩子。

例如刪除圖一中key值為10的節(jié)點(diǎn)，這時(shí)就需要用key值為10的節(jié)點(diǎn)的中序后繼節(jié)點(diǎn)（節(jié)點(diǎn)11）來代替key值為10的節(jié)點(diǎn)，并刪除key值為10的節(jié)點(diǎn)的中序后繼節(jié)點(diǎn)，由中序遍歷相關(guān)規(guī)則可知，key值為10的節(jié)點(diǎn)的直接中序后繼節(jié)點(diǎn)一定是其右子樹中key值最小的節(jié)點(diǎn)，所以此中序后繼節(jié)點(diǎn)一定不含子節(jié)點(diǎn)或者只含有一個(gè)右孩子，刪除此中序后繼節(jié)點(diǎn)就屬于上述1,2所述情況。圖一中key值為10的節(jié)點(diǎn)的直接中序后繼節(jié)點(diǎn)為11，節(jié)點(diǎn)11含有一個(gè)右孩子12。

所以刪除圖一中key值為10的節(jié)點(diǎn)分為以下幾步：

a、找到key值為10的節(jié)點(diǎn)的直接中序后繼節(jié)點(diǎn)（即其右子樹中值最小的節(jié)點(diǎn)11），并刪除此直接中序后繼節(jié)點(diǎn)。

1privateNodegetDirectPostNode(NodedelNode){//方法作用為得到待刪除節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)23NodeparentNode=delNode;//用來保存待刪除節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)的父親節(jié)點(diǎn)4NodedirecrPostNode=delNode;//用來保存待刪除節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)5NodecurrentNode=delNode.rightChild;6while(currentNode!=null){7parentNode=direcrPostNode;8direcrPostNode=currentNode;9currentNode=currentNode.leftChild;10}11if(direcrPostNode!=delNode.rightChild){//從樹中刪除此直接后繼節(jié)點(diǎn)12parentNode.leftChild=direcrPostNode.rightChild;13direcrPostNode.rightChild=null;14}15returndirecrPostNode;//返回此直接后繼節(jié)點(diǎn)1617}

b、將此后繼節(jié)點(diǎn)的key、value值賦給待刪除節(jié)點(diǎn)的key，value值。(接情況二中省略號(hào)代碼之后)

1else{//要?jiǎng)h除的節(jié)點(diǎn)既有左孩子又有右孩子23//思路：用待刪除節(jié)點(diǎn)右子樹中的key值最小節(jié)點(diǎn)的值來替代要?jiǎng)h除的節(jié)點(diǎn)的值,然后刪除右子樹中key值最小的節(jié)點(diǎn)4//右子樹key最小的節(jié)點(diǎn)一定不含左子樹,所以刪除這個(gè)key最小的節(jié)點(diǎn)一定是屬于葉子節(jié)點(diǎn)或者只有右子樹的節(jié)點(diǎn)5NodedirectPostNode=getDirectPostNode(currentNode);6currentNode.key=directPostNode.key;7currentNode.value=directPostNode.value;89}

至此刪除指定節(jié)點(diǎn)的操作結(jié)束。

最后給出完整代碼及簡單測(cè)試代碼及測(cè)試結(jié)果：

1classNode{2intkey;3intvalue;4NodeleftChild;5NoderightChild;67publicNode(intkey,intvalue){8this.key=key;9this.value=value;10}1112publicvoiddisplayNode(){1314}15}1617classTree{18Noderoot;1920publicNodefind(intkey){21NodecurrentNode=root;22while(currentNode!=null&&currentNode.key!=key){23if(key<currentNode.key){24currentNode=currentNode.leftChild;25}else{26currentNode=currentNode.rightChild;27}28}29returncurrentNode;30}3132publicvoidinsert(intkey,intvalue){33if(root==null){34root=newNode(key,value);35return;36}37NodecurrentNode=root;38NodeparentNode=root;39booleanisLeftChild=true;40while(currentNode!=null){41parentNode=currentNode;42if(key<currentNode.key){43currentNode=currentNode.leftChild;44isLeftChild=true;45}else{46currentNode=currentNode.rightChild;47isLeftChild=false;48}49}50NodenewNode=newNode(key,value);51if(isLeftChild){52parentNode.leftChild=newNode;53}else{54parentNode.rightChild=newNode;55}56}5758publicbooleandelete(intkey){59NodecurrentNode=root;60NodeparentNode=root;61booleanisLeftChild=true;62while(currentNode!=null&&currentNode.key!=key){63parentNode=currentNode;64if(key<currentNode.key){65currentNode=currentNode.leftChild;66isLeftChild=true;67}else{68currentNode=currentNode.rightChild;69isLeftChild=false;70}71}72if(currentNode==null){73returnfalse;74}75if(currentNode.leftChild==null&&currentNode.rightChild==null){76//要?jiǎng)h除的節(jié)點(diǎn)為葉子節(jié)點(diǎn)77if(currentNode==root)78root=null;79elseif(isLeftChild)80parentNode.leftChild=null;81else82parentNode.rightChild=null;83}elseif(currentNode.rightChild==null){//要?jiǎng)h除的節(jié)點(diǎn)只有左孩子84if(currentNode==root)85root=currentNode.leftChild;86elseif(isLeftChild)87parentNode.leftChild=currentNode.leftChild;88else89parentNode.rightChild=currentNode.leftChild;90}elseif(currentNode.leftChild==null){//要?jiǎng)h除的節(jié)點(diǎn)只有右孩子91if(currentNode==root)92root=currentNode.rightChild;93elseif(isLeftChild)94parentNode.leftChild=currentNode.rightChild;95else96parentNode.rightChild=currentNode.rightChild;97}else{//要?jiǎng)h除的節(jié)點(diǎn)既有左孩子又有右孩子98//思路：用待刪除節(jié)點(diǎn)右子樹中的key值最小節(jié)點(diǎn)的值來替代要?jiǎng)h除的節(jié)點(diǎn)的值,然后刪除右子樹中key值最小的節(jié)點(diǎn)99//右子樹key最小的節(jié)點(diǎn)一定不含左子樹,所以刪除這個(gè)key最小的節(jié)點(diǎn)一定是屬于葉子節(jié)點(diǎn)或者只有右子樹的節(jié)點(diǎn)100NodedirectPostNode=getDirectPostNode(currentNode);101currentNode.key=directPostNode.key;102currentNode.value=directPostNode.value;103}104returntrue;105}106107privateNodegetDirectPostNode(NodedelNode){//方法作用為得到待刪除節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)108109NodeparentNode=delNode;//用來保存待刪除節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)的父親節(jié)點(diǎn)110NodedirecrPostNode=delNode;//用來保存待刪除節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)111NodecurrentNode=delNode.rightChild;112while(currentNode!=null){113parentNode=direcrPostNode;114direcrPostNode=currentNode;115currentNode=currentNode.leftChild;116}117if(direcrPostNode!=delNode.rightChild){//從樹中刪除此直接后繼節(jié)點(diǎn)118parentNode.leftChild=direcrPostNode.rightChild;119direcrPostNode.rightChild=null;120}121returndirecrPostNode;//返回此直接后繼節(jié)點(diǎn)122123}124125publicvoidpreOrder(NoderootNode){126if(rootNode!=null){127System.out.println(rootNode.key+""+rootNode.value);128preOrder(rootNode.leftChild);129preOrder(rootNode.rightChild);130}131}132133publicvoidinOrder(NoderootNode){134if(rootNode!=null){135inOrder(rootNode.leftChild);136System.out.println("key:"+rootNode.key+""+"value:"+rootNode.value);137inOrder(rootNode.rightChild);138}139}140141publicvoidpostOrder(NoderootNode){142if(rootNode!=null){143postOrder(rootNode.leftChild);144postOrder(rootNode.rightChild);145System.out.println(rootNode.key+""+rootNode.value);146}147}privatevoiddestroy(Nodetree){if(tree==null)return;if(tree.left!=null)destroy(tree.leftChild);if(tree.right!=null)destroy(tree.rightChild);tree=null;}publicvoiddestory(){destory(root);}148}149publicclassBinarySearchTreeApp{150publicstaticvoidmain(String[]args){151Treetree=newTree();152tree.insert(6,6);//插入操作,構(gòu)造圖一所示的二叉樹153tree.insert(3,3);154tree.insert(14,14);155tree.insert(16,16);156tree.insert(10,10);157tree.insert(9,9);158tree.insert(13,13);159tree.insert(11,11);160tree.insert(12,12);161162System.out.println("刪除前遍歷結(jié)果");163tree.inOrder(tree.root);//中序遍歷操作164165System.out.println("刪除節(jié)點(diǎn)10之后遍歷結(jié)果");166tree.delete(10);//刪除操作167tree.inOrder(tree.root);168}169}

測(cè)試結(jié)果：