5639번: 이진 검색 트리
트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다
www.acmicpc.net
자바로 트리를 처음 구현해보았습니다..
입력이 전위순회이므로 들어오는 대로 트리에 넣어줍니다.
이진 검색 트리는 x가 들어오면 트리의 루트노드의 값부터 비교를 합니다.
노드의 값보다 작으면 왼쪽 서브트리이고,
노드의 값보다 크면 오른쪽 서브트리로 이동하면 되고
이동하려는 서브트리가 null이면 그곳에 newnode를 삽입하면 됩니다.
출력은 후위순회로 출력입니다.
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuffer sb = new StringBuffer();
static class tree {
int x;
tree llink;
tree rlink;
tree() {
}
tree(int x, tree llink, tree rlink) {
this.x = x;
this.llink = llink;
this.rlink = rlink;
}
}
static tree node = new tree();
static void addnode(int x) {
tree newnode = new tree(x, null, null);
if (node.x == 0) {
node.x = x;
return;
}
tree p = node;
while (p != null) {
if (p.x > x) {
if (p.llink == null) {
p.llink = newnode;
break;
} else
p = p.llink;
} else {
if (p.rlink == null) {
p.rlink = newnode;
break;
} else
p = p.rlink;
}
}
}
static void postorder(tree t) {
if (t.llink != null)
postorder(t.llink);
if (t.rlink != null)
postorder(t.rlink);
sb.append(t.x + "\n");
}
static void input() throws Exception {
String st;
while (true) {
st = br.readLine();
if (st == null || st.length() == 0)
break;
int x = Integer.parseInt(st);
addnode(x);
}
}
public static void main(String[] args) throws Exception {
input();
postorder(node);
System.out.println(sb.toString());
}
}
|
cs |
'algorithm > data-structure' 카테고리의 다른 글
| boj 17298 오큰수 (0) | 2021.01.25 |
|---|---|
| boj 4358 생태학 (0) | 2021.01.25 |
| boj 1991 트리 순회 (0) | 2021.01.22 |
| boj 11003 최솟값 찾기 (0) | 2021.01.22 |
| boj 1517 버블 소트 (0) | 2021.01.22 |