一区二区三区在线-一区二区三区亚洲视频-一区二区三区亚洲-一区二区三区午夜-一区二区三区四区在线视频-一区二区三区四区在线免费观看

服務(wù)器之家：專注于服務(wù)器技術(shù)及軟件下載分享
分類導(dǎo)航

PHP教程|ASP.NET教程|Java教程|ASP教程|編程技術(shù)|正則表達(dá)式|C/C++|IOS|C#|Swift|Android|VB|R語言|JavaScript|易語言|vb.net|

服務(wù)器之家 - 編程語言 - Java教程 - Java 實現(xiàn)二叉搜索樹的查找、插入、刪除、遍歷

Java 實現(xiàn)二叉搜索樹的查找、插入、刪除、遍歷

2020-08-05 11:46Michaelwjw Java教程

本文主要介紹了Java實現(xiàn)二叉搜索樹的查找、插入、刪除、遍歷等內(nèi)容。具有很好的參考價值，下面跟著小編一起來看下吧

由于最近想要閱讀下JDK1.8 中HashMap的具體實現(xiàn)，但是由于HashMap的實現(xiàn)中用到了紅黑樹，所以我覺得有必要先復(fù)習(xí)下紅黑樹的相關(guān)知識，所以寫下這篇隨筆備忘，有不對的地方請指出～

學(xué)習(xí)紅黑樹，我覺得有必要從二叉搜索樹開始學(xué)起，本篇隨筆就主要介紹Java實現(xiàn)二叉搜索樹的查找、插入、刪除、遍歷等內(nèi)容。

二叉搜索樹需滿足以下四個條件：

若任意節(jié)點的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；

若任意節(jié)點的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；

任意節(jié)點的左、右子樹也分別為二叉查找樹；

沒有鍵值相等的節(jié)點。

二叉搜索樹舉例：

Java 實現(xiàn)二叉搜索樹的查找、插入、刪除、遍歷

圖一

接下來將基于圖一介紹二叉搜索樹相關(guān)操作。

首先，應(yīng)先有一個節(jié)點對象相關(guān)的類，命名為 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 值，用于確定節(jié)點在樹中相應(yīng)位置，value 值代表要存儲的內(nèi)容，還含有指向左右孩子節(jié)點的兩個引用。

接下來看下搜索樹相應(yīng)的類：

?
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) {//查找指定節(jié)點
 }
 public void insert(int key, int value) {//插入節(jié)點
 }
 public boolean delete(int key) {//刪除指定節(jié)點
 }
 private Node getDirectPostNode(Node delNode) {//得到待刪除節(jié)點的直接后繼節(jié)點
 }
 public void preOrder(Node rootNode) {//先序遍歷樹
 }
 public void inOrder(Node rootNode) {//中序遍歷樹
 }
 public void postOrder(Node rootNode) {//后序遍歷樹
 }
}

類中表示樹的框架，包含查找、插入、遍歷、刪除相應(yīng)方法，其中刪除節(jié)點操作最為復(fù)雜，接下來一一介紹。

一、查找某個節(jié)點

由于二叉搜索樹定義上的特殊性，只需根據(jù)輸入的 key 值從根開始進(jìn)行比較，若小于根的 key 值，則與根的左子樹比較，大于根的key值與根的右子樹比較，以此類推，找到則返回相應(yīng)節(jié)點，否則返回 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;
}

二、插入節(jié)點

與查找操作相似，由于二叉搜索樹的特殊性，待插入的節(jié)點也需要從根節(jié)點開始進(jìn)行比較，小于根節(jié)點則與根節(jié)點左子樹比較，反之則與右子樹比較，直到左子樹為空或右子樹為空，則插入到相應(yīng)為空的位置，在比較的過程中要注意保存父節(jié)點的信息 及 待插入的位置是父節(jié)點的左子樹還是右子樹，才能插入到正確的位置。

?
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);
 }
 }

四、刪除指定節(jié)點。

在二叉搜索樹中刪除節(jié)點操作較復(fù)雜，可分為以下三種情況。

1、待刪除的節(jié)點為葉子節(jié)點，可直接刪除。

