자료구조 - 이진탐색 트리 (Binary-Search-Tree)

이진탐색 트리 구조
References

이진탐색 트리 구조

이진탐색 트리의 조건 (이진 트리와 다르다)

모든 원소는 중복된 값을 가지면 안된다.
트리의 루트를 기준으로 왼쪽에 존재하는 노드들의 값은 루트의 값보다 작아야 한다.
반대로 오른쪽에 존재하는 노드들의 값은 루트의 값보다 커야 한다.

이진탐색 트리의 삽입

위에 이진트리의 조건을 이용해서 삽입을 위 그림 처럼 해주면 된다.

삽입 코드를 작성해 보면,

public class BinaryTree {
    Node root;

    public void insertNode(int value) {
        /* root가 비었을 경우 */
        if(root == null){
            root = new Node(value);
        }else {
            Node temp = this.root;

            while(true) {
                /* 왼쪽으로 가야 하는 경우 */
                if(temp.value > value){
                    if(temp.left != null){
                        temp.left = new Node(value);
                        break;
                        }
                    temp = temp.left;
                }
                /* 오른쪽으로 가야 하는 경우 */
                else {
                    if(temp.right != null){
                        temp.right = new Node(value);
                        break;
                    }
                    temp = temp.right;
                }
            }
        }
    }
}

이진탐색 트리의 순회 방법

전위순회 (Pre-order)
- 루트 -> 왼쪽 - > 오른쪽

/* Pre-order (root - left - right) */
public void preOrderSearch(Node node) {
    if(node != null) {
        System.out.println(node.value + " -> ");
        preOrderSearch(node.left);
        preOrderSearch(node.right);
    }
}

A -> B -> D -> E -> C -> F -> G

중위순회 (In-order)
- 왼쪽 -> 루트 -> 오른쪽

/* In-order (left - root - right) */
public void inOrderSearch(Node node) {
    if(node != null) {
        inOrderSearch(node.left);
        System.out.println(node.value + " -> ");
        inOrderSearch(node.right);
    }
}

D -> B -> E -> A -> F -> C -> G

후위순회 (Post-order)
- 왼쪽 -> 오른쪽 - > 루트

/* Post-order (left - right - root) */
public void postOrderSearch(Node node) {
    if(node != null) {
        postOrderSearch(node.left);
        postOrderSearch(node.right);
        System.out.println(node.value + " -> ");
    }
}