이진 탐색 트리란?
이진 탐색 트리(Binary Search Tree)란 부모노드의 값을 기준으로하여 더 작은 값은 왼쪽 자식노드에, 더 큰 값은 오른쪽 자식노드에 이어지는 트리의 형태를 말한다. 탐색하고자 하는 값이 있을 때에는 현재 노드를 중심으로 더 가까운 값들만 골라서 탐색하게 되므로 시간복잡도에서 유리한 시간을 갖는다.
또한 루트노드를 기준으로 자식노드가 연결되므로, 노드가 입력되는 순서에 따라 트리의 모양이 달라진다는 특징을 가진다.
트리 구현
먼저 처음 입력값으로 루트노들르 만들고 그 뒤부터는 노드와의 값을 비교해 탐색하는 노드보다 값이크면 오른쪽 자식노드를, 값이 작다면 왼쪽 자식 노드를 탐색한다. 해당 자식노드가 비어있다면 새로운 노드가 그 위치에 들어가게 되고, 그 노드가 존재한다면, 그 자식노드를 중심으로 함수를 재귀호출하는 방법이다. 코드는 아래와 같다.
소스코드
static class TreeNode{
int value;
TreeNode left;
TreeNode right;
public TreeNode(int v) {value = v;}
}
// 자식노드와 부모노드 연결 함수
static void link_node(TreeNode parent, int value){
// 현재 값이 탐색하고 있는 노드(parent)보다 크다면
// 오른쪽 자식 노드를 탐색
if(value > parent.value){
// 오른쪽 자식 노드가 null 이라면 해당 노드로 연결
if(parent.right == null){
TreeNode newNode = new TreeNode(value);
parent.right = newNode;
} // 오른쪽 자식 노드가 있다면 해당 노드를 탐색노드로 하여 재귀
else{
link_node(parent.right, value);
}
}else{ // 값이 더 작다면 왼쪽 자식 노드 탐색
if(parent.left == null){
TreeNode newNode = new TreeNode(value);
parent.left = newNode;
}else{
link_node(parent.left, value);
}
}
}트리의 순회
1) 전위순회
루트노드를 탐색하고 왼쪽자식노드를 탐색하면 그 단계에서는 왼쪽 자식노드가 루트노드(부모노드)가 되고 그 밑에 있는 자식노드들이 왼쪽자식노드, 오른쪽자식노드가 된다.
// 전위순회 (루트 - 왼 - 오)
static void preorder(TreeNode node){
System.out.print(node.value);
if(node.left != null)
preorder(node.left);
if(node.right != null)
preorder(node.right);
}2) 중위순회
왼쪽자식노드 - 루트노드 - 오른쪽자식노드 순으로 탐색하는 방법이다.
// 중위순회 (왼 - 루트 - 오)
static void inorder(TreeNode node){
if(node.left != null)
inorder(node.left);
System.out.print(node.value);
if(node.right != null)
inorder(node.right);
}3) 후위순회
왼쪽자식노드 - 오른쪽자식노드 - 루트노드 순으로 탐색하는 방법이다.
// 후위순회 (왼 - 오 - 루트)
static void postorder(TreeNode node){
if(node.left != null)
postorder(node.left);
if(node.right != null)
postorder(node.right);
System.out.print(node.value);
}입력을 받아 트리를 만들고 트리를 순회하는 메인함수는 아래와 같다.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
TreeNode root = new TreeNode(sc.nextInt());
for(int i=0; i<N-1; i++)
link_node(root, sc.nextInt());
preorder(root);
System.out.println();
inorder(root);
System.out.println();
preorder(root);
System.out.println();
}
'JAVA' 카테고리의 다른 글
| [JAVA] 조합(Combination) 구현 (0) | 2018.11.23 |
|---|---|
| [JAVA] ArrayList 배열로 바꾸기 (0) | 2018.11.21 |
| [JAVA] 입력 클래스 (0) | 2018.10.10 |
| [JAVA] Scanner함수 next(), nextLine() 차이 (0) | 2018.09.20 |