Java實(shí)現(xiàn)的二叉搜索樹(shù)，并實(shí)現(xiàn)對(duì)該樹(shù)的搜索，插入，刪除操作（合并刪除，復(fù)制刪除）
首先我們要有一個(gè)編碼的思路，大致如下：
1、查找：根據(jù)二叉搜索樹(shù)的數(shù)據(jù)特點(diǎn)，我們可以根據(jù)節(jié)點(diǎn)的值得比較來(lái)實(shí)現(xiàn)查找，查找值大于當(dāng)前節(jié)點(diǎn)時(shí)向右走，反之向左走！
2、插入：我們應(yīng)該知道，插入的全部都是葉子節(jié)點(diǎn)，所以我們就需要找到要進(jìn)行插入的葉子節(jié)點(diǎn)的位置，插入的思路與查找的思路一致。
3、刪除：
1）合并刪除：一般來(lái)說(shuō)會(huì)遇到以下幾種情況，被刪節(jié)點(diǎn)有左子樹(shù)沒(méi)右子樹(shù)，此時(shí)要讓當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)的左子樹(shù)；當(dāng)被刪節(jié)點(diǎn)有右子樹(shù)沒(méi)有左子樹(shù)，此時(shí)要讓當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)指向該右子樹(shù)；當(dāng)被刪節(jié)點(diǎn)即有左子樹(shù)又有右子樹(shù)時(shí)，我們可以找到被刪節(jié)點(diǎn)的左子樹(shù)的最右端的節(jié)點(diǎn)，然后讓這個(gè)節(jié)點(diǎn)的右或者左“指針”指向被刪節(jié)點(diǎn)的右子樹(shù)
2）復(fù)制刪除：復(fù)制刪除相對(duì)而言是比較簡(jiǎn)單的刪除操作，也是最為常用的刪除操作。大致也有以下三種情況：當(dāng)前節(jié)點(diǎn)無(wú)左子樹(shù)有右子樹(shù)時(shí)，讓當(dāng)前右子樹(shù)的根節(jié)點(diǎn)替換被刪節(jié)點(diǎn)；當(dāng)前節(jié)點(diǎn)無(wú)右子樹(shù)有左子樹(shù)時(shí)，讓當(dāng)前左子樹(shù)的根節(jié)點(diǎn)替換被刪除節(jié)點(diǎn)；當(dāng)前被刪節(jié)點(diǎn)既有左子樹(shù)又有右子樹(shù)時(shí)，我們就要找到被刪節(jié)點(diǎn)的替身，可以在被刪節(jié)點(diǎn)的左子樹(shù)中找到其最右端的節(jié)點(diǎn)，并讓這個(gè)節(jié)點(diǎn)的值賦給被刪節(jié)點(diǎn)，然后別忘了讓此替身節(jié)點(diǎn)的父節(jié)點(diǎn)指向替身的“指針”為空，（其實(shí)在Java中無(wú)關(guān)緊要了，有垃圾處理機(jī)制自動(dòng)進(jìn)行處理）。你也可以在當(dāng)前被刪節(jié)點(diǎn)的右子樹(shù)的最左端的節(jié)點(diǎn)作為替身節(jié)點(diǎn)來(lái)實(shí)現(xiàn)這一過(guò)程。
接下來(lái)就上代碼吧。
首先是## 二叉搜索樹(shù)節(jié)點(diǎn)類(lèi) ##
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
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)二叉搜索樹(shù)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
|
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)造一顆二叉樹(shù) */ public void CreateTree(SearchBinaryTreeNode<T> node, T data) { if (root == null) { root = new SearchBinaryTreeNode<T>(); } else { if (Math.random() > 0.5) { //采用隨機(jī)方式創(chuàng)建二叉樹(shù) 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); } } } } /* * 在二查搜索樹(shù)中進(jìn)行搜索 */ public SearchBinaryTreeNode<T> search(SearchBinaryTreeNode<T> root,T value){ SearchBinaryTreeNode<T> current=root; while((root!=null)&&(current.getData()!=value)){ //需要注意的是java中泛型無(wú)法比較大小，在實(shí)際的使用時(shí)我們可以使用常見(jiàn)的數(shù)據(jù)類(lèi)型來(lái)替代這個(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中泛型無(wú)法比較大小，在實(shí)際的使用時(shí)我們可以使用常見(jiàn)的數(shù)據(jù)類(lèi)型來(lái)替代這個(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)沒(méi)有右子樹(shù),用其左子樹(shù)的根節(jié)點(diǎn)來(lái)代替被刪除節(jié)點(diǎn) if(node.rightChild!=null){ node=node.leftChild; }else if(node.leftChild==null){ //若被刪節(jié)點(diǎn)沒(méi)有左子樹(shù)，用其有字?jǐn)?shù)的最左端的節(jié)點(diǎn)代替被刪除的節(jié)點(diǎn) node=node.rightChild; }else{ //如果被刪節(jié)點(diǎn)左右子樹(shù)均存在 temp=node.leftChild; while(temp.rightChild!=null){ temp=temp.rightChild; //一直查找到左子樹(shù)的右節(jié)點(diǎn) } //將查找到的節(jié)點(diǎn)的右指針賦值為被刪除節(jié)點(diǎn)的右子樹(shù)的根 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)沒(méi)有右子樹(shù)，用其左子樹(shù)的根節(jié)點(diǎn)來(lái)代替被刪除節(jié)點(diǎn) if(node.rightChild==null){ node=node.leftChild; }else if(node.leftChild==null){ node=node.rightChild; }else{ //如果被刪節(jié)點(diǎn)的左右子樹(shù)都存在 temp=node.leftChild; pre=node; while(temp.rightChild!=null){ pre=temp; temp=temp.rightChild; //遍歷查找到左子樹(shù)的最右端的節(jié)點(diǎn) } node.data=temp.data; //進(jìn)行賦值操作 if(pre==node){ pre.leftChild=node.leftChild; }else{ pre.rightChild=node.rightChild; } } temp=null; }} |
測(cè)試類(lèi)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
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ù),實(shí)現(xiàn)搜索,插入,刪除的操作實(shí)例就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持服務(wù)器之家。
原文鏈接：http://blog.csdn.net/Marksinoberg/article/details/49951313
