[JAVA] 이진탐색트리

[JAVA] 이진 탐색 트리

이진 탐색 트리란?

이진 탐색 트리(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();
}