[Java] 이진검색트리(BST) 구현

이진검색트리 개념

class Node {

    int value;
    Node left = null;
    Node right = null;

    Node(int value) {
        this.value = value;
    }
}

Node 클래스

위와 같은 BST를 만들어보자.

노드 추가

class BinaryTree {

    Node head;

    void add(Node node) {

        Node parent = head;
        Node now = head;
        while (now != null) {
            parent = now;
            if (now.value > node.value) {
                now = now.left;
            } else {
                now = now.right;
            }
        }

        if (parent == null) {
            head = node;
        } else if (parent.value > node.value) {
            parent.left = node;
        } else {
            parent.right = node;
        }
    }
}

Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
Node node6 = new Node(6);

BinaryTree bt = new BinaryTree();
bt.add(node3);
bt.add(node2);
bt.add(node1);
bt.add(node5);
bt.add(node6);
bt.add(node4);

노드 찾기

class BinaryTree {

    // ...

    boolean find(Node node) {
        Node now = head;
        while (now != null) {
            if (now.value == node.value) {
                return true;
            }
            if (now.value > node.value) {
                now = now.left;
            } else {
                now = now.right;
            }
        }
        return false;
    }
}

bt.find(new Node(3)); // true 
bt.find(new Node(7)); // false

탐색

DFS

class BinaryTree {

    // ...

    // Preorder
    void dfs(Node node) {
        if (node == null) {
            return;
        }
        System.out.println(node.value);
        dfs(node.left);
        dfs(node.right);
    }
}

bt.dfs(node3);

// 출력
3
2
1
5
4
6

BFS

class BinaryTree {

    // ...

    void bfs(Node node) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        Node now;
        while (!queue.isEmpty()) {
            now = queue.poll();
            System.out.println(now.value);
            if (now.left != null) {
                queue.add(now.left);
            }
            if (now.right != null) {
                queue.add(now.right);
            }
        }
    }
}

bt.bfs(node3);

// 출력
3
2
5
1
4
6