-
Notifications
You must be signed in to change notification settings - Fork 0
/
BinarySearchTree.java
130 lines (110 loc) · 3.88 KB
/
BinarySearchTree.java
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
public class BinarySearchTree {
Node root = null;
public void add(int key) {
Node newNode = new Node();
newNode.key = key;
if (root == null) {
root = newNode;
} else {
root = addNode(root, newNode);
}
}
private Node addNode(Node node, Node newNode) {
if (node == null)
return newNode;
else if (node.key > newNode.key)
node.left = addNode(node.left, newNode);
else
node.right = addNode(node.right, newNode);
return node;
}
public void remove(int key) {
root = removeNode(root, key);
}
private Node removeNode(Node node, int key) {
if (node == null)
throw new RuntimeException("해당 값을 가진 노드를 찾을 수 없습니다.");
if (node.key > key)
node.left = removeNode(node.left, key);
else if (node.key < key) {
node.right = removeNode(node.right, key);
} else {
//삭제할 노드를 찾은 경우
if (node.left != null) {
//왼쪽 서브트리에서 가장 오른쪽에 있는 값 찾아 대체하기
Node child = findMaxNode(node.left);
int removedKey = node.key;
node.key = child.key;
child.key = removedKey;
//다시 옮겨진 위치에서 서브트리에 대해 재귀적으로 실행
node.left = removeNode(node.left, key);
} else if (node.right != null) {
//오른족 서브트리에서 가장 왼쪽에 있는 값 찾아 대체하기
Node child = findMinNode(node.right);
int removedKey = node.key;
node.key = child.key;
child.key = removedKey;
//다시 옮겨진 위치에서 서브트리에 대해 재귀적으로 실행
node.right = removeNode(node.right, key);
} else {
//삭제할 노드가 단말 노드인 경우 부모 노드와의 연결 종료
return null;
}
}
return node;
}
private Node findMaxNode(Node node) {
if (node.right == null)
return node;
else
return findMaxNode(node.right);
}
private Node findMinNode(Node node) {
if (node.left == null)
return node;
else
return findMinNode(node.left);
}
public void search(int key) {
searchNode(root, key);
}
private Node searchNode(Node node, int key) {
if (node == null)
throw new RuntimeException("해당 값을 가진 노드를 찾을 수 없습니다.");
if (node.key > key)
node.right = searchNode(node.right, key);
else if (node.key < key)
node.left = searchNode(node.left, key);
else
System.out.println("해당 값을 가진 노드를 찾았습니다.");
return node;
}
public void descendingTraversal() {
//내림차순 순회
System.out.print("내림차순 순회: ");
rightInorderTraversal(root);
System.out.println();
}
private void rightInorderTraversal(Node node){
//우측 중위 순회
if(node == null)
return;
rightInorderTraversal(node.right);
System.out.printf("%d ", node.key);
rightInorderTraversal(node.left);
}
public void ascendingTraversal() {
//오름차순 순회
System.out.print("오름차순 순회: ");
leftInorderTraversal(root);
System.out.println();
}
private void leftInorderTraversal(Node node) {
//좌측 중위 순회
if(node == null)
return;
leftInorderTraversal(node.left);
System.out.printf("%d ", node.key);
leftInorderTraversal(node.right);
}
}