?
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;//用來保存待刪除節(jié)點
 Node parentNode = root;//用來保存待刪除節(jié)點的父親節(jié)點
 boolean isLeftChild = true;//用來確定待刪除節(jié)點是父親節(jié)點的左孩子還是右孩子
 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) {//要刪除的節(jié)點為葉子節(jié)點
 if (currentNode == root)
 root = null;
 else if (isLeftChild)
 parentNode.leftChild = null;
 else
 parentNode.rightChild = null;
 }
 ......
 }

2、待刪除節(jié)點只有一個孩子節(jié)點

例如刪除圖一中的 key 值為 11 的節(jié)點，只需將 key 值為 13 的節(jié)點的左孩子指向 key 值為 12的節(jié)點即可達(dá)到刪除 key 值為 11 的節(jié)點的目的。

由以上分析可得代碼如下（接上述 delete 方法省略號后）：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
else if (currentNode.rightChild == null) {//要刪除的節(jié)點只有左孩子
 if (currentNode == root)
 root = currentNode.leftChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.leftChild;
 else
 parentNode.rightChild = currentNode.leftChild;
 } else if (currentNode.leftChild == null) {//要刪除的節(jié)點只有右孩子
 if (currentNode == root)
 root = currentNode.rightChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.rightChild;
 else
 parentNode.rightChild = currentNode.rightChild;
 }
 ......

3、待刪除節(jié)點既有左孩子，又有右孩子。

例如刪除圖一中 key 值為 10 的節(jié)點，這時就需要用 key 值為 10 的節(jié)點的中序后繼節(jié)點（節(jié)點 11）來代替 key 值為 10 的節(jié)點，并刪除 key 值為 10 的節(jié)點的中序后繼節(jié)點，由中序遍歷相關(guān)規(guī)則可知， key 值為 10 的節(jié)點的直接中序后繼節(jié)點一定是其右子樹中 key 值最小的節(jié)點，所以此中序后繼節(jié)點一定不含子節(jié)點或者只含有一個右孩子，刪除此中序后繼節(jié)點就屬于上述 1,2 所述情況。圖一中 key 值為 10 的節(jié)點的直接中序后繼節(jié)點 為 11，節(jié)點 11 含有一個右孩子 12。

所以刪除 圖一中 key 值為 10 的節(jié)點分為以下幾步：

a、找到 key 值為 10 的節(jié)點的直接中序后繼節(jié)點（即其右子樹中值最小的節(jié)點 11），并刪除此直接中序后繼節(jié)點。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private Node getDirectPostNode(Node delNode) {//方法作用為得到待刪除節(jié)點的直接后繼節(jié)點
 Node parentNode = delNode;//用來保存待刪除節(jié)點的直接后繼節(jié)點的父親節(jié)點
 Node direcrPostNode = delNode;//用來保存待刪除節(jié)點的直接后繼節(jié)點
 Node currentNode = delNode.rightChild;
 while (currentNode != null) {
 parentNode = direcrPostNode;
 direcrPostNode = currentNode;
 currentNode = currentNode.leftChild;
 }
 if (direcrPostNode != delNode.rightChild) {//從樹中刪除此直接后繼節(jié)點
 parentNode.leftChild = direcrPostNode.rightChild;
 direcrPostNode.rightChild = null;
 }
 return direcrPostNode;//返回此直接后繼節(jié)點
}

b、將此后繼節(jié)點的 key、value 值賦給待刪除節(jié)點的 key，value值。(接情況二中省略號代碼之后)

?
1
2
3
4
5
6
7
else { //要刪除的節(jié)點既有左孩子又有右孩子
 //思路：用待刪除節(jié)點右子樹中的key值最小節(jié)點的值來替代要刪除的節(jié)點的值,然后刪除右子樹中key值最小的節(jié)點
 //右子樹key最小的節(jié)點一定不含左子樹,所以刪除這個key最小的節(jié)點一定是屬于葉子節(jié)點或者只有右子樹的節(jié)點
 Node directPostNode = getDirectPostNode(currentNode);
 currentNode.key = directPostNode.key;
 currentNode.value = directPostNode.value;
}

至此刪除指定節(jié)點的操作結(jié)束。

最后給出完整代碼及簡單測試代碼及測試結(jié)果：

