Java實現(xiàn)的二叉搜索樹埂蕊，并實現(xiàn)對該樹的搜索往弓，插入疏唾，刪除操作（合并刪除，復(fù)制刪除）
首先我們要有一個編碼的思路函似，大致如下：
1槐脏、查找：根據(jù)二叉搜索樹的數(shù)據(jù)特點，我們可以根據(jù)節(jié)點的值得比較來實現(xiàn)查找缴淋，查找值大于當(dāng)前節(jié)點時向右走准给，反之向左走！
2重抖、插入：我們應(yīng)該知道露氮，插入的全部都是葉子節(jié)點，所以我們就需要找到要進行插入的葉子節(jié)點的位置钟沛，插入的思路與查找的思路一致畔规。
3、刪除：
1）合并刪除：一般來說會遇到以下幾種情況恨统，被刪節(jié)點有左子樹沒右子樹叁扫，此時要讓當(dāng)前節(jié)點的父節(jié)點指向當(dāng)前節(jié)點的左子樹；當(dāng)被刪節(jié)點有右子樹沒有左子樹畜埋，此時要讓當(dāng)前節(jié)點的父節(jié)點指向該右子樹莫绣；當(dāng)被刪節(jié)點即有左子樹又有右子樹時，我們可以找到被刪節(jié)點的左子樹的最右端的節(jié)點悠鞍，然后讓這個節(jié)點的右或者左“指針”指向被刪節(jié)點的右子樹
2）復(fù)制刪除：復(fù)制刪除相對而言是比較簡單的刪除操作对室，也是最為常用的刪除操作。大致也有以下三種情況：當(dāng)前節(jié)點無左子樹有右子樹時咖祭，讓當(dāng)前右子樹的根節(jié)點替換被刪節(jié)點掩宜；當(dāng)前節(jié)點無右子樹有左子樹時，讓當(dāng)前左子樹的根節(jié)點替換被刪除節(jié)點么翰；當(dāng)前被刪節(jié)點既有左子樹又有右子樹時牺汤，我們就要找到被刪節(jié)點的替身，可以在被刪節(jié)點的左子樹中找到其最右端的節(jié)點浩嫌，并讓這個節(jié)點的值賦給被刪節(jié)點檐迟，然后別忘了讓此替身節(jié)點的父節(jié)點指向替身的“指針”為空，（其實在Java中無關(guān)緊要了码耐，有垃圾處理機制自動進行處理）追迟。你也可以在當(dāng)前被刪節(jié)點的右子樹的最左端的節(jié)點作為替身節(jié)點來實現(xiàn)這一過程。
接下來就上代碼吧伐坏。
首先是## 二叉搜索樹節(jié)點類 ##
package SearchBinaryTree;
public class SearchBinaryTreeNode<T> {
T data;
public SearchBinaryTreeNode<T> leftChild;
public SearchBinaryTreeNode<T> rightChild;
public SearchBinaryTreeNode(){
this.data=null;
this.leftChild=this.rightChild=null;
}
public SearchBinaryTreeNode(T da){
this.data=da;
this.leftChild=this.rightChild=null;
}
public SearchBinaryTreeNode(T da,SearchBinaryTreeNode<T> left,SearchBinaryTreeNode<T>right){
this.data=da;
this.leftChild=left;
this.rightChild=right;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public SearchBinaryTreeNode<T> getLeftChild() {
return leftChild;
}
public void setLeftChild(SearchBinaryTreeNode<T> leftChild) {
this.leftChild = leftChild;
}
public SearchBinaryTreeNode<T> getRightChild() {
return rightChild;
}
public void setRightChild(SearchBinaryTreeNode<T> rightChild) {
this.rightChild = rightChild;
}
public boolean isLeaf(){
if(this.leftChild==null&&this.rightChild==null){
return true;
}
return false;
}
}
實現(xiàn)二叉搜索樹
package SearchBinaryTree;
public class SearchBinaryTree<T> {
SearchBinaryTreeNode<T> root;
public boolean isEmpty(){
if(root==null){
return true;
}
return false;
}
public void Visit(SearchBinaryTreeNode<T> root){
if(root==null){
System.out.println("this tree is empty!");
}
System.out.println(root.getData());
}
public SearchBinaryTreeNode<T> getRoot(){
if(root==null){
root=new SearchBinaryTreeNode<T>();
}
return root;
}
public SearchBinaryTree(){
this.root=null;
}
/*
* 創(chuàng)造一顆二叉樹
*/
public void CreateTree(SearchBinaryTreeNode<T> node, T data) {
if (root == null) {
root = new SearchBinaryTreeNode<T>();
} else {
if (Math.random() > 0.5) { //采用隨機方式創(chuàng)建二叉樹
if (node.leftChild == null) {
node.leftChild = new SearchBinaryTreeNode<T>(data);
} else {
CreateTree(node.leftChild, data);
}
} else {
if (node.rightChild == null) {
node.rightChild = new SearchBinaryTreeNode<T>(data);
} else {
CreateTree(node.rightChild, data);
}
}
}
}
/*
* 在二查搜索樹中進行搜索
*/
public SearchBinaryTreeNode<T> search(SearchBinaryTreeNode<T> root,T value){
SearchBinaryTreeNode<T> current=root;
while((root!=null)&&(current.getData()!=value)){
//需要注意的是java中泛型無法比較大小怔匣，在實際的使用時我們可以使用常見的數(shù)據(jù)類型來替代這個泛型握联，這樣就不會出錯了
current=(value<current.getData()?search(current.leftChild,value):search(current.rightChild,value));
}
return current;
}
public SearchBinaryTreeNode<T> insertNode( T value){
SearchBinaryTreeNode<T> p=root,pre=null;
while(p!=null){
pre=p;
//需要注意的是java中泛型無法比較大小桦沉，在實際的使用時我們可以使用常見的數(shù)據(jù)類型來替代這個泛型每瞒，這樣就不會出錯了
if(p.getData()<value){
p=p.rightChild;
}else{
p=p.leftChild;
}
}
if(root==null){
root=new SearchBinaryTreeNode<T>(value);
}else if(pre.getData()<value){
pre.rightChild=new SearchBinaryTreeNode<T>(value);
}else{
pre.leftChild=new SearchBinaryTreeNode<T>(value);
}
}
/*
* 合并刪除
*/
public void deleteByMerging(SearchBinaryTreeNode<T> node){
SearchBinaryTreeNode<T> temp=node;
if(node!=null){
//若被刪除節(jié)點沒有右子樹,用其左子樹的根節(jié)點來代替被刪除節(jié)點
if(node.rightChild!=null){
node=node.leftChild;
}else if(node.leftChild==null){
//若被刪節(jié)點沒有左子樹，用其有字?jǐn)?shù)的最左端的節(jié)點代替被刪除的節(jié)點
node=node.rightChild;
}else{
//如果被刪節(jié)點左右子樹均存在
temp=node.leftChild;
while(temp.rightChild!=null){
temp=temp.rightChild; //一直查找到左子樹的右節(jié)點
}
//將查找到的節(jié)點的右指針賦值為被刪除節(jié)點的右子樹的根
temp.rightChild=node.rightChild;
temp=node;
node=node.leftChild;
}
temp=null;
}
}
/*
* 復(fù)制刪除
*/
public void deleteByCoping(SearchBinaryTreeNode<T> node){
SearchBinaryTreeNode<T> pre=null;
SearchBinaryTreeNode<T> temp=node;
//如果被刪節(jié)點沒有右子樹纯露，用其左子樹的根節(jié)點來代替被刪除節(jié)點
if(node.rightChild==null){
node=node.leftChild;
}else if(node.leftChild==null){
node=node.rightChild;
}else{
//如果被刪節(jié)點的左右子樹都存在
temp=node.leftChild;
pre=node;
while(temp.rightChild!=null){
pre=temp;
temp=temp.rightChild; //遍歷查找到左子樹的最右端的節(jié)點
}
node.data=temp.data; //進行賦值操作
if(pre==node){
pre.leftChild=node.leftChild;
}else{
pre.rightChild=node.rightChild;
}
}
temp=null;
}
}
測試類
package SearchBinaryTree;
public class SearchBinaryTreeTest {
public static void main(String []args){
SearchBinaryTree<Integer> tree=new SearchBinaryTree<Integer>();
for(int i=1;i<10;i++){
tree.CreateTree(new SearchBinaryTreeNode<Integer>(), i);
}
//搜索
tree.search(tree.root, 7);
//合并刪除
tree.deleteByMerging(new SearchBinaryTreeNode<Integer>(8));
//復(fù)制刪除
tree.deleteByCoping(new SearchBinaryTreeNode<Integer>(6));
}
}
好了剿骨，就是這樣！
