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

이진탐색 트리 구조

---

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

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

 

이진탐색 트리의 삽입

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

삽입 코드를 작성해 보면,

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 + " -> ");
    }
}

 

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

 

BFS - 너비 우선 탐색, DFS - 깊이 우선 탐색 알고리즘은 해당 포스트를 참고 하시길 바랍니다.

 

References

---

blog.naver.com/swoh1227/222175350122

k3068.tistory.com/30