?
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) {
 //要刪除的節(jié)點為葉子節(jié)點
 if (currentNode == root)
 root = null;
 else if (isLeftChild)
 parentNode.leftChild = null;
 else
 parentNode.rightChild = null;
 } else if (currentNode.rightChild == null) {//要刪除的節(jié)點只有左孩子
 if (currentNode == root)
 root = currentNode.leftChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.leftChild;
 else
 parentNode.rightChild = currentNode.leftChild;
 } else if (currentNode.leftChild == null) {//要刪除的節(jié)點只有右孩子
 if (currentNode == root)
 root = currentNode.rightChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.rightChild;
 else
 parentNode.rightChild = currentNode.rightChild;
 } else { //要刪除的節(jié)點既有左孩子又有右孩子
 //思路：用待刪除節(jié)點右子樹中的key值最小節(jié)點的值來替代要刪除的節(jié)點的值,然后刪除右子樹中key值最小的節(jié)點
 //右子樹key最小的節(jié)點一定不含左子樹,所以刪除這個key最小的節(jié)點一定是屬于葉子節(jié)點或者只有右子樹的節(jié)點
 Node directPostNode = getDirectPostNode(currentNode);
 currentNode.key = directPostNode.key;
 currentNode.value = directPostNode.value;
 }
 return true;
 }
 private Node getDirectPostNode(Node delNode) {//方法作用為得到待刪除節(jié)點的直接后繼節(jié)點
 Node parentNode = delNode;//用來保存待刪除節(jié)點的直接后繼節(jié)點的父親節(jié)點
 Node direcrPostNode = delNode;//用來保存待刪除節(jié)點的直接后繼節(jié)點
 Node currentNode = delNode.rightChild;
 while (currentNode != null) {
 parentNode = direcrPostNode;
 direcrPostNode = currentNode;
 currentNode = currentNode.leftChild;
 }
 if (direcrPostNode != delNode.rightChild) {//從樹中刪除此直接后繼節(jié)點
 parentNode.leftChild = direcrPostNode.rightChild;
 direcrPostNode.rightChild = null;
 }
 return direcrPostNode;//返回此直接后繼節(jié)點
 }
 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);//插入操作,構(gòu)造圖一所示的二叉樹
 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("刪除前遍歷結(jié)果");
 tree.inOrder(tree.root);//中序遍歷操作
 System.out.println("刪除節(jié)點10之后遍歷結(jié)果");
 tree.delete(10);//刪除操作
 tree.inOrder(tree.root);
 }
}

測試結(jié)果：

Java 實現(xiàn)二叉搜索樹的查找、插入、刪除、遍歷

以上就是本文的全部內(nèi)容，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作能帶來一定的幫助，同時也希望多多支持服務(wù)器之家！

原文鏈接：http://www.cnblogs.com/Michaelwjw/p/6384428.html

延伸 · 閱讀

精彩推薦
主站蜘蛛池模板： 亚洲麻豆精品 | 被老头肉至怀孕小说 | 五月天国产视频 | 四虎影视地址 | 国产免费美女视频 | 星空无限传媒xk8129 | 国产精品一区久久精品 | 91porny丨首页 | 精品一区二区三区在线播放 | h日本漫画全彩在线观看 | 538亚洲欧美国产日韩在线精品 | 日本三级做a全过程在线观看 | 91日本在线 | 草草精品视频 | 男女一级特黄a大片 | 九色PORNY丨视频入口 | 日本在线观看视频网站 | 国产精品久久免费 | 成人区精品一区二区毛片不卡 | 窝窝午夜精品一区二区 | 成人福利在线视频免费观看 | 韩国三级在线播放 | 特大黑人娇小亚洲女mp4 | 7个黑人玩北条麻妃 | 亚洲高清中文字幕一区二区三区 | 秋霞色 | 免费看视频高清在线观看 | 美妇在男人胯下哀求 | 国产成人精品一区二三区2022 | 精品suv一区二区三区 | 99热精品在线免费观看 | 国产精品合集一区二区 | 7mav视频| 黄蓉h系列| 日韩在线1 | 亚洲精品AV无码喷奶水糖心 | 欧美高清免费一级在线 | 日韩porn | 激情视频亚洲 | 美女69xx| 2021久久|