由于最近想要閱讀下JDK1.8 中HashMap的具體實現，但是由于HashMap的實現中用到了紅黑樹，所以我覺得有必要先復習下紅黑樹的相關知識，所以寫下這篇隨筆備忘，有不對的地方請指出～
學習紅黑樹，我覺得有必要從二叉搜索樹開始學起，本篇隨筆就主要介紹Java實現二叉搜索樹的查找、插入、刪除、遍歷等內容。
二叉搜索樹需滿足以下四個條件：
若任意節點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
若任意節點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
任意節點的左、右子樹也分別為二叉查找樹；
沒有鍵值相等的節點。
二叉搜索樹舉例：
圖一
接下來將基于圖一介紹二叉搜索樹相關操作。
首先，應先有一個節點對象相關的類，命名為 Node。
|
1
2
3
4
5
6
7
8
9
10
11
12
|
class Node { int key; int value; Node leftChild; Node rightChild; public Node(int key, int value) { this.key = key; this.value = value; } public void displayNode() { }} |
Node 類中包含 key 值，用于確定節點在樹中相應位置，value 值代表要存儲的內容，還含有指向左右孩子節點的兩個引用。
接下來看下搜索樹相應的類：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Tree { Node root;//保存樹的根 public Node find(int key) {//查找指定節點 } public void insert(int key, int value) {//插入節點 } public boolean delete(int key) {//刪除指定節點 } private Node getDirectPostNode(Node delNode) {//得到待刪除節點的直接后繼節點 } public void preOrder(Node rootNode) {//先序遍歷樹 } public void inOrder(Node rootNode) {//中序遍歷樹 } public void postOrder(Node rootNode) {//后序遍歷樹 }} |
類中表示樹的框架，包含查找、插入、遍歷、刪除相應方法，其中刪除節點操作最為復雜，接下來一一介紹。
一、查找某個節點
由于二叉搜索樹定義上的特殊性，只需根據輸入的 key 值從根開始進行比較，若小于根的 key 值，則與根的左子樹比較，大于根的key值與根的右子樹比較，以此類推，找到則返回相應節點，否則返回 null。
|
1
2
3
4
5
6
7
8
9
10
11
|
public Node find(int key) { Node currentNode = root; while (currentNode != null && currentNode.key != key) { if (key < currentNode.key) { currentNode = currentNode.leftChild; } else { currentNode = currentNode.rightChild; } } return currentNode;} |
二、插入節點
與查找操作相似，由于二叉搜索樹的特殊性，待插入的節點也需要從根節點開始進行比較，小于根節點則與根節點左子樹比較，反之則與右子樹比較，直到左子樹為空或右子樹為空，則插入到相應為空的位置，在比較的過程中要注意保存父節點的信息 及 待插入的位置是父節點的左子樹還是右子樹，才能插入到正確的位置。
|
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
|
public void insert(int key, int value) { if (root == null) { root = new Node(key, value); return; } Node currentNode = root; Node parentNode = root; boolean isLeftChild = true; while (currentNode != null) { parentNode = currentNode; if (key < currentNode.key) { currentNode = currentNode.leftChild; isLeftChild = true; } else { currentNode = currentNode.rightChild; isLeftChild = false; } } Node newNode = new Node(key, value); if (isLeftChild) { parentNode.leftChild = newNode; } else { parentNode.rightChild = newNode; }} |
三、遍歷二叉搜索樹
遍歷操作與遍歷普通二叉樹操作完全相同，不贅述。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public void preOrder(Node rootNode) { if (rootNode != null) { System.out.println(rootNode.key + " " + rootNode.value); preOrder(rootNode.leftChild); preOrder(rootNode.rightChild); } }public void inOrder(Node rootNode) { if (rootNode != null) { inOrder(rootNode.leftChild); System.out.println(rootNode.key + " " + rootNode.value); inOrder(rootNode.rightChild); } }public void postOrder(Node rootNode) { if (rootNode != null) { postOrder(rootNode.leftChild); postOrder(rootNode.rightChild); System.out.println(rootNode.key + " " + rootNode.value); } } |
四、刪除指定節點。
在二叉搜索樹中刪除節點操作較復雜，可分為以下三種情況。
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
|
public boolean delete(int key) { Node currentNode = root;//用來保存待刪除節點 Node parentNode = root;//用來保存待刪除節點的父親節點 boolean isLeftChild = true;//用來確定待刪除節點是父親節點的左孩子還是右孩子 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) { return false; } if (currentNode.leftChild == null && currentNode.rightChild == null) {//要刪除的節點為葉子節點 if (currentNode == root) root = null; else if (isLeftChild) parentNode.leftChild = null; else parentNode.rightChild = null; } ...... } |
2、待刪除節點只有一個孩子節點
例如刪除圖一中的 key 值為 11 的節點，只需將 key 值為 13 的節點的左孩子指向 key 值為 12的節點即可達到刪除 key 值為 11 的節點的目的。
由以上分析可得代碼如下（接上述 delete 方法省略號后）：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
else if (currentNode.rightChild == null) {//要刪除的節點只有左孩子 if (currentNode == root) root = currentNode.leftChild; else if (isLeftChild) parentNode.leftChild = currentNode.leftChild; else parentNode.rightChild = currentNode.leftChild; } else if (currentNode.leftChild == null) {//要刪除的節點只有右孩子 if (currentNode == root) root = currentNode.rightChild; else if (isLeftChild) parentNode.leftChild = currentNode.rightChild; else parentNode.rightChild = currentNode.rightChild; } ...... |
3、待刪除節點既有左孩子，又有右孩子。
例如刪除圖一中 key 值為 10 的節點，這時就需要用 key 值為 10 的節點的中序后繼節點（節點 11）來代替 key 值為 10 的節點，并刪除 key 值為 10 的節點的中序后繼節點，由中序遍歷相關規則可知， key 值為 10 的節點的直接中序后繼節點一定是其右子樹中 key 值最小的節點，所以此中序后繼節點一定不含子節點或者只含有一個右孩子，刪除此中序后繼節點就屬于上述 1,2 所述情況。圖一中 key 值為 10 的節點的直接中序后繼節點 為 11，節點 11 含有一個右孩子 12。
所以刪除 圖一中 key 值為 10 的節點分為以下幾步：
a、找到 key 值為 10 的節點的直接中序后繼節點（即其右子樹中值最小的節點 11），并刪除此直接中序后繼節點。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
private Node getDirectPostNode(Node delNode) {//方法作用為得到待刪除節點的直接后繼節點 Node parentNode = delNode;//用來保存待刪除節點的直接后繼節點的父親節點 Node direcrPostNode = delNode;//用來保存待刪除節點的直接后繼節點 Node currentNode = delNode.rightChild; while (currentNode != null) { parentNode = direcrPostNode; direcrPostNode = currentNode; currentNode = currentNode.leftChild; } if (direcrPostNode != delNode.rightChild) {//從樹中刪除此直接后繼節點 parentNode.leftChild = direcrPostNode.rightChild; direcrPostNode.rightChild = null; } return direcrPostNode;//返回此直接后繼節點} |
b、將此后繼節點的 key、value 值賦給待刪除節點的 key，value值。(接情況二中省略號代碼之后)
|
1
2
3
4
5
6
7
|
else { //要刪除的節點既有左孩子又有右孩子 //思路：用待刪除節點右子樹中的key值最小節點的值來替代要刪除的節點的值,然后刪除右子樹中key值最小的節點 //右子樹key最小的節點一定不含左子樹,所以刪除這個key最小的節點一定是屬于葉子節點或者只有右子樹的節點 Node directPostNode = getDirectPostNode(currentNode); currentNode.key = directPostNode.key; currentNode.value = directPostNode.value;} |
至此刪除指定節點的操作結束。
最后給出完整代碼及簡單測試代碼及測試結果：
|
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
145
146
147
148
149
150
151
152
153
154
|
class Node { int key; int value; Node leftChild; Node rightChild; public Node(int key, int value) { this.key = key; this.value = value; } public void displayNode() { }}class Tree { Node root; public Node find(int key) { Node currentNode = root; while (currentNode != null && currentNode.key != key) { if (key < currentNode.key) { currentNode = currentNode.leftChild; } else { currentNode = currentNode.rightChild; } } return currentNode; } public void insert(int key, int value) { if (root == null) { root = new Node(key, value); return; } Node currentNode = root; Node parentNode = root; boolean isLeftChild = true; while (currentNode != null) { parentNode = currentNode; if (key < currentNode.key) { currentNode = currentNode.leftChild; isLeftChild = true; } else { currentNode = currentNode.rightChild; isLeftChild = false; } } Node newNode = new Node(key, value); if (isLeftChild) { parentNode.leftChild = newNode; } else { parentNode.rightChild = newNode; } } public boolean delete(int key) { Node currentNode = root; Node parentNode = root; boolean isLeftChild = true; 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) { return false; } if (currentNode.leftChild == null && currentNode.rightChild == null) { //要刪除的節點為葉子節點 if (currentNode == root) root = null; else if (isLeftChild) parentNode.leftChild = null; else parentNode.rightChild = null; } else if (currentNode.rightChild == null) {//要刪除的節點只有左孩子 if (currentNode == root) root = currentNode.leftChild; else if (isLeftChild) parentNode.leftChild = currentNode.leftChild; else parentNode.rightChild = currentNode.leftChild; } else if (currentNode.leftChild == null) {//要刪除的節點只有右孩子 if (currentNode == root) root = currentNode.rightChild; else if (isLeftChild) parentNode.leftChild = currentNode.rightChild; else parentNode.rightChild = currentNode.rightChild; } else { //要刪除的節點既有左孩子又有右孩子 //思路：用待刪除節點右子樹中的key值最小節點的值來替代要刪除的節點的值,然后刪除右子樹中key值最小的節點 //右子樹key最小的節點一定不含左子樹,所以刪除這個key最小的節點一定是屬于葉子節點或者只有右子樹的節點 Node directPostNode = getDirectPostNode(currentNode); currentNode.key = directPostNode.key; currentNode.value = directPostNode.value; } return true; } private Node getDirectPostNode(Node delNode) {//方法作用為得到待刪除節點的直接后繼節點 Node parentNode = delNode;//用來保存待刪除節點的直接后繼節點的父親節點 Node direcrPostNode = delNode;//用來保存待刪除節點的直接后繼節點 Node currentNode = delNode.rightChild; while (currentNode != null) { parentNode = direcrPostNode; direcrPostNode = currentNode; currentNode = currentNode.leftChild; } if (direcrPostNode != delNode.rightChild) {//從樹中刪除此直接后繼節點 parentNode.leftChild = direcrPostNode.rightChild; direcrPostNode.rightChild = null; } return direcrPostNode;//返回此直接后繼節點 } public void preOrder(Node rootNode) { if (rootNode != null) { System.out.println(rootNode.key + " " + rootNode.value); preOrder(rootNode.leftChild); preOrder(rootNode.rightChild); } } public void inOrder(Node rootNode) { if (rootNode != null) { inOrder(rootNode.leftChild); System.out.println("key: " + rootNode.key + " " + "value: " + rootNode.value); inOrder(rootNode.rightChild); } } public void postOrder(Node rootNode) { if (rootNode != null) { postOrder(rootNode.leftChild); postOrder(rootNode.rightChild); System.out.println(rootNode.key + " " + rootNode.value); } }}public class BinarySearchTreeApp { public static void main(String[] args) { Tree tree = new Tree(); tree.insert(6, 6);//插入操作,構造圖一所示的二叉樹 tree.insert(3, 3); tree.insert(14, 14); tree.insert(16, 16); tree.insert(10, 10); tree.insert(9, 9); tree.insert(13, 13); tree.insert(11, 11); tree.insert(12, 12); System.out.println("刪除前遍歷結果"); tree.inOrder(tree.root);//中序遍歷操作 System.out.println("刪除節點10之后遍歷結果"); tree.delete(10);//刪除操作 tree.inOrder(tree.root); }} |
測試結果：
以上就是本文的全部內容，希望本文的內容對大家的學習或者工作能帶來一定的幫助，同時也希望多多支持服務器之家！
原文鏈接：http://www.cnblogs.com/Michaelwjw/p/6384428.html
