[자료구조] 주어진 트리가 이진탐색트리인지 확인하기

---

이전 포스팅 [이진탐색트리] 와[배열로 이진탐색트리 만들기]를 먼저 참고하시기 바랍니다.

---

[ 이진트리인지 확인하기 ]

주어진 트리가 이진트리인지 확인하는 가장 간단한 방법은 주어진 트리를 중위순회하면서 나온 데이터들이 모두 오름차순으로 정렬되는지 확인하면 된다. 이유는 이진탐색트리의 전제조건때문인데, 이는 이전 포스팅을 확인하기 바란다.

아래와 같은 트리가 있을 때, 이 트리가 이진탐색트리인지 확인하는 함수를 작성한다.

[ 배열을 사용해서 확인하기 ]

1. 주어진 트리를 중위순회하며 데이터를 임의의 다른 배열에 저장한다.

2. 저장된 데이터들이 모두 오름차순으로 정렬되어있는지 확인한다.

3. 저장된 데이터가 모두 오름차순으로 정렬되어있으면 True, 아니라면 False를 반환한다.

[ JAVA 코드 ]

 
public class IsBST1 {
 
    public static void main(String[] args) {
 
        BST1 bst = new BST1(10);
        System.out.println(bst.isBST());
    }
}
 
class BST1 {
 
    Node root;
    int size;
    int idx;
 
    static class Node {
        int data;
        Node left;
        Node right;
 
        public Node(int data) {
            this.data = data;
            this.left = this.right = null;
        }
    }
 
    public BST1(int size) {
        this.idx = 0;
        this.size = size;
        root = makeTree(0, size - 1);
    }
 
    public Node makeTree(int start, int end) {
 
        if (start > end)
            return null;
 
        int mid = (start + end) / 2;
        Node node = new Node(mid);
        node.left = makeTree(start, mid - 1);
        node.right = makeTree(mid + 1, end);
        return node;
    }
 
    public boolean isBST() {
        int[] arr = new int[size];
        traverseInOrder(root, arr);
 
        for (int i = 0; i < size - 1; i++)
            if (arr[i] > arr[i + 1])
                return false;
        return true;
    }
 
    public void traverseInOrder(Node root, int[] arr) {
 
        if (root == null)
            return;
        traverseInOrder(root.left, arr);
        arr[idx++] = root.data;
        traverseInOrder(root.right, arr);
    }
}
 

[ 배열을 사용하지 않고 확인하기 ]

위에서는 트리의 중위 순회 결과를 새로운 배열에 저장하고, 이 배열에 저장된 데이터들을 다시 확인하면서 이진탐색트리인지 아닌지 확인했다. 이 방법은 트리에 저장된 노드의 갯수만큼의 길이를 갖는 배열이 필요로 한다는 단점이 있다.

하지만, 굳이 새로운 배열을 선언하지 않고, 주어진 트리에서 중위 순회를 하며 현재 값과 다음 값과의 비교를 통해 이진탐색트리의 조건을 만족하는지 확인할 수 있다.

[ JAVA 코드 ]

 
public class IsBST2 {
 
    public static void main(String[] args) {
        BST2 bst = new BST2(10);
        System.out.println(bst.isBST());
    }
}
 
class BST2 {
 
    Node root;
    Integer prev;
    int size;
 
    static class Node {
        int data;
        Node left;
        Node right;
 
        public Node(int data) {
            this.data = data;
            this.left = this.right = null;
        }
    }
 
    public BST2(int size) {
        this.prev = null;
        this.size = size;
        root = makeTree(0, size - 1);
    }
 
    public Node makeTree(int start, int end) {
 
        if (start > end)
            return null;
 
        int mid = (start + end) / 2;
        Node node = new Node(mid);
        node.left = makeTree(start, mid - 1);
        node.right = makeTree(mid + 1, end);
        return node;
    }
 
    public boolean isBST() {
        return isBST(root);
    }
 
    public boolean isBST(Node root) {
        if (root == null)
            return true;
 
        if (!isBST(root.left))
            return false;
 
        if (prev != null && root.data < prev)
            return false;
 
        prev = root.data;
 
        if (!isBST(root.right))
            return false;
 
        return true;
    }
 
}