您好,登錄后才能下訂單哦!
Java實(shí)現(xiàn)的二叉搜索樹,并實(shí)現(xiàn)對(duì)該樹的搜索,插入,刪除操作(合并刪除,復(fù)制刪除)
首先我們要有一個(gè)編碼的思路,大致如下:
1、查找:根據(jù)二叉搜索樹的數(shù)據(jù)特點(diǎn),我們可以根據(jù)節(jié)點(diǎn)的值得比較來實(shí)現(xiàn)查找,查找值大于當(dāng)前節(jié)點(diǎn)時(shí)向右走,反之向左走!
2、插入:我們應(yīng)該知道,插入的全部都是葉子節(jié)點(diǎn),所以我們就需要找到要進(jìn)行插入的葉子節(jié)點(diǎn)的位置,插入的思路與查找的思路一致。
3、刪除:
1)合并刪除:一般來說會(huì)遇到以下幾種情況,被刪節(jié)點(diǎn)有左子樹沒右子樹,此時(shí)要讓當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)的左子樹;當(dāng)被刪節(jié)點(diǎn)有右子樹沒有左子樹,此時(shí)要讓當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)指向該右子樹;當(dāng)被刪節(jié)點(diǎn)即有左子樹又有右子樹時(shí),我們可以找到被刪節(jié)點(diǎn)的左子樹的最右端的節(jié)點(diǎn),然后讓這個(gè)節(jié)點(diǎn)的右或者左“指針”指向被刪節(jié)點(diǎn)的右子樹
2)復(fù)制刪除:復(fù)制刪除相對(duì)而言是比較簡(jiǎn)單的刪除操作,也是最為常用的刪除操作。大致也有以下三種情況:當(dāng)前節(jié)點(diǎn)無左子樹有右子樹時(shí),讓當(dāng)前右子樹的根節(jié)點(diǎn)替換被刪節(jié)點(diǎn);當(dāng)前節(jié)點(diǎn)無右子樹有左子樹時(shí),讓當(dāng)前左子樹的根節(jié)點(diǎn)替換被刪除節(jié)點(diǎn);當(dāng)前被刪節(jié)點(diǎn)既有左子樹又有右子樹時(shí),我們就要找到被刪節(jié)點(diǎn)的替身,可以在被刪節(jié)點(diǎn)的左子樹中找到其最右端的節(jié)點(diǎn),并讓這個(gè)節(jié)點(diǎn)的值賦給被刪節(jié)點(diǎn),然后別忘了讓此替身節(jié)點(diǎn)的父節(jié)點(diǎn)指向替身的“指針”為空,(其實(shí)在Java中無關(guān)緊要了,有垃圾處理機(jī)制自動(dòng)進(jìn)行處理)。你也可以在當(dāng)前被刪節(jié)點(diǎn)的右子樹的最左端的節(jié)點(diǎn)作為替身節(jié)點(diǎn)來實(shí)現(xiàn)這一過程。
接下來就上代碼吧。
首先是## 二叉搜索樹節(jié)點(diǎn)類 ##
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; } }
實(shí)現(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) { //采用隨機(jī)方式創(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); } } } } /* * 在二查搜索樹中進(jìn)行搜索 */ public SearchBinaryTreeNode<T> search(SearchBinaryTreeNode<T> root,T value){ SearchBinaryTreeNode<T> current=root; while((root!=null)&&(current.getData()!=value)){ //需要注意的是java中泛型無法比較大小,在實(shí)際的使用時(shí)我們可以使用常見的數(shù)據(jù)類型來替代這個(gè)泛型,這樣就不會(huì)出錯(cuò)了 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í)際的使用時(shí)我們可以使用常見的數(shù)據(jù)類型來替代這個(gè)泛型,這樣就不會(huì)出錯(cuò)了 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é)點(diǎn)沒有右子樹,用其左子樹的根節(jié)點(diǎn)來代替被刪除節(jié)點(diǎn) if(node.rightChild!=null){ node=node.leftChild; }else if(node.leftChild==null){ //若被刪節(jié)點(diǎn)沒有左子樹,用其有字?jǐn)?shù)的最左端的節(jié)點(diǎn)代替被刪除的節(jié)點(diǎn) node=node.rightChild; }else{ //如果被刪節(jié)點(diǎn)左右子樹均存在 temp=node.leftChild; while(temp.rightChild!=null){ temp=temp.rightChild; //一直查找到左子樹的右節(jié)點(diǎn) } //將查找到的節(jié)點(diǎn)的右指針賦值為被刪除節(jié)點(diǎn)的右子樹的根 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é)點(diǎn)沒有右子樹,用其左子樹的根節(jié)點(diǎn)來代替被刪除節(jié)點(diǎn) if(node.rightChild==null){ node=node.leftChild; }else if(node.leftChild==null){ node=node.rightChild; }else{ //如果被刪節(jié)點(diǎn)的左右子樹都存在 temp=node.leftChild; pre=node; while(temp.rightChild!=null){ pre=temp; temp=temp.rightChild; //遍歷查找到左子樹的最右端的節(jié)點(diǎn) } node.data=temp.data; //進(jìn)行賦值操作 if(pre==node){ pre.leftChild=node.leftChild; }else{ pre.rightChild=node.rightChild; } } temp=null; } }
測(cè)試類
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)); } }
好了,就是這樣!
以上這篇Java創(chuàng)建二叉搜索樹,實(shí)現(xiàn)搜索,插入,刪除的操作實(shí)例就是小編分享給大家的全部?jī)?nèi)容了,希望能給大家一個(gè)參考,也希望大家多多支持億速云。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。