一、概念
二叉搜索樹也成二叉排序樹，它有這么一個特點，某個節(jié)點，若其有兩個子節(jié)點，則一定滿足，左子節(jié)點值一定小于該節(jié)點值，右子節(jié)點值一定大于該節(jié)點值，對于非基本類型的比較，可以實現(xiàn)comparator接口，在本文中為了方便，采用了int類型數(shù)據(jù)進行操作。
要想實現(xiàn)一顆二叉樹，肯定得從它的增加說起，只有把樹構(gòu)建出來了，才能使用其他操作。
二、二叉搜索樹構(gòu)建
談起二叉樹的增加，肯定先得構(gòu)建一個表示節(jié)點的類，該節(jié)點的類，有這么幾個屬性，節(jié)點的值，節(jié)點的父節(jié)點、左節(jié)點、右節(jié)點這四個屬性，代碼如下
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
static class node{ node parent; node leftchild; node rightchild; int val; public node(node parent, node leftchild, node rightchild,int val) { super(); this.parent = parent; this.leftchild = leftchild; this.rightchild = rightchild; this.val = val; } public node(int val){ this(null,null,null,val); } public node(node node,int val){ this(node,null,null,val); } } |
這里采用的是內(nèi)部類的寫法，構(gòu)建完節(jié)點值后，再對整棵樹去構(gòu)建，一棵樹，先得有根節(jié)點，再能延伸到余下子節(jié)點，那在這棵樹里，也有一些屬性，比如基本的根節(jié)點root,樹中元素大小size，這兩個屬性，如果采用了泛型，可能還得增加comparator屬性，或提供其一個默認(rèn)實現(xiàn)。具體代碼如下
|
1
2
3
4
5
6
7
|
public class searchbinarytree { private node root; private int size; public searchbinarytree() { super(); }} |
三、增加
當(dāng)要進行添加元素的時候，得考慮根節(jié)點的初始化，一般情況有兩種、當(dāng)該類的構(gòu)造函數(shù)一初始化就對根節(jié)點root進行初始化，第二種、在進行第一次添加元素的時候，對根節(jié)點進行添加。理論上兩個都可以行得通，但通常采用的是第二種懶加載形式。
在進行添加元素的時候，有這樣幾種情況需要考慮
一、添加時判斷root是否初始化，若沒初始化，則初始化，將該值賦給根節(jié)點，size加一。
二、因為二叉樹搜索樹滿足根節(jié)點值大于左節(jié)點，小于右節(jié)點，需要將插入的值，先同根節(jié)點比較，若大，則往右子樹中進行查找，若小，則往左子樹中進行查找。直到某個子節(jié)點。
這里的插入實現(xiàn)，可以采用兩種，一、遞歸、二、迭代(即通過while循環(huán)模式)。
3.1、遞歸版本插入
|
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
|
public boolean add(int val){ if(root == null){ root = new node(val); size++; return true; } node node = getadapternode(root, val); node newnode = new node(val); if(node.val > val){ node.leftchild = newnode; newnode.parent = node; }else if(node.val < val){ node.rightchild = newnode; newnode.parent = node; }else{ // 暫不做處理 } size++;19 return true; } /** * 獲取要插入的節(jié)點的父節(jié)點，該父節(jié)點滿足以下幾種狀態(tài)之一 * 1、父節(jié)點為子節(jié)點 * 2、插入節(jié)點值比父節(jié)點小，但父節(jié)點沒有左子節(jié)點 * 3、插入節(jié)點值比父節(jié)點大，但父節(jié)點沒有右子節(jié)點 * 4、插入節(jié)點值和父節(jié)點相等。 * 5、父節(jié)點為空 * 如果滿足以上5種情況之一，則遞歸停止。 * @param node * @param val * @return */ private node getadapternode(node node,int val){ if(node == null){ return node; } // 往左子樹中插入，但沒左子樹，則返回 if(node.val > val && node.leftchild == null){ return node; } // 往右子樹中插入，但沒右子樹，也返回 if(node.val < val && node.rightchild == null){ return node; } // 該節(jié)點是葉子節(jié)點，則返回 if(node.leftchild == null && node.rightchild == null){ return node; } if(node.val > val && node.leftchild != null){ return getadaptarnode(node.leftchild, val); }else if(node.val < val && node.rightchild != null){ return getadaptarnode(node.rightchild, val); }else{ return node; } } |
使用遞歸，先找到遞歸的結(jié)束點，再去把整個問題化為子問題，在上述代碼里，邏輯大致是這樣的，先判斷根節(jié)點有沒有初始化，沒初始化則初始化，完成后返回，之后通過一個函數(shù)去獲取適配的節(jié)點。之后進行插入值。
3.2、迭代版本
|
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
|
public boolean put(int val){ return putval(root,val); } private boolean putval(node node,int val){ if(node == null){// 初始化根節(jié)點 node = new node(val); root = node; size++; return true; } node temp = node; node p; int t; /** * 通過do while循環(huán)迭代獲取最佳節(jié)點， */ do{ p = temp; t = temp.val-val; if(t > 0){ temp = temp.leftchild; }else if(t < 0){ temp = temp.rightchild; }else{ temp.val = val; return false; } }while(temp != null); node newnode = new node(p, val); if(t > 0){ p.leftchild = newnode; }else if(t < 0){ p.rightchild = newnode; } size++; return true; } |
原理其實和遞歸一樣，都是獲取最佳節(jié)點，在該節(jié)點上進行操作。
論起性能，肯定迭代版本最佳，所以一般情況下，都是選擇迭代版本進行操作數(shù)據(jù)。
四、刪除
可以說在二叉搜索樹的操作中，刪除是最復(fù)雜的，要考慮的情況也相對多，在常規(guī)思路中，刪除二叉搜索樹的某一個節(jié)點，肯定會想到以下四種情況,
1、要刪除的節(jié)點沒有左右子節(jié)點，如上圖的d、e、g節(jié)點
2、要刪除的節(jié)點只有左子節(jié)點，如b節(jié)點
3、要刪除的節(jié)點只有右子節(jié)點，如f節(jié)點
4、要刪除的節(jié)點既有左子節(jié)點，又有右子節(jié)點，如 a、c節(jié)點
對于前面三種情況，可以說是比較簡單，第四種復(fù)雜了。下面先來分析第一種
若是這種情況，比如 刪除d節(jié)點，則可以將b節(jié)點的左子節(jié)點設(shè)置為null，若刪除g節(jié)點，則可將f節(jié)點的右子節(jié)點設(shè)置為null。具體要設(shè)置哪一邊，看刪除的節(jié)點位于哪一邊。
第二種，刪除b節(jié)點，則只需將a節(jié)點的左節(jié)點設(shè)置成d節(jié)點，將d節(jié)點的父節(jié)點設(shè)置成a即可。具體設(shè)置哪一邊，也是看刪除的節(jié)點位于父節(jié)點的哪一邊。
第三種，同第二種。
第四種，也就是之前說的有點復(fù)雜，比如要刪除c節(jié)點，將f節(jié)點的父節(jié)點設(shè)置成a節(jié)點，f節(jié)點左節(jié)點設(shè)置成e節(jié)點，將a的右節(jié)點設(shè)置成f，e的父節(jié)點設(shè)置f節(jié)點(也就是將f節(jié)點替換c節(jié)點)，還有一種，直接將e節(jié)點替換c節(jié)點。那采用哪一種呢，如果刪除節(jié)點為根節(jié)點，又該怎么刪除？
對于第四種情況，可以這樣想，找到c或者a節(jié)點的后繼節(jié)點，刪除后繼節(jié)點，且將后繼節(jié)點的值設(shè)置為c或a節(jié)點的值。先來補充下后繼節(jié)點的概念。
一個節(jié)點在整棵樹中的后繼節(jié)點必滿足，大于該節(jié)點值得所有節(jié)點集合中值最小的那個節(jié)點，即為后繼節(jié)點，當(dāng)然，也有可能不存在后繼節(jié)點。
但是對于第四種情況，后繼節(jié)點一定存在，且一定在其右子樹中，而且還滿足，只有一個子節(jié)點或者沒有子節(jié)點兩者情況之一。具體原因可以這樣想，因為后繼節(jié)點要比c節(jié)點大，又因為c節(jié)點左右子節(jié)一定存在，所以一定存在右子樹中的左子節(jié)點中。就比如c的后繼節(jié)點是f，a的后繼節(jié)點是e。
有了以上分析，那么實現(xiàn)也比較簡單了，代碼如下
|
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
|
public boolean delete(int val){ node node = getnode(val); if(node == null){ return false; } node parent = node.parent; node leftchild = node.leftchild; node rightchild = node.rightchild; //以下所有父節(jié)點為空的情況，則表明刪除的節(jié)點是根節(jié)點 if(leftchild == null && rightchild == null){//沒有子節(jié)點 if(parent != null){ if(parent.leftchild == node){ parent.leftchild = null; }else if(parent.rightchild == node){ parent.rightchild = null; } }else{//不存在父節(jié)點，則表明刪除節(jié)點為根節(jié)點 root = null; } node = null; return true; }else if(leftchild == null && rightchild != null){// 只有右節(jié)點 if(parent != null && parent.val > val){// 存在父節(jié)點，且node位置為父節(jié)點的左邊 parent.leftchild = rightchild; }else if(parent != null && parent.val < val){// 存在父節(jié)點，且node位置為父節(jié)點的右邊 parent.rightchild = rightchild; }else{ root = rightchild; } node = null; return true; }else if(leftchild != null && rightchild == null){// 只有左節(jié)點 if(parent != null && parent.val > val){// 存在父節(jié)點，且node位置為父節(jié)點的左邊 parent.leftchild = leftchild; }else if(parent != null && parent.val < val){// 存在父節(jié)點，且node位置為父節(jié)點的右邊 parent.rightchild = leftchild; }else{ root = leftchild; } return true; }else if(leftchild != null && rightchild != null){// 兩個子節(jié)點都存在 node successor = getsuccessor(node);// 這種情況，一定存在后繼節(jié)點 int temp = successor.val; boolean delete = delete(temp); if(delete){ node.val = temp; } successor = null; return true; } return false; } /** * 找到node節(jié)點的后繼節(jié)點 * 1、先判斷該節(jié)點有沒有右子樹，如果有，則從右節(jié)點的左子樹中尋找后繼節(jié)點，沒有則進行下一步 * 2、查找該節(jié)點的父節(jié)點，若該父節(jié)點的右節(jié)點等于該節(jié)點，則繼續(xù)尋找父節(jié)點， * 直至父節(jié)點為null或找到不等于該節(jié)點的右節(jié)點。 * 理由，后繼節(jié)點一定比該節(jié)點大，若存在右子樹，則后繼節(jié)點一定存在右子樹中，這是第一步的理由 * 若不存在右子樹，則也可能存在該節(jié)點的某個祖父節(jié)點(即該節(jié)點的父節(jié)點，或更上層父節(jié)點)的右子樹中， * 對其迭代查找，若有，則返回該節(jié)點，沒有則返回null * @param node * @return */ private node getsuccessor(node node){ if(node.rightchild != null){ node rightchild = node.rightchild; while(rightchild.leftchild != null){ rightchild = rightchild.leftchild; } return rightchild; } node parent = node.parent; while(parent != null && (node == parent.rightchild)){ node = parent; parent = parent.parent; } return parent; } |
具體邏輯，看上面分析，這里不作文字?jǐn)⑹隽耍?/p>
除了這種實現(xiàn)，在算法導(dǎo)論書中，提供了另外一種實現(xiàn)。
|
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
|
public boolean remove(int val){ node node = getnode(val); if(node == null){ return false; } if(node.leftchild == null){// 1、左節(jié)點不存在，右節(jié)點可能存在，包含兩種情況 ，兩個節(jié)點都不存在和只存在右節(jié)點 transplant(node, node.rightchild); }else if(node.rightchild == null){//2、左孩子存在，右節(jié)點不存在 transplant(node, node.leftchild); }else{// 3、兩個節(jié)點都存在 node successor = getsuccessor(node);// 得到node后繼節(jié)點 if(successor.parent != node){// 后繼節(jié)點存在node的右子樹中。 transplant(successor, successor.rightchild);// 用后繼節(jié)點的右子節(jié)點替換該后繼節(jié)點 successor.rightchild = node.rightchild;// 將node節(jié)點的右子樹賦給后繼節(jié)點的右節(jié)點，即類似后繼與node節(jié)點調(diào)換位置 successor.rightchild.parent = successor;// 接著上一步 給接過來的右節(jié)點的父引用復(fù)制 } transplant(node, successor); successor.leftchild = node.leftchild; successor.leftchild.parent = successor; } return true; } /** * 將child節(jié)點替換node節(jié)點 * @param root 根節(jié)點 * @param node 要刪除的節(jié)點 * @param child node節(jié)點的子節(jié)點 */ private void transplant(node node,node child){ /** * 1、先判斷 node是否存在父節(jié)點 * 1、不存在，則child替換為根節(jié)點 * 2、存在，則繼續(xù)下一步 * 2、判斷node節(jié)點是父節(jié)點的那個孩子(即判斷出 node是右節(jié)點還是左節(jié)點)， * 得出結(jié)果后，將child節(jié)點替換node節(jié)點 ，即若node節(jié)點是左節(jié)點 則child替換后 也為左節(jié)點，否則為右節(jié)點 * 3、將node節(jié)點的父節(jié)點置為child節(jié)點的父節(jié)點 */ if(node.parent == null){ this.root = child; }else if(node.parent.leftchild == node){ node.parent.leftchild = child; }else if(node.parent.rightchild == node){ node.parent.rightchild = child; } if(child != null){ child.parent = node.parent; } } |
五、查找
查找也比較簡單，其實在增加的時候，已經(jīng)實現(xiàn)了。實際情況中，這部分可以抽出來單獨方法。代碼如下
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public node getnode(int val){ node temp = root; int t; do{ t = temp.val-val; if(t > 0){ temp = temp.leftchild; }else if(t < 0){ temp = temp.rightchild; }else{ return temp; } }while(temp != null); return null; } |
六、二叉搜索樹遍歷
在了解二叉搜索樹的性質(zhì)后，很清楚的知道，它的中序遍歷是從小到大依次排列的，這里提供中序遍歷代碼
|
1
2
3
4
5
6
7
8
9
10
|
public void print(){ print(root); } private void print(node root){ if(root != null){ print(root.leftchild); system.out.println(root.val);// 位置在中間，則中序，若在前面，則為先序，否則為后續(xù) print(root.rightchild); } } |
總結(jié)
以上所述是小編給大家介紹的java實現(xiàn) 二叉搜索樹功能，希望對大家有所幫助，如果大家有任何疑問歡迎給我留言，小編會及時回復(fù)大家的！
原文鏈接：https://www.cnblogs.com/qm-article/p/9279655.html
