-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTree.java
More file actions
113 lines (97 loc) · 2.9 KB
/
Copy pathTree.java
File metadata and controls
113 lines (97 loc) · 2.9 KB
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
package algorithm.module;
public class Tree {
/*
2진트리와 그 외 트리가 존재
트리란?
- 계층 구조를 가지고 있는 자료구조
- 그 외 트리의 특징은?
- 사이클이 없다
- 노드, 루트노드, 잎노드, 높이, 서브트리(재귀적 구조)
트리의 추가 제거, 좌측노드 우측노드
- 우선순위 큐일 경우 추가할때 정렬함
트리의 정렬(우선순위 큐)
트리의 탐색(왼쪽우선 오른쪽우선 중심노드 우선)
*/
TreeNode root;
//삽입
public void insert(int value){
root = insertRecursive(root, value);
}
private TreeNode insertRecursive(TreeNode node, int value) {
if (node == null){
return new TreeNode(value);
}
if(value < node.getValue()) {
node.setLeft(insertRecursive(node.getLeft(), value));
} else if (value > node.getValue()) {
node.setRight(insertRecursive(node.getRight(), value));
}
return node;
}
//탐색
public boolean search(int value){
return searchRecursive(root, value);
}
private boolean searchRecursive(TreeNode node, int value) {
if(node == null){
return false;
}
if(value == node.getValue()){
return true;
}
return value < node.getValue() ? searchRecursive(node.getLeft(), value) : searchRecursive(node.getRight(), value);
}
//순회
public void preorderTraversal(TreeNode node){
if(node!=null){
visit(node);
preorderTraversal(node.getLeft());
preorderTraversal(node.getRight());
}
}
public void inorderTraversal(TreeNode node){
if(node != null){
inorderTraversal(node.getLeft());
visit(node);
inorderTraversal(node.getRight());
}
}
public void postorderTraversal(TreeNode node){
if(node != null){
postorderTraversal(node.getLeft());
postorderTraversal(node.getRight());
visit(node);
}
}
private void visit(TreeNode node) {
System.out.println("doing some : " + node);
}
}
class TreeNode {
private int value;
private TreeNode left;
private TreeNode right;
public TreeNode(int value){
this.value = value;
this.left = null;
this.right = null;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
}